Travelling Salesman

[Dragonfall]

Main Question or Discussion Point

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?

 

[daniel_i_l]

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.

 

[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.

 

[Dragonfall]

This makes a lot more sense.