An NP-hard problem differs from an NP-complete one because NP-hard problems
Amust be in P
Bneed not be in NP; can be undecidable
Cmust be in coNP
Dmust have polynomial-time verifiers
Answer & Solution
Correct answer: B. need not be in NP; can be undecidable
NP-hard requires only that EVERY NP problem reduces to it. The hard problem itself may sit outside NP entirely. The Halting Problem is NP-hard but not even decidable, so certainly not in NP. NP-complete adds the second requirement: the problem must itself be in NP. Polynomial verification, P-membership and coNP-membership are not part of NP-hardness.
Related questions
The first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined forThe running time and space of Floyd-Warshall on a graph with V vertices and E edges is