snippetMajor
How can I verify a solution to Travelling Salesman Problem in polynomial time?
Viewed 0 times
salesmancanproblempolynomialtimeverifytravellinghowsolution
Problem
So, TSP (Travelling salesman problem) decision problem is NP complete.
But I do not understand how I can verify that a given solution to TSP is in fact optimal in polynomial time, given that there is no way to find the optimal solution in polynomial time (which is because the problem is not in P)?
Anything that might help me see that the verification can in fact be done in polynomial time?
But I do not understand how I can verify that a given solution to TSP is in fact optimal in polynomial time, given that there is no way to find the optimal solution in polynomial time (which is because the problem is not in P)?
Anything that might help me see that the verification can in fact be done in polynomial time?
Solution
The crux is that you have to consider the decision problem:
Travelling Salesman Problem (Decision Version). Given a weighted graph G and a target cost C, is there a Hamiltonian cycle in G whose weight is at most C?
For a 'yes' instance, the certificate is just some Hamiltonian cycle whose weight is at most C. If you could solve this problem efficiently, you could find the cost of a minimum tour by binary search, starting with the weight of the entire network as an upper bound.
Travelling Salesman Problem (Decision Version). Given a weighted graph G and a target cost C, is there a Hamiltonian cycle in G whose weight is at most C?
For a 'yes' instance, the certificate is just some Hamiltonian cycle whose weight is at most C. If you could solve this problem efficiently, you could find the cost of a minimum tour by binary search, starting with the weight of the entire network as an upper bound.
Context
StackExchange Computer Science Q#2834, answer score: 37
Revisions (0)
No revisions yet.