Why is the decision problem of the "Travelling Salesman" $\in \mathcal{NP}$?

Question

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?"

Answer 1

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

Answer 2

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.