Does the polynomial hierarchy collapse? (Is the polynomial-time hierarchy infinite?)

The polynomial-time hierarchy PH, introduced by Stockmeyer in 1976, stratifies decision problems by the number of alternating existential and universal polynomially bounded quantifiers applied to polynomial-time predicates. Whether PH collapses to some finite level (some level coinciding with the next, which forces the entire hierarchy to that level) or is strictly infinite at every level is a central open problem of computational complexity theory, and the non-collapse direction subsumes P versus NP.

Background

A central goal of computational complexity theory is to classify decision problems — languages, i.e. sets of finite binary strings — by the computational resources needed to decide them. P is the class of languages decidable by a deterministic Turing machine in polynomial time, and NP is the class of languages whose members have polynomially long certificates checkable in polynomial time. The polynomial-time hierarchy (PH), introduced by Larry Stockmeyer in 1976, refines this picture by allowing a fixed number of alternating existential and universal quantifiers over polynomially bounded strings applied to a polynomial-time predicate. Formally, $\Sigma_0^P=P$, and $\Sigma_{k+1}^P$ consists of the languages definable by an existential block of polynomially bounded string quantifiers in front of a $\Pi_k^P$ predicate, where $\Pi_k^P$ is the complementary class obtained from universal quantifiers; equivalently, $\Sigma_{k+1}^P$ is what a nondeterministic polynomial-time oracle Turing machine — a Turing machine that may write query strings on a special tape and receive yes/no answers from a fixed oracle set — can decide when equipped with an oracle for a $\Sigma_k^P$ language. The hierarchy is $\mathrm{PH}=\bigcup_{k\ge0}\Sigma_k^P$, with $\Sigma_1^P=\mathrm{NP}$ and $\Pi_1^P=$ co-NP. This construction parallels the arithmetical hierarchy of computability theory, which uses unbounded quantifiers over the integers; that hierarchy is provably strict, and PH inherits its shape but with polynomial length bounds — which is exactly why its strictness is far harder to establish.

PH is contained in PSPACE (the class decidable using polynomial memory), and a standard argument shows that if $\Sigma_k^P=\Sigma_{k+1}^P$ for some $k$, then the entire hierarchy equals $\Sigma_k^P$; for this reason, asking whether PH collapses means precisely: is there a finite $k$ with $\Sigma_k^P=\Sigma_{k+1}^P$? The question interacts tightly with P versus NP: $\mathrm{P}=\mathrm{NP}$ forces $\mathrm{PH}=\mathrm{P}$ (collapse at the base level), so proving the hierarchy infinite would in particular prove $\mathrm{P}\ne\mathrm{NP}$. The levels of PH capture the cost of bounded quantifier alternation in polynomial-time computation, making its structure a benchmark for the power of alternation itself.

Three lines of work frame what is known. First, conditional collapse theorems: Karp and Lipton (1980) proved that if every NP problem has polynomial-size Boolean circuit families — the inclusion $\mathrm{NP}\subseteq\mathrm{P/poly}$, where P/poly denotes the languages decidable by polynomial-size nonuniform circuit families, equivalently with polynomial-length advice — then PH collapses to $\Sigma_2^P$; Yap (1983) proved that $\Sigma_k^P=\Pi_k^P$ for some $k$ implies $\mathrm{PH}\subseteq\Sigma_{k+1}^P$. These results show that plausible hypotheses force dramatic collapses, yet no unconditional collapse or separation is known. Second, oracle (relativization) barriers: Baker, Gill, and Solovay (1975) constructed competing oracles relative to which the P vs NP question resolves differently, and the same phenomenon confronts PH directly — relative to a PSPACE-complete oracle $A$, one has $\mathrm{PH}^A=P^A$ (full collapse), while Cai (1989) proved that with probability one a random oracle $A$ separates $\mathrm{PSPACE}^A$ from $\mathrm{PH}^A$. Consequently, no relativizing proof can settle the unrelativized question. Third, Aaronson and Wigderson (2009) showed that arithmetization — the technique behind most known non-relativizing results, formalized as the algebrization barrier — is likewise too weak for such separations.

Problem Statement

Determine, unconditionally and in full generality, whether the polynomial-time hierarchy collapses. Here $\Sigma_k^P$ denotes the $k$-th level of the polynomial-time hierarchy PH — the class of languages definable by $k$ alternating blocks of polynomially bounded existential and universal string quantifiers applied to a polynomial-time predicate, with $\Sigma_0^P=\mathrm{P}$ and $\Sigma_1^P=\mathrm{NP}$ — and $\mathrm{PH}=\bigcup_{k\ge0}\Sigma_k^P$. Prove either that $\Sigma_k^P\ne\Sigma_{k+1}^P$ for every $k\ge1$ — equivalently, that PH is infinite (strict at every level) — or that $\Sigma_k^P=\Sigma_{k+1}^P$ for some $k\ge0$ — equivalently, that PH collapses to $\Sigma_k^P$, where the $k=0$ case is exactly $\mathrm{P}=\mathrm{NP}$. The answer must be unrelativized (no oracle) and unconditional (no hypothesis such as $\mathrm{NP}\subseteq\mathrm{P/poly}$, i.e. every NP problem having polynomial-size circuit families); a relativized, promised, or average-case variant does not resolve the problem. A separation at one fixed level alone does not establish strictness at every level, whereas a collapse equality $\Sigma_k^P=\Sigma_{k+1}^P$ at any single level resolves the entire question, by the standard propagation argument recalled in the Background.

References

1. Larry J. Stockmeyer, "The polynomial-time hierarchy", Theoretical Computer Science (1976), doi:10.1016/0304-3975(76)90061-X, https://doi.org/10.1016/0304-3975(76)90061-X
2. Theodore Baker, John Gill, Robert Solovay, "Relativizations of the P=?NP Question", SIAM Journal on Computing (1975), doi:10.1137/0204037, https://doi.org/10.1137/0204037
3. Richard M. Karp, Richard J. Lipton, "Some connections between nonuniform and uniform complexity classes", Proceedings of the twelfth annual ACM symposium on Theory of computing (STOC '80) (1980), doi:10.1145/800141.804678, https://doi.org/10.1145/800141.804678
4. Chee K. Yap, "Some consequences of non-uniform conditions on uniform classes", Theoretical Computer Science (1983), doi:10.1016/0304-3975(83)90020-8, https://doi.org/10.1016/0304-3975(83)90020-8
5. Jin-Yi Cai, "With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy", Journal of Computer and System Sciences (1989), doi:10.1016/0022-0000(89)90033-0, https://doi.org/10.1016/0022-0000(89)90033-0
6. Scott Aaronson, Avi Wigderson, "Algebrization: a new barrier in complexity theory", ACM Transactions on Computation Theory (2009), doi:10.1145/1490270.1490272, https://doi.org/10.1145/1490270.1490272