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.
Keep practising Algorithms
Browse all Algorithms questions for GATE CSE, or explore more Computer Science topics.