Polynomial Hierarchy

The polynomial hierarchy (PH) extends the complexity classes NP and co-NP through alternating quantifier levels. At the first level: Σ₁^P = NP (existential quantifier), Π₁^P = co-NP (universal quantifier). Each successive level adds one more alternation — Σ₂^P captures problems of the form 'there exists a witness such that for all adversaries, a condition holds,' with a Σ₁^P oracle. The union of all levels is PH.

If NP = co-NP, the hierarchy collapses to its first level. If P = NP, it collapses entirely to P. Most complexity theorists believe neither collapse occurs — that each level is strictly larger than the one below — but no unconditional proof exists. Problems complete for Σ₂^P arise naturally in AI planning, two-player games, and succinct circuit problems. The polynomial hierarchy sits strictly inside PSPACE, itself inside EXP.