2
$\begingroup$

One of the most well-known problems that belongs into the class of $\mathcal{NP}$-complete problems is the Travelling Salesman Problem. However, I fail to see why it is "so obviously" in $\mathcal{NP}$, as most resources on the internet claim. Let's gather what I know so far:

A decision problem is in $\mathcal{NP}$, if a "yes"-instance is verifyable in polynomial time.

This is an easy definition. E.g. I can see that for the decision problem "is $x$ the maximum of $x_1,\ldots,x_n$?", it is verifyable in $n$ steps whether the answer is correct.

Let's see the formulation of the Travelling Salesman Problem as a decision Problem.

For a simple graph $G$ with costs assigned to each edge, is there a hamiltonian cycle with total cost of at most $\lambda$?

I often read that a solution is verifyable as adding the costs of a tour has polynomial time complexity. The crux: we don't have a tour! We only have the information that there is a tour with total cost $\leq \lambda$.

In my understanding, a decision problem can't "return" the tour as well, so we can't just magically have one for which we just verify the sum of costs.

That leaves me with the question "Is there a way to construct a tour with a certain value in polynomial time?"

OR

"Is my definition of $\mathcal{NP}$ incorrect?"

$\endgroup$
  • $\begingroup$ What is the exact definition of $\mathcal NP$ you are using? $\endgroup$ – Johannes Kloos Oct 23 '13 at 13:59
  • $\begingroup$ @JohannesKloos ahem, read the question. I've written it there. $\endgroup$ – stefan Oct 23 '13 at 14:00
  • $\begingroup$ If you want to verify a solution, and a solution is a tour... there you have your tour! edit: But the solution to the problem is not "yes" or "no", in this case. Of course. Read Chen's Introduction to problem tractability, it helped me a lot to understand it better! And to answer your last question, if TSP is not in P, then there is no way to construct this tour in polynomial time AFAIK. $\endgroup$ – bernatguillen Oct 23 '13 at 14:01
  • $\begingroup$ @Duronman That's my point. The solution to a decision problem isn't a tour. It's "yes". Verify that this "yes" is correct is the point of $\mathcal{NP}$. $\endgroup$ – stefan Oct 23 '13 at 14:01
  • $\begingroup$ @Duronman (regarding your edited comment) A decision problem can't have any other output than "yes" or "no" by definition. how can you claim "not in this case though"? $\endgroup$ – stefan Oct 23 '13 at 14:05
3
$\begingroup$

A language $\def\L{{\mathcal L}}\L$ is in $\def\NP{{\mathscr N\!\!\mathscr P}}\NP$ if there is a nondeterministic turing machine $M$ that correctly decides $\L$ in polynomial time. This means that, given any string $s$, $M$ decides in polynomial time whether $s\in \L$. (Actually it only has to semidecide, but we can ignore that here.)

For a decision problem, say travelling salesman (TS), we define a language $\def\Lts{\L_{TS}}\Lts$ to consist of all pairs $(n, G)$ where $n$ is a bound on the tour length and $G$ is a (suitably encoded) graph with a tour of length at most $n$. Then the decision problem for $\Lts$ is: given some string, is it:

  1. Properly encoded in the form $(n, G)$ and, supposing that it is,
  2. Does $G$ have a tour of length at most $n$?

This language $\Lts$ is in $\NP$ if there is a nondeterministic turing machine $M$ which, given a string, decides this question in polynomial time. This is exactly what we mean when we say that $\Lts\in\NP$.

Now it is true that there is such an $M$. It works as you expect, by nondeterministically "guessing" a permutation of the vertices and then checking (in polynomial time) whether this permutation forms a tour that satisfies the bound.

At this point it should be clear where your confusion lies: $M$ is not verifying a solution to the decision problem; it is verifying whether a proposed string $s$ is an element of the language $\Lts$. To do this, it is sufficient to find, in polynomial time, an acceptable tour for the given graph $G$ and bound $n$ that are specified by $s$. The decision problem is in $\NP$ because $M$ can verify a proposed (or nondeterministically guessed) tour in polynomial time.

I strongly suggest that instead of depending on Wikipedia or other "popular" accounts, which are prone to this sort of confusion, that you read the first chapter or two of Michael R. Garey and David S. Johnson Computers and Intractibility: A Guide to the Theory of NP-Completeness (W.H. Freeman and Company, 1979).

$\endgroup$
3
$\begingroup$

In my understanding, a decision problem can't "return" the tour as well

You have misunderstood the verifier-based definition of NP. NP is a class of decision problems, but there is an additional requirement that there exists a proof that a "yes" answer is correct and that proof be verifiable in polynomial time. The need for a decision problem and the need for a polynomial time checkable proof are separate requirements.

Note that if you have an oracle that can answer yes/no questions about NP problems, you can use it to construct a proof, be it a Travelling Salesman tour, clique or a variable assignment that satisfies a Boolean formula. This is because all NP problems are downward self-reducible, meaning queries about subproblems of the main problem can be used to prune the search space down to a solution.

$\endgroup$

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.