39
$\begingroup$

So, TSP (Travelling salesman problem) decision problem is NP complete.

But I do not understand how I can verify that a given solution to TSP is in fact optimal in polynomial time, given that there is no way to find the optimal solution in polynomial time (which is because the problem is not in P)?

Anything that might help me see that the verification can in fact be done in polynomial time?

Improve this question
$\endgroup$

5 Answers 5

Reset to default
22
$\begingroup$

To be more precise, we do not know if TSP is in $\mathsf{P}$. It is possible that it can be solved in polynomial time, even though perhaps the common belief is that $\mathsf{P} \neq \mathsf{NP}$. Now, recall what it means for a problem to be $\mathsf{NP}$-hard and $\mathsf{NP}$-complete, see for example my answer here. I believe your source of confusion stems from the definitions: an $\mathsf{NP}$-hard problem is not necessarily in $\mathsf{NP}$.

As you and the Wikipedia page you link states, the decision problem is $\mathsf{NP}$-complete: given the costs and an integer $x$, decide whether there is a tour cheaper than $x$. One way of seeing the problem is in $\mathsf{NP}$ is to see that given a solution, it is easy to verify in polynomial time whether the solution is cheaper than $x$. How can you do this? Just follow the tour given, record its total cost and finally compare the total cost to $x$.

Improve this answer
$\endgroup$
7
  • 2
    $\begingroup$ "Just follow the tour given, record its total cost and finally compare the total cost to x." -> Yes, but there are exponential number of tours to check! $\endgroup$
    – Lazer
    Commented Jul 20, 2012 at 7:45
  • 2
    $\begingroup$ I was just a tad too slow, it seems. ;-) $\endgroup$
    – Niel de Beaudrap
    Commented Jul 20, 2012 at 7:45
  • 4
    $\begingroup$ @Lazer No, there is exactly one tour to check. You are given a tour and you record its length. If it is less than $x$, output yes, otherwise no. $\endgroup$
    – Juho
    Commented Jul 20, 2012 at 8:02
  • $\begingroup$ "decide whether there is a tour" this definitely means that we are not given a tour. What am I missing? $\endgroup$
    – Lazer
    Commented Jul 20, 2012 at 8:04
  • 5
    $\begingroup$ @Lazer No, in the problem you are given a weighted graph and a target cost. The certificate is a tour. For an alternative explanation, see Niel's answer. Just as in the example on Wiki in the case of SUBSET-SUM, we are not given zero, but instead we are given a particular subset as a certificate. $\endgroup$
    – Juho
    Commented Jul 20, 2012 at 8:20
37
$\begingroup$

The crux is that you have to consider the decision problem:

Travelling Salesman Problem (Decision Version). Given a weighted graph G and a target cost C, is there a Hamiltonian cycle in G whose weight is at most C?

For a 'yes' instance, the certificate is just some Hamiltonian cycle whose weight is at most C. If you could solve this problem efficiently, you could find the cost of a minimum tour by binary search, starting with the weight of the entire network as an upper bound.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Make sure to explicitly say "Decision Version" or something along those lines. The TSP is an optimization problem, not a decision problem. This is a common misunderstanding, because CS types assume that TSP refers to the decision problem, when TSP refers to an optimization problem. Being explicit about this being a decision version of TSP is vital to avoid this misunderstanding. $\endgroup$
    – Tom Mercer
    Commented Feb 13, 2020 at 17:02
6
$\begingroup$

You are probably thinking of the problem of determining whether a given solution to the TSP is the best solution. However, there is no known polynomial solution for this, which means that this problem is in NP-hard, but not necessarily NP-Complete.

The TSP Decision Problem is actually about determining whether the weight of any solution in a graph G is at most cost C (as explained better in Niel's answer), which is certainly verifiable in polynomial time.

Improve this answer
$\endgroup$
6
  • 6
    $\begingroup$ Sorry for the pedantry, but TSP is not NP-hard because there are $O(n!)$ tours. For example, sorting is in P although there are $n!$ possible permutations as well. Huge or quickly growing search spaces don't always imply hardness. $\endgroup$
    – Juho
    Commented Jul 20, 2012 at 14:49
  • $\begingroup$ @Juho It is possible to verify that a sequence is sorted, by simply checking that $n_0 <= n_1 <= ...$. However, to know that something is the BEST solution for TSP, it is required to know that the cost is the minimum cost, which inherently requires knowing all other costs. $\endgroup$
    – Casey Kuball
    Commented Jul 20, 2012 at 14:53
  • 4
    $\begingroup$ No, you can obtain the optimum even without computing the lengths of all the other tours. And yes, it is possible to prove this is in fact the optimum without computing all the other tours. For an example consider branch & bound. $\endgroup$
    – Juho
    Commented Jul 20, 2012 at 15:09
  • 9
    $\begingroup$ All I'm saying is that huge search spaces don't necessarily mean the problem is difficult. Even when we for example don't know of a better algorithm than brute-force that enumerates all the possibilities, it doesn't mean it's the only algorithm out there. Dynamic programming is good example even here: the Held-Karp algorithm is an exact algorithm for TSP running in $O(n^22^n)$ time. Sorry, this is arguably just nitpicking, but I just wanted to add a reminder :) $\endgroup$
    – Juho
    Commented Jul 20, 2012 at 15:15
  • $\begingroup$ @Juho good point. I've updated the answer to no longer indicate brute force as the only option (only that there aren't any polynomial solutions). $\endgroup$
    – Casey Kuball
    Commented Jul 20, 2012 at 16:55
2
$\begingroup$

You can show that it is optimal given an oracle that solves the decision problem (see other answers) in polynomial time by querying if there exists a shorter solution. If your goal is to construct an optimal solution given the oracle, proceed as follows. Find the minimum total weight via binary search (or if there are non-integer edge weights, find a total weight which differs from the minimum by less than the min difference between two edge weights). Call this value $M$. For each edge in the graph, remove the edge, and query the oracle to see if there is still a solution of at most $M$. If so, leave the edge out, and continue. If not, put the edge back in, and continue. When you've processed all the edges, you'll be left with a Hamiltonian cycle of minimum weight.

Improve this answer
$\endgroup$
1
$\begingroup$

In your first sentence you mixed up "decision problem" and "optimality problem". They are different problems. One is: Given a list of cities and a distance d, can you visit all cities with a tour of length ≤ d? This is easily verified in linear time if I give you a sorted list of the cities. The other is: Given a list of cities, what is the shortest possible tour to visit all cities? Or the cities, and a tour, is that tour the shortest possible tour?

The first is a decision problem clearly in NP. The second is not a decision problem. The third is a decision problem, but not known to be in NP. (It is in co-NP).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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