# Decision version of the traveling salesman problem and NP-hardness

Wikipedia says:

The problem has been shown to be NP-hard

and

the decision problem version ("given the costs and a number x, decide whether there is a round-trip route cheaper than x") is NP-complete.

How can the "non-decision problem" version be NP-hard? Doesn't this class contain decision problems, by definition? Is this some sort of abuse of notation? Are they just being overly flexible with the definition of NP-hard?

When we say that an optimization problem is NP-hard, what we mean is that its decision version is NP-hard. In this particular case, according to Wikipedia more is true: the function version (finding an optimal solution) is complete for $\mathsf{FP}^\mathsf{NP}$.

• But the second sentence says that the decision version of TSP is NP-complete, hence in NP. Why mention NP-hardness at all then? Dec 12 '16 at 21:01
• You are misquoting the Wikipedia article. The point the article is trying to make is that the function problem (finding an optimal tour) is complete from $\mathsf{FP}^\mathsf{NP}$. Regarding your exegetic question, I don't think there is any significance. Dec 12 '16 at 21:05
• I'm still a bit confused. The article says: TSP is $NP-hard$; TSP is complete for $FP^{NP}$; and the decision problem is $NP-complete$. Right? Isn't the third statement much stronger than the first, given what you said ("When we say that an optimization problem is NP-hard, what we mean is that its decision version is NP-hard")? Doesn't this extend to "When we say that an optimization problem is NP-complete, what we mean is that its decision version is NP-complete" Dec 12 '16 at 21:19
• You're reading it too closely. Perhaps for the author, the convention of identifying the optimization problem with its decision version is OK for NP-hardness but not OK for NP-completeness. But the facts are clear: the decision version of TSP is NP-complete, and its function version is complete for $\mathsf{FP}^{\mathsf{NP}}$. Dec 12 '16 at 21:53

No, it is not the abuse of notation.

First of all, very formally $NP$ contains only decision problems, while $NP$-hard contain problems to which all problems in $NP$ can be reduced. So, if you have an optimization problem for which the decision version is $NP$-complete, it automatically becomes $NP$-hard (but not complete). Vice versa, for hard optimization problem the decision version becomes complete.

Note, that search vs decision versions of a problem are not always equivalent in terms of hardness. They are for an optimization search or $NP$-complete problems though.

Also, I expect some comments about stuff above from people who might have seen different definitions. I warn that different books allow different level if strictness of their definitions.