Project ForgeTheory of Computation
Grammars, Turing Machines & Decidability
GATE 2012
Medium
Assuming P ≠ NP, which of the following is TRUE?
- ANP-complete = NP
- NP-complete ∩ P = ∅
- CNP-hard = NP
- DP = NP-complete
Explanation
If any NP-complete problem were in P, then (by NP-completeness, every NP problem reduces to it in polynomial time) all of NP would be in P, contradicting P ≠ NP. So no NP-complete problem can be in P, i.e. NP-complete ∩ P = ∅.
Source: GATE CS 2012 (2012)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.