Polynomial hierarchy

The polynomial hierarchy is a hierarchy of complexity classes that refines the distinction between P and NP by bounding the number of alternations between existential and universal choices in a polynomial-time computation. It may be defined through alternating quantifiers, alternating machines, or oracle access to lower levels. These definitions yield the same hierarchy under polynomial-time reductions.

The hierarchy is denoted by

[ \mathrm{PH}=\bigcup_{k\geq 0}\Sigma_k^{\mathrm P} =\bigcup_{k\geq 0}\Pi_k^{\mathrm P}. ]

Its zeroth level is P. The first level contains NP and co-NP, while each subsequent level represents decision problems whose polynomially bounded certificates may alternate between existential and universal interpretation a fixed number of times. Whether any two adjacent levels are distinct remains unknown.

Historical development

Albert R. Meyer and Larry J. Stockmeyer introduced the polynomial hierarchy in the early 1970s while studying decision procedures whose complexity could not be represented adequately by the single distinction between deterministic and nondeterministic polynomial time. Their formulation organized nested forms of nondeterminism into a sequence indexed by alternation depth.

Later work connected this sequence with alternating Turing machines, quantified predicates, and computations using oracles. Celia Wrathall established an influential logical characterization in which a fixed number of alternating quantifier blocks precedes a polynomial-time predicate. This characterization made the hierarchy a standard interface between computational complexity theory and finite logical systems.

Formal definition

The classes at level zero are defined by

[ \Sigma_0^{\mathrm P}=\Pi_0^{\mathrm P}=\Delta_0^{\mathrm P} =\mathrm P. ]

For (k\geq 0), the higher levels may be defined recursively through polynomial-time oracle computation:

[ \Sigma_{k+1}^{\mathrm P} =\mathrm{NP}^{\Sigma_k^{\mathrm P}}, ]

[ \Pi_{k+1}^{\mathrm P} =\mathrm{coNP}^{\Sigma_k^{\mathrm P}}, ]

and

[ \Delta_{k+1}^{\mathrm P} =\mathrm P^{\Sigma_k^{\mathrm P}}. ]

Here, an oracle for a class means an oracle for any language complete for that class under an appropriate polynomial-time reduction. The resulting definition does not depend on the selected complete language.

The first level therefore satisfies

[ \Sigma_1^{\mathrm P}=\mathrm{NP}, \qquad \Pi_1^{\mathrm P}=\mathrm{coNP}, \qquad \Delta_1^{\mathrm P}=\mathrm P. ]

At the second level, a (\Sigma_2^{\mathrm P}) computation may be regarded as an NP computation with access to an NP oracle. A (\Pi_2^{\mathrm P}) computation has the complementary acceptance condition, while a (\Delta_2^{\mathrm P}) computation uses deterministic polynomial time with the same oracle access.

The recursive definition gives the containments

[ \Sigma_k^{\mathrm P}\cup\Pi_k^{\mathrm P} \subseteq \Delta_{k+1}^{\mathrm P} \subseteq \Sigma_{k+1}^{\mathrm P}\cap\Pi_{k+1}^{\mathrm P}. ]

Consequently, each level contains the classes below it, although equality between successive levels has not been resolved.

Quantified-predicate characterization

A language (L) belongs to (\Sigma_k^{\mathrm P}) if there are a polynomial (p) and a polynomial-time predicate (R) such that

[ x\in L \iff \exists y_1, \forall y_2, \exists y_3\cdots Q_k y_k; R(x,y_1,\ldots,y_k), ]

where every string (y_i) has length at most (p(|x|)), and the quantifiers alternate. The first quantifier is existential. The final quantifier (Q_k) is existential when (k) is odd and universal when (k) is even.

For (\Pi_k^{\mathrm P}), the corresponding expression begins with a universal quantifier:

[ x\in L \iff \forall y_1, \exists y_2, \forall y_3\cdots Q_k y_k; R(x,y_1,\ldots,y_k). ]

This logical form identifies alternation, rather than the total number of quantified variables, as the relevant computational resource. A single quantifier block may contain polynomially many variables without increasing the level of the hierarchy.

The quantifiers can also be interpreted as moves in a finite computational game. Existential blocks represent moves selecting a witness that supports acceptance, whereas universal blocks require acceptance for every permitted response. Because the number of alternations is fixed independently of the input length, the resulting classes remain within the polynomial hierarchy rather than extending to unrestricted polynomial-space computation.

Complete problems

Bounded forms of the quantified Boolean formula problem provide canonical complete problems for the hierarchy. A quantified Boolean formula with (k) alternating quantifier blocks, beginning with an existential block, defines a (\Sigma_k^{\mathrm P})-complete problem. Reversing the leading quantifier gives a (\Pi_k^{\mathrm P})-complete problem.

For example, the general form

[ \exists X_1\forall X_2\cdots Q_kX_k; \varphi(X_1,\ldots,X_k) ]

is complete for (\Sigma_k^{\mathrm P}) when the propositional matrix (\varphi) is represented with polynomial size and the quantifier prefix has exactly the required alternation pattern. Completeness is normally taken under polynomial-time many-one reductions.

In 1978, You Watanabe developed a block-preserving tableau transformation that converted polynomial-time predicates into quantified Boolean formulas without increasing their quantifier alternation depth. The construction assigned auxiliary variables within quantifier blocks according to their computational dependencies, allowing machine-based definitions of the hierarchy to transfer directly to bounded quantified satisfiability. This normalization became part of the standard equivalence between the predicate and complete-problem formulations.

The first level recovers familiar problems from NP and co-NP. At higher levels, completeness expresses the need to solve a polynomially bounded sequence of opposing witness conditions rather than merely to find one accepting certificate. Unrestricted quantified Boolean formulas permit a number of alternations that grows with the input and are instead complete for PSPACE.

Collapse properties

A collapse occurs when two levels that are potentially distinct are equal. If

[ \Sigma_k^{\mathrm P}=\Pi_k^{\mathrm P} ]

for some (k\geq 1), then every higher level reduces to that level, and

[ \mathrm{PH}=\Sigma_k^{\mathrm P}=\Pi_k^{\mathrm P}. ]

The proof absorbs each additional quantifier block into the assumed equality between existentially and universally initiated computations. Thus, separation at every level is necessary for the hierarchy to be infinite.

The equality (\mathrm P=\mathrm{NP}) would produce the most extensive collapse:

[ \mathrm{PH}=\mathrm P. ]

The weaker equality (\mathrm{NP}=\mathrm{coNP}) would also collapse the hierarchy, although the resulting common class would not thereby be known to equal P.

Nonuniform computation gives another conditional collapse. The Karp–Lipton theorem, named for Richard Karp and Richard Lipton, states that if

[ \mathrm{NP}\subseteq\mathrm{P/poly}, ]

then the polynomial hierarchy collapses to its second level. This connects the internal structure of PH with the size of Boolean circuits for NP languages.

Oracle constructions show that standard relativizing arguments cannot determine the hierarchy’s unconditional structure. There are oracles relative to which the hierarchy collapses and other oracles relative to which it has infinitely many distinct levels. These constructions establish limitations on proof methods that remain valid under arbitrary oracle access, rather than resolving the unrelativized hierarchy.

Relation to counting and space complexity

The polynomial hierarchy is contained in PSPACE because a fixed sequence of polynomially bounded quantifiers can be evaluated using polynomial space. This yields

[ \mathrm{PH}\subseteq\mathrm{PSPACE}. ]

A substantially sharper upper bound follows from Toda's theorem. Seinosuke Toda proved that

[ \mathrm{PH}\subseteq\mathrm P^{#\mathrm P}, ]

where #P is the class of functions that count accepting computation paths of nondeterministic polynomial-time machines. The theorem shows that a polynomial-time computation with access to an exact counting oracle can simulate every fixed level of quantifier alternation.

Toda’s theorem does not identify PH with a counting class. Instead, it establishes that counting information can encode the cumulative effect of existential and universal choices throughout the hierarchy. This relationship is one reason that lower bounds for counting problems can have consequences for decision classes defined by alternation.

Structural significance

The polynomial hierarchy provides a graduated framework for studying the consequences of assumptions involving NP, co-NP, circuits, and oracle computation. Its levels distinguish problems according to the depth of interaction between claims and universally quantified challenges, while preserving polynomial bounds on every certificate and verification step.

No unconditional separation is known between distinct finite levels of the hierarchy. In particular, it is unknown whether (\Sigma_2^{\mathrm P}) differs from NP or whether PH differs from PSPACE. The hierarchy nevertheless supplies precise collapse consequences: an equality at a finite level propagates upward, converting a local identification of classes into a global simplification of the hierarchy.