Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Travelling Salesman

  1. May 5, 2008 #1
    I don't understand how travenlling salesman is NP-complete. In particular, how can you possibly verify that a given route is the shortest one in polynomial time?
  2. jcsd
  3. May 5, 2008 #2


    User Avatar
    Gold Member

    The TSP isn't NP-complete - it's NP-hard. But the question: Is there a path shorter than x is NP-complete. A problem is NP-hard iff it can be used to solve an NP-complete problem in O(n) time.
    Last edited: May 5, 2008
  4. May 5, 2008 #3
    TSP is only NP-complete if you use the decision version of the problem.

    Side note, TSP is one reason why combinatorial optimization is one of my favorite subjects.
  5. May 6, 2008 #4
    This makes a lot more sense.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook