1. May 5, 2008 #1

   Dragonfall

   

   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?

    

   Dragonfall, May 5, 2008
2. 
   Phys.org - latest science and technology news stories on Phys.org

   • • Mathematicians solve age-old spaghetti mystery
   • • Mathematician discusses solving a seemingly unsolvable equation
   • • Kurdish refugee wins 'Nobel of mathematics' Fields medal (Update)
3. May 5, 2008 #2

   daniel_i_l

   

   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

   daniel_i_l, May 5, 2008
4. May 5, 2008 #3

   PowerIso

   

   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.

    

   PowerIso, May 5, 2008
5. May 6, 2008 #4

   Dragonfall

   

   This makes a lot more sense.

    

   Dragonfall, May 6, 2008

• Log in with Facebook
• Log in with Twitter

Your name or email address:

Do you already have an account?

• No, create an account now.
• Yes, my password is:
• Forgot your password?

Stay logged in