1. Not finding help here? Sign up for a free 30min 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

    daniel_i_l

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Travelling Salesman
Loading...