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. 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 '12 at 8:18

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.