Editing Polynomial hierarchy (section)

== 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>