patternModerate
NP-Hard problems which are not NP-Complete
Viewed 0 times
arehardcompletewhichproblemsnot
Problem
-
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.
-
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.
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.
-
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.
Solution
-
No. E.g. the Halting problem is a decision problem which is NP-hard but not in NP and therefore not NP-complete.
-
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.
No. E.g. the Halting problem is a decision problem which is NP-hard but not in NP and therefore not NP-complete.
-
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.
Context
StackExchange Computer Science Q#6910, answer score: 10
Revisions (0)
No revisions yet.