Efficient Verification for Travelling Salesman Problem

Question

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?

Answer 1

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$.