How does one interpret statements like: "The traveling salesman problem is NP-complete?"

Question

The world abounds with statements like:

The traveling salesman problem is NP-complete.

But when I follow try to follow the Internet's links "down the rabbit hole," I don't get a truly sensible explanation of what these kinds of statements actually mean. I'll try to narrow this down to exactly the part where the "understanding black hole" occurs for me.

Take the traveling salesman problem, for example. When I read about this, all I really see is a function. Explicitly, there's a function that maps each weighted graph $G$ to the set of all Hamiltonian cycles in $G$ of minimum length. We might as well denote this function $\mathrm{TSF}$ and call it the traveling salesman function.

Now lets change topic a bit. When I follow the links related to NP-completeness, I manage to surmise that NP-completeness can be defined formally as a collection of subsets of $\mathbb{N}$.

$$\mathrm{NPCOMP} \subseteq 2^\mathbb{N}$$

In more detail, I surmise that

$$\mathrm{NPCOMP} = \mathrm{NP} \cap \mathrm{NPHARD}$$

Okay. So lets try putting these together. For convenience, by a blurgle, I'll mean a function that (like $\mathrm{TSF})$, assigns to each weighted graph $G$ a set of cycles in $G$. So what's going on, presumably, is that we can assign to each blurgle $\mathrm{FOO}$ a corresponding collection of subsets of $\mathbb{N}$, call this $\underline{\mathrm{FOO}}$. We can therefore define that a blurgle $\mathrm{FOO}$ is NP-complete iff $\underline{\mathrm{FOO}} \subseteq \mathrm{NPCOMP}.$

Hence, since $\mathrm{TSF}$ is a blurgle, we can reinterpret the opening statement as saying that: $$\underline{\mathrm{TSF}} \subseteq \mathrm{NPCOMP}$$

It furthermore seems reasonable to define that the travelling salesman problem equals $\underline{\mathrm{TSF}}.$

The trouble I'm having (and this is the "understanding black hole") is that I don't understand how to get from a blurgle $\mathrm{FOO}$ to $\underline{\mathrm{FOO}}$, which is meant to be a collection of subsets of $\mathbb{N}$. Therefore, although I can describe $\mathrm{TSF}$ in completely precise terms, I don't have a clue what $\underline{\mathrm{TSF}}$ is, except that its a collection of subsets of $\mathbb{N}$.

But its much worse than that. Speaking very generally, and forgetting all about graph theory and blurgles and what not, and just dealing with things at the highest possible level of abstraction, it seems that people are often dealing with an object $\mathrm{FOO}$, and then they start talking about the "complexity" of foo, which implicitly means that they're studying $\underline{\mathrm{FOO}},$ but it seems like, in general, no one ever really tells you how to get from $\mathrm{FOO}$ to $\underline{\mathrm{FOO}}.$

So, my question is:

Question. How does one interpret statements like: "The traveling salesman problem is NP-complete" when in reality the writer hasn't given you a problem at all, what they've given you is an object $\mathrm{FOO}$ (like the traveling salesman function), but next thing you know they're making statements about the corresponding problem $\underline{\mathrm{FOO}}$ without telling you precisely which subsets of $\mathbb{N}$ this refers to?

I suppose you're just meant to make an educated guess: but, if so, how are we meant to make this guess, and why would the reader's guess agree with what the writer is actually thinking?

Answer 1

To go from "the traveling salesman problem" to a subset of $\mathbb{N}$ you need to pick a reasonable encoding of weighted graphs as natural numbers (so you can write down the subset of weighted graphs with a Hamiltonian cycle of less than some length as a subset of the natural numbers). These encodings are not unique, and NP-completeness could depend on the encoding (for example, a very bad encoding would be to start with a reasonable encoding, then recode every natural number $n$ as the string consisting of $2^n$ consecutive $1$s, then a $2$).

This is why you need to pick a reasonable encoding. In practice I think everyone agrees on what reasonable encodings are, and all reasonable encodings should return the same answer (in that they should either all give an NP-complete problem or not) because they should all be recodable in terms of each other in polynomial time. It's not "isomorphism invariant" to worry about particular encodings.

Answer 2

You make a good point: NP-completeness is a property of decision problems, i.e., set-membership tests, and not a property of problems to compute more general functions (like finding an optimal Hamiltonian cycle in a given graph). So you have been misled in your Internet research if "all you see is a function": the decision problem associated with the travelling salesman problem is whether a given weighted graph has a Hamiltonian cycle of a given length. This decision problem is NP-complete if you use standard efficient representations of the weighted graph and the length of the cycle.

Answer 3

The set of $NP-complete$ problems is specific to decision problems. When people say that the Travelling Salesman Problem is NP-complete, they are referring to the decision variant of it:

Does there exist a tour of less than length $k$?

The above is different from the variant of the TSP where the goal is to produce the minimal weight tour (the one you are asking about).

This variant is a function problem, not a decision problem. There are function complexity classes that are analogous to decision ones, but allows for the output to be more than just ACCEPT or REJECT. For instance, the output could be the binary encoding a TSP tour or just an integer. The function analogue to the decision complexity class, $P$ (polynomial time), is known as $FP$, which is the set of functions computable in polynomial time on a deterministic Turing machine with an output tape. Likewise, there are other function classes like $FNP$ and $FEXP$.

The travelling salesman problem you are considering is complete for the function complexity class $FP^{NP}$, which is functional polynomial time with access to an $NP$ oracle (black box).