# NP-Hard problems which are not NP-Complete

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.

-
add comment

## 1 Answer

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.

-
Also this one. –  Raphael Nov 27 '12 at 8:18
add comment