patternMinor
Decision version of the traveling salesman problem and NP-hardness
Viewed 0 times
salesmanproblemthehardnessversiontravelingdecisionand
Problem
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?
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?
Solution
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}$.
Context
StackExchange Computer Science Q#67300, answer score: 2
Revisions (0)
No revisions yet.