Through reading popular mathematical literature, I have learned the following two facts about computational complexity theory:
- The complexity class NP is the set of problems for which a candidate solution can be checked efficiently (i.e. in polynomial time).
- 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?