The Polynomial Hierarchy

Alternating quantifier blocks stack NP and coNP into an infinite tower.

The idea

The polynomial hierarchy extends $\mathbf{NP}$ and $\mathbf{coNP}$ by allowing the quantifiers over certificates to alternate. A language is in $\mathbf{NP}$ when membership has a short certificate: $x$ belongs exactly when some polynomially bounded string makes a polynomial-time verifier accept. Many natural questions do not have that one-quantifier shape. Whether a circuit is the smallest circuit computing its function asserts that every smaller circuit computes a different function — a $\forall$ where $\mathbf{NP}$ supplies only an $\exists$.

The level $\Sigma_k^{p}$ consists of the languages $L$ with

$x \in L \iff \exists u_1\, \forall u_2\, \exists u_3 \cdots Q_k u_k\; V(x, u_1, \ldots, u_k) = 1,$

where the $k$ blocks alternate beginning at $\exists$, each $u_i$ is polynomially bounded, and $V$ runs in polynomial time. $\Pi_k^{p}$ is defined the same way with the blocks beginning at $\forall$. Each level contains all the ones below it, and $\mathbf{PH}$ is the union of them all. In particular $\Sigma_1^{p} = \mathbf{NP}$ and $\Pi_1^{p} = \mathbf{coNP}$, and at the base of the tower sits $\mathbf{P}$, the level with no quantifier blocks at all.

We can read the quantifiers as a game: a prover plays the $\exists$ moves and wants $V$ to accept, and an adversary plays the $\forall$ moves and wants it to reject. Whether extra moves buy extra power is not known: the levels are believed to be distinct, but no separation has been proved, and many results take the conditional form "if such-and-such held, the hierarchy would collapse to a finite level".

Ways to work on it

• Walkthrough. Define the hierarchy's levels by alternating quantifiers, and see what collapse means.
• Practice. Read a quantifier prefix and name its level of the hierarchy.
• Hardest. Complement a level, then reason about PH versus PSPACE.

Not sure where to start? Take the ten-question placement test.