This article includes alist of references,related reading, orexternal links,but its sources remain unclear because it lacksinline citations. Please helpimprove this article byintroducing more precise citations.(July 2019) (Learn how and when to remove this message)

Incomputational complexity theory, thepolynomial hierarchy (sometimes called thepolynomial-time hierarchy) is ahierarchy ofcomplexity classes that generalize the classesNP andco-NP.^[1] Each class in the hierarchy is contained withinPSPACE. The hierarchy can be defined usingoracle machines oralternating Turing machines. It is a resource-bounded counterpart to thearithmetical hierarchy andanalytical hierarchy frommathematical logic. The union of the classes in the hierarchy is denotedPH.

Classes within the hierarchy have complete problems (with respect topolynomial-time reductions) that ask ifquantified Boolean formulae hold, for formulae with restrictions on the quantifier order. It is known that equality between classes on the same level or consecutive levels in the hierarchy would imply a "collapse" of the hierarchy to that level.

There are multiple equivalent definitions of the classes of the polynomial hierarchy.

For the oracle definition of the polynomial hierarchy, define

${\displaystyle {\mathrm{\Delta }}_0^{\mathsf{P}}:={\mathrm{\Sigma }}_0^{\mathsf{P}}:={\mathrm{\Pi }}_0^{\mathsf{P}}:=\mathsf{P},}$

whereP is the set ofdecision problems solvable inpolynomial time. Then for i ≥ 0 define

${\displaystyle {\mathrm{\Delta }}_{i+1}^{\mathsf{P}}:={\mathsf{P}}^{{\mathrm{\Sigma }}_i^{\mathsf{P}}}}$

${\displaystyle {\mathrm{\Sigma }}_{i+1}^{\mathsf{P}}:={\mathsf{N}\mathsf{P}}^{{\mathrm{\Sigma }}_i^{\mathsf{P}}}}$

${\displaystyle {\mathrm{\Pi }}_{i+1}^{\mathsf{P}}:={\mathsf{c}\mathsf{o}\mathsf{N}\mathsf{P}}^{{\mathrm{\Sigma }}_i^{\mathsf{P}}}}$

where${\displaystyle {\mathsf{P}}^{\mathrm{A}}}$ is the set ofdecision problems solvable in polynomial time by aTuring machine augmented by anoracle for some complete problem in class A; the classes${\displaystyle {\mathsf{N}\mathsf{P}}^{\mathrm{A}}}$ and${\displaystyle {\mathsf{c}\mathsf{o}\mathsf{N}\mathsf{P}}^{\mathrm{A}}}$ are defined analogously. For example,${\displaystyle {\mathrm{\Sigma }}_1^{\mathsf{P}}=\mathsf{N}\mathsf{P},{\mathrm{\Pi }}_1^{\mathsf{P}}=\mathsf{c}\mathsf{o}\mathsf{N}\mathsf{P}}$, and${\displaystyle {\mathrm{\Delta }}_2^{\mathsf{P}}={\mathsf{P}}^{\mathsf{N}\mathsf{P}}}$ is the class of problems solvable in polynomial time by a deterministic Turing machine with an oracle for some NP-complete problem.^[2]

For the existential/universal definition of the polynomial hierarchy, letL be alanguage (i.e. adecision problem, a subset of {0,1}^*), letp be apolynomial, and define

${\displaystyle {\mathrm{\exists }}^{p}L:=\left\{x\in \{0,1{\}}^{\ast }|\left(\mathrm{\exists }w\in \{0,1{\}}^{\le p(|x|)}\right)⟨x,w⟩\in L\right\},}$

where${\displaystyle ⟨x,w⟩\in \{0,1{\}}^{\ast }}$ is some standard encoding of the pair of binary stringsx andw as a single binary string. The languageL represents a set of ordered pairs of strings, where the first stringx is a member of${\displaystyle {\mathrm{\exists }}^{p}L}$, and the second stringw is a "short" (${\displaystyle |w|\le p(|x|)}$) witness testifying thatx is a member of${\displaystyle {\mathrm{\exists }}^{p}L}$. In other words,${\displaystyle x\in {\mathrm{\exists }}^{p}L}$ if and only if there exists a short witnessw such that${\displaystyle ⟨x,w⟩\in L}$. Similarly, define

${\displaystyle {\mathrm{\forall }}^{p}L:=\left\{x\in \{0,1{\}}^{\ast }|\left(\mathrm{\forall }w\in \{0,1{\}}^{\le p(|x|)}\right)⟨x,w⟩\in L\right\}}$

Note thatDe Morgan's laws hold:${\displaystyle {\left({\mathrm{\exists }}^{p}L\right)}^{\mathrm{c}}={\mathrm{\forall }}^p{L}^{\mathrm{c}}}$ and${\displaystyle {\left({\mathrm{\forall }}^{p}L\right)}^{\mathrm{c}}={\mathrm{\exists }}^p{L}^{\mathrm{c}}}$, whereL^c is the complement ofL.

LetC be a class of languages. Extend these operators to work on whole classes of languages by the definition

${\displaystyle {\mathrm{\exists }}^{\mathsf{P}}\mathcal{C}:=\left\{{\mathrm{\exists }}^{p}L|p\text{ is a polynomial and }L\in \mathcal{C}\right\}}$

${\displaystyle {\mathrm{\forall }}^{\mathsf{P}}\mathcal{C}:=\left\{{\mathrm{\forall }}^{p}L|p\text{ is a polynomial and }L\in \mathcal{C}\right\}}$

Again, De Morgan's laws hold:${\displaystyle \mathsf{c}\mathsf{o}{\mathrm{\exists }}^{\mathsf{P}}\mathcal{C}={\mathrm{\forall }}^{\mathsf{P}}\mathsf{c}\mathsf{o}\mathcal{C}}$ and${\displaystyle \mathsf{c}\mathsf{o}{\mathrm{\forall }}^{\mathsf{P}}\mathcal{C}={\mathrm{\exists }}^{\mathsf{P}}\mathsf{c}\mathsf{o}\mathcal{C}}$, where${\displaystyle \mathsf{c}\mathsf{o}\mathcal{C}=\left\{L^c|L\in \mathcal{C}\right\}}$.

The classesNP andco-NP can be defined as${\displaystyle \mathsf{N}\mathsf{P}={\mathrm{\exists }}^{\mathsf{P}}\mathsf{P}}$, and${\displaystyle \mathsf{c}\mathsf{o}\mathsf{N}\mathsf{P}={\mathrm{\forall }}^{\mathsf{P}}\mathsf{P}}$, whereP is the class of all feasibly (polynomial-time) decidable languages. The polynomial hierarchy can be defined recursively as

${\displaystyle {\mathrm{\Sigma }}_0^{\mathsf{P}}:={\mathrm{\Pi }}_0^{\mathsf{P}}:=\mathsf{P}}$

${\displaystyle {\mathrm{\Sigma }}_{k+1}^{\mathsf{P}}:={\mathrm{\exists }}^{\mathsf{P}}{\mathrm{\Pi }}_k^{\mathsf{P}}}$

${\displaystyle {\mathrm{\Pi }}_{k+1}^{\mathsf{P}}:={\mathrm{\forall }}^{\mathsf{P}}{\mathrm{\Sigma }}_k^{\mathsf{P}}}$

Note that${\displaystyle \mathsf{N}\mathsf{P}={\mathrm{\Sigma }}_1^{\mathsf{P}}}$, and${\displaystyle \mathsf{c}\mathsf{o}\mathsf{N}\mathsf{P}={\mathrm{\Pi }}_1^{\mathsf{P}}}$.

This definition reflects the close connection between the polynomial hierarchy and thearithmetical hierarchy, whereR andRE play roles analogous toP andNP, respectively. Theanalytic hierarchy is also defined in a similar way to give a hierarchy of subsets of thereal numbers.

Analternating Turing machine is a non-deterministic Turing machine with non-final states partitioned into existential and universal states. It is eventually accepting from its current configuration if: it is in an existential state and can transition into some eventually accepting configuration; or, it is in a universal state and every transition is into some eventually accepting configuration; or, it is in an accepting state.^[3]

We define${\displaystyle {\mathrm{\Sigma }}_k^{\mathsf{P}}}$ to be the class of languages accepted by an alternating Turing machine in polynomial time such that the initial state is an existential state and every path the machine can take swaps at mostk – 1 times between existential and universal states. We define${\displaystyle {\mathrm{\Pi }}_k^{\mathsf{P}}}$ similarly, except that the initial state is a universal state.^[4]

If we omit the requirement of at mostk – 1 swaps between the existential and universal states, so that we only require that our alternating Turing machine runs in polynomial time, then we have the definition of the classAP, which is equal toPSPACE.^[5]

The union of all classes in the polynomial hierarchy is the complexity classPH.

The definitions imply the relations:

${\displaystyle {\mathrm{\Sigma }}_i^{\mathsf{P}}\subseteq {\mathrm{\Delta }}_{i+1}^{\mathsf{P}}\subseteq {\mathrm{\Sigma }}_{i+1}^{\mathsf{P}}}$

${\displaystyle {\mathrm{\Pi }}_i^{\mathsf{P}}\subseteq {\mathrm{\Delta }}_{i+1}^{\mathsf{P}}\subseteq {\mathrm{\Pi }}_{i+1}^{\mathsf{P}}}$

${\displaystyle {\mathrm{\Sigma }}_i^{\mathsf{P}}=\mathsf{c}\mathsf{o}{\mathrm{\Pi }}_i^{\mathsf{P}}}$

Unlike the arithmetic and analytic hierarchies, whose inclusions are known to be proper, it is an open question whether any of these inclusions are proper, though it is widely believed that they all are. If any${\displaystyle {\mathrm{\Sigma }}_k^{\mathsf{P}}={\mathrm{\Sigma }}_{k+1}^{\mathsf{P}}}$, or if any${\displaystyle {\mathrm{\Sigma }}_k^{\mathsf{P}}={\mathrm{\Pi }}_k^{\mathsf{P}}}$, then the hierarchycollapses to level k: for all${\displaystyle i>k}$,${\displaystyle {\mathrm{\Sigma }}_i^{\mathsf{P}}={\mathrm{\Sigma }}_k^{\mathsf{P}}}$.^[6] In particular, we have the following implications involving unsolved problems:

• P =NP if and only ifP =PH.^[7]
• IfNP =co-NP thenNP =PH. (co-NP is${\displaystyle {\mathrm{\Pi }}_1^{\mathsf{P}}}$.)

The case in whichNP =PH is also termed as acollapse of thePH tothe second level. The caseP =NP corresponds to a collapse ofPH toP.

Unsolved problem in computer science:

⁠${\displaystyle \mathsf{P}\stackrel{?}{=}\mathsf{N}\mathsf{P}}$⁠

(more unsolved problems in computer science)

The question of collapse to the first level is generally thought to be extremely difficult. Most researchers do not believe in a collapse, even to the second level.

Unsolved problem in computer science:

⁠${\displaystyle \mathsf{P}\mathsf{H}\stackrel{?}{=}\mathsf{P}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}}$⁠

(more unsolved problems in computer science)

The polynomial hierarchy is an analogue (at much lower complexity) of theexponential hierarchy andarithmetical hierarchy.

It is known that PH is contained withinPSPACE, but it is not known whether the two classes are equal. One useful reformulation of this problem is that PH = PSPACE if and only ifsecond-order logic over finite structures gains no additional power from the addition of atransitive closure operator over relations of relations (i.e., over the second-order variables).^[8]

If the polynomial hierarchy has anycomplete problems, then it has only finitely many distinct levels. Since there arePSPACE-complete problems, we know that if PSPACE = PH, then the polynomial hierarchy must collapse, since a PSPACE-complete problem would be a${\displaystyle {\mathrm{\Sigma }}_k^{\mathsf{P}}}$-complete problem for somek.^[9]

Each class in the polynomial hierarchy contains${\displaystyle {\le }_{\mathrm{m}}^{\mathsf{P}}}$-complete problems (problems complete under polynomial-time many-one reductions). Furthermore, each class in the polynomial hierarchy isclosed under${\displaystyle {\le }_{\mathrm{m}}^{\mathsf{P}}}$-reductions: meaning that for a classC in the hierarchy and a language${\displaystyle L\in \mathcal{C}}$, if${\displaystyle A{\le }_{\mathrm{m}}^{\mathsf{P}}L}$, then${\displaystyle A\in \mathcal{C}}$ as well. These two facts together imply that if${\displaystyle K_i}$ is a complete problem for${\displaystyle {\mathrm{\Sigma }}_i^{\mathsf{P}}}$, then${\displaystyle {\mathrm{\Sigma }}_{i+1}^{\mathsf{P}}={\mathsf{N}\mathsf{P}}^{K_i}}$, and${\displaystyle {\mathrm{\Pi }}_{i+1}^{\mathsf{P}}={\mathsf{c}\mathsf{o}\mathsf{N}\mathsf{P}}^{K_i}}$. For instance,${\displaystyle {\mathrm{\Sigma }}_2^{\mathsf{P}}={\mathsf{N}\mathsf{P}}^{\mathsf{S}\mathsf{A}\mathsf{T}}}$. In other words, if a language is defined based on some oracle inC, then we can assume that it is defined based on a complete problem forC. Complete problems therefore act as "representatives" of the class for which they are complete.

• Sipser–Lautemann theorem:${\displaystyle \mathsf{B}\mathsf{P}\mathsf{P}\subset {\mathrm{\Sigma }}_2^{\mathsf{P}}\cap {\mathrm{\Pi }}_2^{\mathsf{P}}}$.
• Kannan's theorem:${\displaystyle \mathrm{\forall }k,{\mathrm{\Sigma }}_2\not\subset \mathsf{S}\mathsf{I}\mathsf{Z}\mathsf{E}(n^k)}$. It is an open question whether${\displaystyle {\mathrm{\Sigma }}_2\not\subset \bigcup _k\mathsf{S}\mathsf{I}\mathsf{Z}\mathsf{E}(n^k)=\mathsf{P}\mathsf{/}\mathsf{p}\mathsf{o}\mathsf{l}\mathsf{y}}$.
• Toda's theorem:${\displaystyle \mathsf{P}\mathsf{H}\subset {\mathsf{P}}^{\mathsf{\#}\mathsf{P}}}$.

There is some evidence thatBQP, the class of problems solvable in polynomial time by aquantum computer, is not contained in PH; however, it is also believed that PH is not contained in BQP.^[10]=^[11]

• EXPTIME
• Exponential hierarchy
• Arithmetic hierarchy

1. Arora, Sanjeev; Barak, Boaz (2009).Complexity Theory: A Modern Approach. Cambridge University Press.ISBN 978-0-521-42426-4.section 1.4, "Machines as strings and the universal Turing machine" and 1.7, "Proof of theorem 1.9"
2. A. R. Meyer andL. J. Stockmeyer. The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space.In Proceedings of the 13th IEEESymposium on Switching and Automata Theory, pp. 125–129, 1972. The paper that introduced the polynomial hierarchy.
3. L. J. Stockmeyer.The polynomial-time hierarchy.Theoretical Computer Science, vol.3, pp. 1–22, 1976.
4. C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Chapter 17.Polynomial hierarchy, pp. 409–438.
5. Michael R. Garey andDavid S. Johnson (1979).Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman.ISBN 0-7167-1045-5. Section 7.2: The Polynomial Hierarchy, pp. 161–167.

• Mathematical logic hierarchies
• Complexity classes

• Articles with short description
• Short description is different from Wikidata
• Articles lacking in-text citations from July 2019
• All articles lacking in-text citations