1. Is it always true that a problem which is ${\sf NP}$-hard but not ${\sf NP}$-complete is an optimization problem such as Minimum-Vertex-Cover and many others.

  2. Is it always true that a ${\sf NP}$-complete problem is always a decision problem such as vertex cover of size $k$, independent set of size $k$ and many others.


1 Answer 1

  1. No. E.g. the Halting problem is a decision problem which is NP-hard but not in NP and therefore not NP-complete.

  2. In normal usage yes, because an NP-complete problem must be in NP and NP is a class of decision problems. But see Decision problems vs “real” problems that aren't yes-or-no.

  • 1
    $\begingroup$ Also this one. $\endgroup$
    – Raphael
    Commented Nov 27, 2012 at 8:18

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.