Editing Polynomial hierarchy

{{Short description|Computer science concept}}
{{no footnotes|date=July 2019}}

In [[computational complexity theory]], the '''polynomial hierarchy''' (sometimes called the '''polynomial-time hierarchy''') is a [[hierarchy (mathematics)|hierarchy]] of [[complexity class]]es that generalize the classes '''[[NP (complexity)|NP]]''' and '''[[co-NP]]'''.<ref>Arora and Barak, 2009, pp.97</ref> Each class in the hierarchy is contained within '''[[PSPACE]]'''. The hierarchy can be defined using [[oracle machine]]s or [[alternating Turing machine]]s. It is a resource-bounded counterpart to the [[arithmetical hierarchy]] and [[analytical hierarchy]] from [[mathematical logic]]. The union of the classes in the hierarchy is denoted '''PH'''.

Classes within the hierarchy have complete problems (with respect to [[polynomial-time reduction]]s) that ask if [[quantified Boolean formula]]e 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.

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

===Oracle definition===
For the oracle definition of the polynomial hierarchy, define

:<math>\Delta_0^\mathrm{P} := \Sigma_0^\mathrm{P} := \Pi_0^\mathrm{P} := \mathrm{P},</math>

where [[P (complexity)|P]] is the set of [[decision problem]]s solvable in [[polynomial time]]. Then for i ≥ 0 define

:<math>\Delta_{i+1}^\mathrm{P} := \mathrm{P}^{\Sigma_i^\mathrm{P}}</math>
:<math>\Sigma_{i+1}^\mathrm{P} := \mathrm{NP}^{\Sigma_i^\mathrm{P}}</math>
:<math>\Pi_{i+1}^\mathrm{P} := \mathrm{coNP}^{\Sigma_i^\mathrm{P}}</math>

where <math>\mathrm{P}^{\rm A}</math> is the set of [[decision problem]]s solvable in polynomial time by a [[Turing machine]] augmented by an [[oracle machine|oracle]] for some complete problem in class A; the classes <math>\mathrm{NP}^{\rm A}</math> and <math>\mathrm{coNP}^{\rm A}</math> are defined analogously.  For example, <math> \Sigma_1^\mathrm{P} = \mathrm{NP}, \Pi_1^\mathrm{P} = \mathrm{coNP} </math>, and <math> \Delta_2^\mathrm{P} = \mathrm{P^{NP}} </math> is the class of problems solvable in polynomial time by a deterministic Turing machine with an oracle for some NP-complete problem.<ref>Completeness in the Polynomial-Time Hierarchy A Compendium, M. Schaefer, C. Umans</ref>

===Quantified Boolean formulae definition ===
For the existential/universal definition of the polynomial hierarchy, let {{mvar|L}} be a [[formal language|language]] (i.e. a [[decision problem]], a subset of {0,1}<sup>*</sup>), let {{mvar|p}} be a [[polynomial]], and define

: <math> \exists^p L := \left\{ x \in \{0,1\}^* \ \left| \ \left( \exists w \in \{0,1\}^{\leq p(|x|)} \right) \langle x,w \rangle \in L \right. \right\}, </math>

where <math>\langle x,w \rangle \in \{0,1\}^*</math> is some standard encoding of the pair of binary strings ''x'' and ''w'' as a single binary string. The language ''L'' represents a set of ordered pairs of strings, where the first string ''x'' is a member of <math>\exists^p L</math>, and the second string ''w'' is a "short" (<math>|w| \leq p(|x|) </math>) witness testifying that ''x'' is a member of <math>\exists^p L</math>. In other words, <math>x \in \exists^p L</math> if and only if there exists a short  witness ''w'' such that <math> \langle x,w \rangle \in L </math>. Similarly, define

: <math> \forall^p L := \left\{ x \in \{0,1\}^* \ \left| \ \left( \forall w \in \{0,1\}^{\leq p(|x|)} \right) \langle x,w \rangle \in L \right. \right\} </math>
Note that [[De Morgan's laws]] hold: <math> \left( \exists^p L \right)^{\rm c} = \forall^p L^{\rm c} </math> and <math> \left( \forall^p L \right)^{\rm c} = \exists^p L^{\rm c} </math>, where ''L''<sup>c</sup> is the complement of ''L''.

Let {{mathcal|C}} be a class of languages. Extend these operators to work on whole classes of languages by the definition

:<math>\exists^\mathrm{P} \mathcal{C} := \left\{\exists^p L \ | \ p \text{ is a polynomial and } L \in \mathcal{C} \right\}</math>
:<math>\forall^\mathrm{P} \mathcal{C} := \left\{\forall^p L \ | \ p \text{ is a polynomial and } L \in \mathcal{C} \right\}</math>

Again, De Morgan's laws hold: <math> \mathrm{co} \exists^\mathrm{P} \mathcal{C} = \forall^\mathrm{P} \mathrm{co} \mathcal{C} </math> and <math> \mathrm{co} \forall^\mathrm{P} \mathcal{C} = \exists^\mathrm{P} \mathrm{co} \mathcal{C} </math>, where <math>\mathrm{co}\mathcal{C} = \left\{ L^c | L \in \mathcal{C} \right\}</math>.

The classes '''[[NP (complexity)|NP]]''' and '''[[co-NP]]''' can be defined as <math> \mathrm{NP} = \exists^\mathrm{P} \mathrm{P} </math>, and <math> \mathrm{coNP} = \forall^\mathrm{P} \mathrm{P} </math>, where '''[[P (complexity)|P]]''' is the class of all feasibly (polynomial-time) decidable languages. The polynomial hierarchy can be defined recursively as

:<math> \Sigma_0^\mathrm{P} := \Pi_0^\mathrm{P} := \mathrm{P} </math>
:<math> \Sigma_{k+1}^\mathrm{P} := \exists^\mathrm{P} \Pi_k^\mathrm{P} </math>
:<math> \Pi_{k+1}^\mathrm{P} := \forall^\mathrm{P} \Sigma_k^\mathrm{P} </math>

Note that <math> \mathrm{NP} = \Sigma_1^\mathrm{P} </math>, and <math> \mathrm{coNP} = \Pi_1^\mathrm{P} </math>.

This definition reflects the close connection between the polynomial hierarchy and the [[arithmetical hierarchy]], where '''[[Decidable language|R]]''' and '''[[Recursively enumerable language|RE]]''' play roles analogous to '''[[P (complexity)|P]]''' and '''[[NP (complexity)|NP]]''', respectively. The [[analytic hierarchy]] is also defined in a similar way to give a hierarchy of subsets of the [[Baire space (set theory)|real number]]s.

===Alternating Turing machines definition===
An [[alternating 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.<ref>Arora and Barak, pp.99–100</ref>

We define <math>\Sigma_k^\mathrm{P}</math> 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 most ''k'' – 1 times between existential and universal states. We define <math>\Pi_k^\mathrm{P}</math> similarly, except that the initial state is a universal state.<ref>Arora and Barak, pp.100</ref>

If we omit the requirement of at most ''k'' – 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 class '''AP''', which is equal to '''[[PSPACE]]'''.<ref>Arora and Barak, pp.100</ref>

==Relations between classes in the polynomial hierarchy==
[[Image:Polynomial time hierarchy.svg|250px|thumb|right|Commutative diagram equivalent to the polynomial time hierarchy. The arrows denote inclusion.]]
The union of all classes in the polynomial hierarchy is the complexity class '''PH'''.

The definitions imply the relations:

:<math>\Sigma_i^\mathrm{P} \subseteq \Delta_{i+1}^\mathrm{P} \subseteq \Sigma_{i+1}^\mathrm{P}</math>
:<math>\Pi_i^\mathrm{P} \subseteq \Delta_{i+1}^\mathrm{P} \subseteq \Pi_{i+1}^\mathrm{P}</math>
:<math>\Sigma_i^\mathrm{P} = \mathrm{co}\Pi_{i}^\mathrm{P}</math>

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 <math>\Sigma_k^\mathrm{P} = \Sigma_{k+1}^\mathrm{P}</math>, or if any <math>\Sigma_k^\mathrm{P} = \Pi_{k}^\mathrm{P}</math>, then the hierarchy ''collapses to level k'': for all <math>i > k</math>, <math>\Sigma_i^\mathrm{P} = \Sigma_k^\mathrm{P}</math>.<ref>Arora and Barak, 2009, Theorem 5.4</ref> In particular, we have the following implications involving unsolved problems:

* [[P versus NP problem|'''P''' = '''NP''']] if and only if '''P''' = '''PH'''.<ref>{{cite book|title=Handbook of Discrete and Combinatorial Mathematics|series=Discrete Mathematics and Its Applications|editor-first=Kenneth H.|editor-last=Rosen|edition=2nd|publisher=CRC Press|year=2018|pages=1308–1314|isbn=9781351644051|chapter=17.5 Complexity classes|first=Lane|last=Hemaspaandra}}</ref>
* If '''NP''' = '''[[co-NP]]''' then '''NP''' = '''PH'''. ('''co-NP''' is <math>\Pi_1^\mathrm{P}</math>.)
The case in which '''NP''' = '''PH''' is also termed as a ''collapse'' of the '''PH''' to ''the second level''. The case '''P''' = '''NP''' corresponds to a collapse of '''PH''' to '''P'''.

{{Unsolved|computer science|{{tmath|1= \mathrm{P} \overset{?}{=} \mathrm{NP} }}}}

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.

== Relationships to other classes ==
{{unsolved|computer science|{{tmath|1= \mathrm{PH} \overset{?}{=} \mathrm{PSPACE} }}}}

[[File:Complexity-classes-polynomial.svg|thumb|[[Hasse diagram]] of complexity classes including [[P (complexity)|P]], [[NP (complexity)|NP]], [[co-NP]], [[BPP (complexity)|BPP]], [[P/poly]], PH, and [[PSPACE]]]]

The polynomial hierarchy is an analogue (at much lower complexity) of the [[exponential hierarchy]] and [[arithmetical hierarchy]].

It is known that PH is contained within [[PSPACE]], but it is not known whether the two classes are equal. One useful reformulation of this problem is that PH = PSPACE if and only if [[SO (complexity)|second-order logic over finite structures]] gains no additional power from the addition of a [[transitive closure]] operator over relations of relations (i.e., over the second-order variables).<ref>{{Cite journal |last1=Ferrarotti |first1=Flavio |last2=Van den Bussche |first2=Jan |last3=Virtema |first3=Jonni |date=2018 |title=Expressivity Within Second-Order Transitive-Closure Logic |journal=DROPS-IDN/V2/Document/10.4230/LIPIcs.CSL.2018.22 |language=en |publisher=Schloss-Dagstuhl - Leibniz Zentrum für Informatik |doi=10.4230/LIPIcs.CSL.2018.22|doi-access=free |s2cid=4903744 }}</ref>

If the polynomial hierarchy has any [[complete problem]]s, then it has only finitely many distinct levels.  Since there are [[PSPACE-complete]] problems, we know that if PSPACE = PH, then the polynomial hierarchy must collapse, since a PSPACE-complete problem would be a <math>\Sigma_{k}^\mathrm{P}</math>-complete problem for some ''k''.<ref>Arora and Barak, 2009, Claim 5.5</ref>

Each class in the polynomial hierarchy contains <math>\leq_{\rm m}^\mathrm{P}</math>-complete problems (problems complete under polynomial-time many-one reductions). Furthermore, each class in the polynomial hierarchy is ''closed under <math>\leq_{\rm m}^\mathrm{P}</math>-reductions'': meaning that for a class {{mathcal|C}} in the hierarchy and a language <math>L \in \mathcal{C}</math>, if <math>A \leq_{\rm m}^\mathrm{P} L</math>, then <math>A \in \mathcal{C}</math> as well. These two facts together imply that if <math>K_i</math> is a complete problem for <math>\Sigma_{i}^\mathrm{P}</math>, then <math>\Sigma_{i+1}^\mathrm{P} = \mathrm{NP}^{K_i}</math>, and <math>\Pi_{i+1}^\mathrm{P} = \mathrm{coNP}^{K_i}</math>. For instance, <math>\Sigma_{2}^\mathrm{P} = \mathrm{NP}^\mathrm{SAT}</math>. In other words, if a language is defined based on some oracle in {{mathcal|C}}, then we can assume that it is defined based on a complete problem for {{mathcal|C}}. Complete problems therefore act as "representatives" of the class for which they are complete.

* [[Sipser–Lautemann theorem]]: <math>\mathrm{BPP} \subset \Sigma_2^\mathrm{P} \cap \Pi_2^\mathrm{P}</math>.
* [[Karp–Lipton theorem|Kannan's theorem]]: <math>\forall k, \Sigma_2 \not\subset \mathrm{SIZE}(n^k) </math>. It is an open question whether <math>\Sigma_2 \not\subset \bigcup_k \mathrm{SIZE}(n^k) = \mathrm{P/poly} </math>.
* [[Toda's theorem]]: <math>\mathrm{PH} \subset \mathrm{P}^{\mathrm{\#P}} </math>.

There is some evidence that [[BQP]], the class of problems solvable in polynomial time by a [[quantum computer]], is not contained in PH; however, it is also believed that PH is not contained in BQP.<ref>{{Cite conference| last = Aaronson| first = Scott| author-link=Scott Aaronson| contribution = BQP and the Polynomial Hierarchy| year= 2009| id={{ECCC|2009|09|104}} | arxiv=0910.4698 | title=[[Symposium on Theory of Computing|Proc. 42nd Symposium on Theory of Computing (STOC 2009)]]|publisher=[[Association for Computing Machinery]]|pages=141–150|doi=10.1145/1806689.1806711}}</ref>=<ref>{{cite web |last1=Hartnett |first1=Kevin |title=Finally, a Problem That Only Quantum Computers Will Ever Be Able to Solve |url=https://www.quantamagazine.org/finally-a-problem-that-only-quantum-computers-will-ever-be-able-to-solve-20180621/ |website=Quanta Magazine |language=en |date=21 June 2018}}</ref>

==Problems==
{{unordered list
|1=
An example of a natural problem in <math>\Sigma_2^\mathrm{P}</math> is ''[[circuit minimization]]'': given a number ''k'' and a circuit ''A'' computing a [[Boolean function]] ''f'', determine if there is a circuit with at most ''k'' gates that computes the same function ''f''. Let {{mathcal|C}} be the set of all boolean circuits. The language

:<math> L = \left\{ \langle A,k,B,x \rangle \in \mathcal{C} \times \mathbb{N} \times \mathcal{C} \times \{0,1\}^*  
\left|
B \text{ has at most } k \text{ gates, and } A(x)=B(x) 
\right.
\right\} </math>

is decidable in polynomial time. The language

:<math> \mathit{CM} = \left\{ \langle A,k \rangle \in \mathcal{C} \times \mathbb{N} 
\left| 
\begin{matrix}
\text{there exists a circuit } B \text{ with at most } k \text{ gates } \\
\text{ such that } A \text{ and } B \text{ compute the same function} 
\end{matrix}
\right.
\right\} </math>

is the circuit minimization language. <math> \mathit{CM} \in \Sigma_2^\mathrm{P} (= \exists^\mathrm{P} \forall^\mathrm{P} \mathrm{P}) </math> because {{mvar|L}} is decidable in polynomial time and because, given <math> \langle A,k \rangle </math>, <math> \langle A,k \rangle \in \mathit{CM}</math> if and only if ''there exists'' a circuit {{mvar|B}} such that ''for all'' inputs {{mvar|x}}, <math> \langle A,k,B,x \rangle \in L </math>.

|2=
A complete problem for <math>\Sigma_k^\mathrm{P}</math> is '''satisfiability for quantified Boolean formulas with ''k'' – 1 alternations of quantifiers''' (abbreviated '''QBF<sub>k</sub>''' or '''QSAT<sub>k</sub>'''). This is the version of the [[boolean satisfiability problem]] for <math>\Sigma_k^\mathrm{P}</math>. In this problem, we are given a Boolean formula ''f'' with variables partitioned into ''k'' sets ''X''<sub>1</sub>, ..., ''X<sub>k</sub>''. We have to determine if it is true that 
:<math> \exists X_1 \forall X_2 \exists X_3 \ldots f</math>
That is, is there an assignment of values to variables in ''X''<sub>1</sub> such that, for all assignments of values in ''X''<sub>2</sub>, there exists an assignment of values to variables in ''X''<sub>3</sub>, ... ''f'' is true?

The variant above is complete for <math>\Sigma_k^\mathrm{P}</math>. The variant in which the first quantifier is "for all", the second is "exists", etc., is complete for <math>\Pi_k^\mathrm{P}</math>. Each language is a subset of the problem obtained by removing the restriction of ''k'' – 1 alternations, the '''PSPACE'''-complete problem [[TQBF]].

|3=
A Garey/Johnson-style list of problems known to be complete for the second
and higher levels of the polynomial hierarchy can be found in [http://ovid.cs.depaul.edu/documents/phcom.pdf this Compendium].

}}

== See also ==
* [[EXPTIME]]
* [[Exponential hierarchy]]
* [[Arithmetic hierarchy]]

==References==

===General references===
# {{cite book |last1= Arora |first1= Sanjeev |last2= Barak |first2= Boaz |url= http://www.cs.princeton.edu/theory/complexity/ |title= Complexity Theory: A Modern Approach |publisher= Cambridge University Press |date= 2009 |isbn= 978-0-521-42426-4 |quote= section 1.4, "Machines as strings and the universal Turing machine" and 1.7, "Proof of theorem 1.9" }}
# [[Albert R. Meyer|A. R. Meyer]] and [[Larry Stockmeyer|L. J. Stockmeyer]].  The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space.  ''In Proceedings of the 13th IEEE [[Symposium on Switching and Automata Theory]]'', pp.&nbsp;125&ndash;129, 1972.  The paper that introduced the polynomial hierarchy.
# [[Larry Stockmeyer|L. J. Stockmeyer]]. [[:doi:10.1016/0304-3975(76)90061-X|The polynomial-time hierarchy]]. ''Theoretical Computer Science'', vol.3, pp.&nbsp;1&ndash;22, 1976.
# [[Christos Papadimitriou|C. Papadimitriou]]. Computational Complexity. Addison-Wesley, 1994. Chapter 17. ''Polynomial hierarchy'', pp.&nbsp;409&ndash;438.
# {{cite book|author = [[Michael R. Garey]] and [[David S. Johnson]] | year = 1979 | title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]] | publisher = W.H. Freeman | isbn = 0-7167-1045-5}} Section 7.2: The Polynomial Hierarchy, pp.&nbsp;161–167.

===Citations===
{{reflist}}

{{ComplexityClasses}}

[[Category:Mathematical logic hierarchies]]
[[Category:Complexity classes]]