3
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

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}$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ But the second sentence says that the decision version of TSP is NP-complete, hence in NP. Why mention NP-hardness at all then? $\endgroup$
    – theQman
    Commented Dec 12, 2016 at 21:01
  • $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Commented Dec 12, 2016 at 21:05
  • $\begingroup$ 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" $\endgroup$
    – theQman
    Commented Dec 12, 2016 at 21:19
  • 2
    $\begingroup$ 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}}$. $\endgroup$
    – Yuval Filmus
    Commented Dec 12, 2016 at 21:53
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.