1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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