nitpick: I wonder how TSP became NP complete. It would require to polynomial time algorithm to validate the solution. I doubt such algorithm does exist.
Strictly speaking, the only problems in NP are decision problems, so when we say "TSP is in NP", we're talking about the "decision version of TSP": given a graph G, does there exist a Hamiltonian circuit with total length <= K?
And it's straightforward to show that this problem is in NP, because if the answer is "yes", then simply exhibiting such a tour is enough to provide a polynomial-time-verifiable proof of the answer's correctness.
(Note that it is not known whether TSP is in co-NP, so it is not known whether one can produce a polynomial-time-verifiable proof of a "no" answer.)
But note that if it were to turn out that the decision version of TSP was solvable in polynomial time, then the optimization version would also be in P, because you can just binary-search on all of the possible values of K. This results in at most a polynomial slowdown.
teraflop|2 years ago
Strictly speaking, the only problems in NP are decision problems, so when we say "TSP is in NP", we're talking about the "decision version of TSP": given a graph G, does there exist a Hamiltonian circuit with total length <= K?
And it's straightforward to show that this problem is in NP, because if the answer is "yes", then simply exhibiting such a tour is enough to provide a polynomial-time-verifiable proof of the answer's correctness.
(Note that it is not known whether TSP is in co-NP, so it is not known whether one can produce a polynomial-time-verifiable proof of a "no" answer.)
But note that if it were to turn out that the decision version of TSP was solvable in polynomial time, then the optimization version would also be in P, because you can just binary-search on all of the possible values of K. This results in at most a polynomial slowdown.