The Polynomial Hierarchy

NP asks a one-quantifier question: does there exist a short certificate? coNP asks the mirror image: do all candidates check out? But real questions are often nested. "Is there a chess move so that, whatever Black replies, I have a winning follow-up?" That is \exists\,\forall — two quantifiers, alternating. Add a third, "…and for which there exists a mate," and you have \exists\,\forall\,\exists.

The polynomial hierarchy (PH) is the tower you climb by stacking more and more alternating quantifiers, each ranging over a polynomial-size certificate. Its bottom rungs are old friends — NP and coNP — and each new rung is a strictly richer class of question (or so almost everyone believes). It is the natural home for problems that are "one step harder than NP."

Building the levels from alternating quantifiers

Fix a polynomial-time verifier V and let every quantified variable range over strings of length polynomial in the input x. The two families of classes are defined by the leading quantifier and the number of alternations.

\Sigma_k^{\mathrm{P}}: problems expressible with k alternating quantifier blocks starting with \exists — \exists w_1\,\forall w_2\,\exists w_3\cdots\,V(x, w_1,\dots,w_k).
\Pi_k^{\mathrm{P}}: the same but starting with \forall — \forall w_1\,\exists w_2\,\forall w_3\cdots\,V(x, w_1,\dots,w_k).
The base: \Sigma_0^{\mathrm{P}} = \Pi_0^{\mathrm{P}} = \mathrm{P} (no quantifiers — just decide directly).
Level 1: \Sigma_1^{\mathrm{P}} = \mathrm{NP} (one \exists) and \Pi_1^{\mathrm{P}} = \mathrm{coNP} (one \forall).

Negating a \Sigma_k formula flips every quantifier and gives a \Pi_k formula, so \Pi_k is exactly \mathrm{co}\Sigma_k — the two columns of the tower are complements of each other, level by level, just as coNP is the complement of NP.

A concrete level-2 problem: MIN-DNF — "is there a DNF formula of size \le s that agrees with the given formula on every input?" That is \exists (a small formula) \forall (all inputs), a \Sigma_2^{\mathrm{P}} question, and it is not known to sit in NP or coNP.

The same tower, defined by oracles

There is a second, equivalent way up — and it is the one that makes the hierarchy's structure obvious. Give an NP machine a free oracle: a black box that answers any question from a class C in a single step. Write \mathrm{NP}^{C} for "NP with a C-oracle."

\Sigma_0^{\mathrm{P}} = \mathrm{P}, and then each level is NP relative to the one below: \Sigma_{k+1}^{\mathrm{P}} = \mathrm{NP}^{\Sigma_k^{\mathrm{P}}}.
So \Sigma_1 = \mathrm{NP}^{\mathrm{P}} = \mathrm{NP}, and \Sigma_2 = \mathrm{NP}^{\mathrm{NP}} — guess a certificate, then consult an NP oracle to check a nested claim about it. That inner NP call is the second quantifier.
\Pi_{k}^{\mathrm{P}} = \mathrm{co}\Sigma_{k}^{\mathrm{P}}, and one also defines \Delta_{k+1}^{\mathrm{P}} = \mathrm{P}^{\Sigma_k^{\mathrm{P}}} (deterministic with the oracle) sitting between the levels: \Sigma_k \cup \Pi_k \subseteq \Delta_{k+1} \subseteq \Sigma_{k+1} \cap \Pi_{k+1}.
The whole hierarchy is the union of all levels: \displaystyle \mathrm{PH} = \bigcup_{k \ge 0} \Sigma_k^{\mathrm{P}}.

The picture is a genuine containment ladder: each class contains everything below it, the \Sigma and \Pi columns meeting at the shared \Delta rungs, and the whole tower packed inside PSPACE. Widely believed to be infinitely tall — but proving it is (yet again) open.

The collapse theorem

The hierarchy's levels are conjectured to be all distinct — a strictly growing tower. But they are knotted together by a startling rigidity result: the tower cannot have a "false ceiling." If it ever stops growing, it stops completely.

If \Sigma_k^{\mathrm{P}} = \Sigma_{k+1}^{\mathrm{P}} for some k, then \mathrm{PH} = \Sigma_k^{\mathrm{P}} — the entire hierarchy collapses to level k.
Equivalently, if any level equals the next, or if \Sigma_k = \Pi_k, everything above it folds down onto that level.
Special cases you should recognise: if \mathrm{P} = \mathrm{NP} then \mathrm{PH} = \mathrm{P} (collapse to level 0); if \mathrm{NP} = \mathrm{coNP} (i.e. \Sigma_1 = \Pi_1) then \mathrm{PH} = \mathrm{NP} (collapse to level 1).

The intuition: an extra quantifier can be simulated away once two adjacent levels coincide, and that simulation cascades all the way up. This is why complexity theorists prize the phrase "…unless the polynomial hierarchy collapses." Showing that some hypothesis would collapse PH is treated as very strong evidence against that hypothesis — because almost nobody believes the tower is finite.

And the outer bound is easy to state: \mathrm{PH} \subseteq \mathrm{PSPACE}. A polynomial-space machine can evaluate a fixed number of alternating quantifiers by looping over all certificates in turn, reusing the same space each time. Whether that containment is strict is — you guessed it — open, and would follow from the hierarchy being infinite.

Think of a \Sigma_{k+2} question as an \exists in front of a \Pi_{k+1} question. Suppose we are told \Sigma_k = \Pi_k. The \Pi_{k+1} part is "\forall then a \Sigma_k"; using the hypothesis you can rewrite that inner \Sigma_k as a \Pi_k, which merges its leading \forall with the outer one — two \forall blocks fuse into one. One alternation vanishes, so \Sigma_{k+2} drops to \Sigma_{k+1}. Repeat, and every level above k tumbles down. The magic is that adjacent quantifiers of the same type always merge; equality of two levels is exactly what lets you change type and trigger the merge.

A common slip is to count raw quantifier symbols. The level is set by the number of alternation blocks, not the number of quantifiers. The formula \exists w_1\,\exists w_2\,\forall w_3\,V has three quantifiers but only two blocks (an \exists-block then a \forall-block), so it is \Sigma_2, not \Sigma_3 — you may always pack a run of same-type quantifiers into one by pairing their witnesses. Only a change of quantifier type starts a new block and climbs a level. Miscounting here is the fastest way to place a problem on the wrong rung.