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?

  • $\begingroup$ The decision problem is "Is there a tour shorter than x". So given a tour it's easy to check it. $\endgroup$ – xavierm02 Feb 13 '14 at 23:07
  • $\begingroup$ 4th paragraph of the introduction on en.wikipedia.org/wiki/Travelling_salesman_problem $\endgroup$ – xavierm02 Feb 13 '14 at 23:08
  • $\begingroup$ So the verification requirement applies only to the decision version of the problem? $\endgroup$ – David Zhang Feb 13 '14 at 23:11
  • $\begingroup$ The optimization problem is NP-hard. So it could be (is?) outside NP. $\endgroup$ – xavierm02 Feb 13 '14 at 23:13
  • $\begingroup$ 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). $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.