A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
The polynomial hierarchy (PH) is a stratification of complexity classes: Σ₁P = NP, Π₁P = co-NP, Σ₂P = NPNP, and so on. Each level corresponds to problems with an additional layer of quantified existential or universal conditions. Unless PH collapses (all levels coincide), the hierarchy is infinite and provides a fine-grained classification of hardness beyond NP.
You know NP from your prerequisite work: it is the class of problems where a "yes" answer can be verified in polynomial time, equivalently, where a nondeterministic Turing machine finds a "yes" solution in polynomial time. The polynomial hierarchy (PH) is what you get when you stack NP on top of itself — building problems that require multiple alternating layers of search and verification.
The key to understanding PH is the quantifier interpretation. NP corresponds to ∃x φ(x): "there exists a certificate x such that φ(x) holds in polynomial time." The class Σ₂P corresponds to ∃x ∀y φ(x,y): "there exists a strategy x such that for all adversarial responses y, φ holds." The class Π₂P corresponds to ∀x ∃y φ(x,y). In general, Σₖ involves k alternating quantifiers starting with ∃, while Πₖ starts with ∀. The complement of a Σₖ problem is a Πₖ problem — just as co-NP is the complement class of NP. Each new level of quantification adds a layer of search whose solution must survive all possible challenges from the next layer.
A concrete example: consider asking whether a Boolean circuit of size ≤ k computes a given function — this is in NP. But asking whether a circuit is *minimal* (no smaller circuit computes the same function) requires verifying that *for all* smaller circuits, they fail to match. This ∀-quantification over an exponential space pushes the problem into Π₂P. More generally, any problem where you must find something that works for all possible inputs or adversaries tends to land in Σ₂P or Π₂P, while problems requiring reasoning about the existence of witnesses to non-existence push into Σ₃P.
The hypothesis that PH does not collapse is central to modern complexity theory. If PH collapses to Σₖ for some k, every level above Σₖ would contain no new problems — meaning all alternating quantification beyond k levels is redundant. This would imply, as a special case, that co-NP ⊆ NP, resolving a major open problem. Most researchers believe the hierarchy is genuinely infinite — that each level of alternating quantification adds expressive power — but proving this remains far beyond current techniques. PH ⊆ PSPACE provides the ceiling: everything in the hierarchy can be decided with polynomial space. The hierarchy thus occupies a rich structural zone between NP and PSPACE, providing the right language for classifying problems whose hardness comes from nested search-and-verify structure.