# Efficient Verification for Travelling Salesman Problem

Through reading popular mathematical literature, I have learned the following two facts about computational complexity theory:

1. The complexity class NP is the set of problems for which a candidate solution can be checked efficiently (i.e. in polynomial time).
2. The Travelling Salesman Problem is one such problem, which asks for the shortest tour on a given graph.

I am having a bit of trouble reconciling these two facts. Given a candidate solution for the Travelling Salesman Problem, how can we verify it efficiently? I cannot see a way of doing it without essentially solving the problem over again. Is my understanding of the problem or of NP incorrect?

• The decision problem is "Is there a tour shorter than x". So given a tour it's easy to check it. – xavierm02 Feb 13 '14 at 23:07
• 4th paragraph of the introduction on en.wikipedia.org/wiki/Travelling_salesman_problem – xavierm02 Feb 13 '14 at 23:08
• So the verification requirement applies only to the decision version of the problem? – David Zhang Feb 13 '14 at 23:11
• The optimization problem is NP-hard. So it could be (is?) outside NP. – xavierm02 Feb 13 '14 at 23:13
• The decision problem is $NP$, so if $NP = P$, there is a polynomial time algorithm answering whether there is a path shorter than $x$. Then determining the length of the shortest path is also polynomial time (calculate the length of a path, and solve the decision problem in decrements from there). – Arthur Feb 14 '14 at 0:07

In computational complexity theory you usually talk about the decision versions of problems (see for example the Wikipedia article on NP). The decision version of the travelling salesman problem is: Is there a travelling salesman tour of length at most $L$. A solution to this decision problem can be easily checked by summing the costs of all used edges and checking whether this sum is less than or equal to $L$. This check can be performed in linear time. That is why the decision version of the travelling salesman problem is in $NP$.