10
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How is it shown that the problem goblin's considering is FP$^{NP}$-hard? ​ ​ $\endgroup$ – user57159 Mar 27 '16 at 22:45
  • $\begingroup$ For that matter, your next-to-last sentence is equivalent to ​ NP = coNP , ​ since that sentence's problem is trivially in coNP: There's a shorter tour if and only if T is not optimal. ​ ​ ​ ​ $\endgroup$ – user57159 Apr 4 '16 at 6:56
  • $\begingroup$ @RickyDemer I think, at the time of writing, I meant to specify additional constraints on the word "optimal" (such as uniqueness or something), but never found a good way to word it. Regardless, that would be an error too considering I'm not immediately aware of a reduction of an NP-complete problem to it. I'll remove it to avoid confusion. $\endgroup$ – mdxn Aug 9 '16 at 13:25
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could there be other, less efficient representations of weighted graphs such that the decision problem is no longer NP-hard? $\endgroup$ – goblin Mar 20 '16 at 10:37
  • $\begingroup$ Sure: if you have a decision procedure that executes in time $f(n)$ using an efficient representation, require an instance of the problem of size $n$ (with the efficient representation), to be represented by $f(n)$ dummy symbols followed by the efficient representation. With this representation, the decision procedure has time complexity $O(n)$ in the size of the input. $\endgroup$ – Rob Arthan Mar 20 '16 at 20:45
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Does this mean that we have to do something like deal with $\mathbb{Q}_{\geq 0}$-weighted finite graphs only, because otherwise if we're dealing with $\mathbb{R}_{\geq 0}$-weighted finite graphs, then suddenly there's uncountably many of them and fundamentally we can't code them as natural numbers? $\endgroup$ – goblin Mar 20 '16 at 0:03
  • $\begingroup$ @goblin: yes, but in practice this isn't an issue because you'll only store the weights of an actual graph you care about to finite precision anyway. $\endgroup$ – Qiaochu Yuan Mar 20 '16 at 3:11

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.