Start learning →

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.
Practise this question with Quill — GATE CSE →

Keep practising Algorithms

Browse all Algorithms questions for GATE CSE, or explore more Computer Science topics.

Start a Algorithms lesson →
Related questions