2
$\begingroup$

I'm studying some of computation theory and i encounter a big question mark. I have an optimization problem and i have to proof that is NP-HARD. I know that my problem can be reduced to another np-complete problem so my problem is np-hard. But my question is: why some algorithms are np-hard for the combinatorial version and the same problem transformed in a decision problem are np-complete?

I mean, if i have an optimization problem, is this np-hard because the decision problem can be reduced in a np-complete problem?

$\endgroup$
  • 3
    $\begingroup$ We had a discussion about this somewhere here, unfortunately I can't find it. For a problem to be NP-complete, it must be in the class NP which contains only decision problems. Optimization problems are not decision problems. They have a decision equivalent, and if it is NP-complete, then you can reduce optimization to this decision so you call it NP-hard. Hope this helps. $\endgroup$ – Eugene Dec 27 '16 at 10:56
  • 1
    $\begingroup$ @Eugene Yeah, I can't quite remember what question it was, either. Small correction, though: the optimization problem is NP-hard because you can reduce the NP-complete decision problem to it, not the other way around. $\endgroup$ – David Richerby Dec 27 '16 at 17:48
1
$\begingroup$

NP-hardness is a category that applies to both decision problems and optimization problems. In contrast, NP-completeness is a category that applies only to decision problems.

Here are the relevant definitions:

  • A decision problem is in NP if it is accepted by some polynomial time nondeterministic Turing machine.
  • A decision problem is NP-hard if all problems in NP can be reduced to it in polynomial time.
  • A decision problem is NP-complete if it is both in NP and NP-hard.
  • An optimization problem "max $f(x)$ subject to $x \in X$" is NP-hard if the decision problem "given $x$ and $y$, does there exist $x \in X$ such that $f(x) \geq y$?" is NP-hard.
  • An optimization problem "min $f(x)$ subject to $x \in X$" is NP-hard if the decision problem "given $x$ and $y$, does there exist $x \in X$ such that $f(x) \leq y$?" is NP-hard.

The decision problems used to define NP-hardness for optimization problems are known as decision versions of the optimization problems.

One could extend the definition of NP to optimization problems in various ways. For example, we could say that "max $f(x)$ subject to $x \in X$" is in NP if its decision version is in NP. This would also allow us to define NP-completeness for optimization problems. But for some reasons these definitions are not standard.

Let me also mention FNP, an extension of NP to functions.

$\endgroup$

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.