3
$\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?

Improve this question
$\endgroup$
2
  • 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, 2016 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, 2016 at 17:48

1 Answer 1

Reset to default
5
$\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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I suspect the answer is yes but just to clarify: Is it possible that solving the problem "given $x$ and $y$, does there exist $x\in X$ such that $f(x)\leq y$" is easy (say it is in $P$) but finding that $x$ is hard (say $NP$)? In general, does stating that an optimization problem is in $P$ give us any guarantees about how hard it is to find the optimizer or does it only make a statement about how easy it is to determine the existence of such an optimizer? $\endgroup$
    – user1936752
    Feb 3, 2020 at 14:38
  • 1
    $\begingroup$ There is an entire complexity class, called TFNP, consisting of problems in which $x \in X$ is guaranteed to exist but is expected to be hard to find. $\endgroup$
    – Yuval Filmus
    Feb 3, 2020 at 15:05

Your Answer

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

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