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
    Nov 27, 2012 at 8:18

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.