Solving the NP-Completeness of Travelling Salesman Problem

Dragonfall · May 5, 2008

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 · May 5, 2008

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 · May 5, 2008

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 · May 6, 2008

This makes a lot more sense.

Solving the NP-Completeness of Travelling Salesman Problem

Discussion

Similar threads

Graduate Difficult to understand the solution provided in the video (travelling salesman problem)

Undergrad Real life traveling salesman problem

Undergrad Is There a Polynomial Time Solution to the Travelling Salesman Problem?

Graduate Can you find the maximum distance in the travelling salesman problem?

Showing NP-completeness of longest path problem

Undergrad How Many Possible Routes in the Traveling Salesman Problem?

Reducing clique problem to independent set NP-completeness proof

High School What is the purpose of finding a lower bound in the Traveling Salesman Problem?

How Can the Traveling Salesman Problem Be Solved?