7
$\begingroup$

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?

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

1 Answer 1

Reset to default
6
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .