Complexity Classes

Reductions →

Polynomial-time mapping reductions and NP-completeness proofs.

Legend

P, NP, NP-complete, NP-hard

NP-hard is everything every NP problem reduces to in polynomial time — it extends past NP into harder classes. NP-complete is the overlap: NP-hard problems that are themselves still in NP.

The classic picture, drawn under the standard conjecture P ≠ NP. NP-complete sits exactly at NP ∩ NP-hard — these are the hardest problems still verifiable in polynomial time. TQBF is NP-hard but lives outside NP (it is PSPACE-complete), so it stays in the right lobe only.

World of Possibilities

The relationships between P, NP, and coNP are not settled. Each diagram below depicts a topology that is consistent with everything currently known — proving or disproving any of them would resolve one of the central open questions in complexity theory.

P ⊊ NP ∩ coNPcurrently conjectured

The textbook conjecture. Problems like FACTORING and GRAPH-ISO are believed to live in NP ∩ coNP yet outside P.

P = NPopen

All three classes collapse into one. P = NP forces NP = coNP automatically, since P is closed under complement.

NP = coNP, P ⊊ NPopen

NP is closed under complement, but verifying is still strictly easier than deciding.

P = NP ∩ coNPopen

NP and coNP differ, but every problem in both is already in P. No "intermediate" problems exist.