How can I verify a solution to Travelling Salesman Problem in polynomial time?

Question Detail: 

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?

Asked By : Lazer

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2834

Answered By : Juho

To be more precise, we do not know if TSP is in $\mathsf{P}$. It is possible that it can be solved in polynomial time, even though perhaps the common belief is that $\mathsf{P} \neq \mathsf{NP}$. Now, recall what it means for a problem to be $\mathsf{NP}$-hard and $\mathsf{NP}$-complete, see for example my answer here. I believe your source of confusion stems from the definitions: an $\mathsf{NP}$-hard problem is not necessarily in $\mathsf{NP}$.

As you and the Wikipedia page you link states, the decision problem is $\mathsf{NP}$-complete: given the costs and an integer $x$, decide whether there is a tour cheaper than $x$. One way of seeing the problem is in $\mathsf{NP}$ is to see that given a solution, it is easy to verify in polynomial time whether the solution is cheaper than $x$. How can you do this? Just follow the tour given, record its total cost and finally compare the total cost to $x$.