View source for PH (complexity)

{{Short description|Class in computational complexity theory}}
[[Image:Complexity-classes-polynomial.svg|thumb|Inclusions of complexity classes including [[P (complexity)|P]], [[NP (complexity)|NP]], [[co-NP]], [[BPP (complexity)|BPP]], [[P/poly]], [[PH (complexity)|PH]], and [[PSPACE]]]]
In [[computational complexity theory]], the [[complexity class]] '''PH''' is the union of all complexity classes in the [[polynomial hierarchy]]:

:<math>\mathrm{PH} = \bigcup_{k\in\mathbb{N}} \Delta_k^\mathrm{P}</math>

'''PH''' was first defined by [[Larry Stockmeyer]].<ref>{{cite journal | last=Stockmeyer | first=Larry J. | authorlink=Larry J. Stockmeyer | title=The polynomial-time hierarchy | zbl=0353.02024 | journal=[[Theor. Comput. Sci.]] | volume=3 | pages=1–22 | year=1977 | doi=10.1016/0304-3975(76)90061-X | doi-access=free }}</ref> It is a special case of hierarchy of [[Alternating Turing machine#Bounded alternation|bounded alternating Turing machine]]. It is contained in '''P<sup>#P</sup>''' = '''P<sup>PP</sup>''' and [[PSPACE]].

'''PH''' has a simple [[descriptive complexity|logical characterization]]: it is the set of languages expressible by [[second-order logic]].

==Relationship to other classes==

{{see|Polynomial hierarchy#Relationships to other classes}}
{{Unsolved|computer science|{{tmath|1= \mathsf{P} \overset{?}{=} \mathsf{NP} }}}}
{{unsolved|computer science|{{tmath|1= \mathsf{PH} \overset{?}{=} \mathsf{PSPACE} }}}}

'''PH''' contains almost all well-known complexity classes inside '''PSPACE'''; in particular, it contains '''[[P (complexity)|P]]''', '''[[NP (complexity)|NP]]''', and '''[[co-NP]]'''. It even contains probabilistic classes such as '''[[Bounded-error probabilistic polynomial|BPP]]'''<ref>{{Cite journal |last=Lautemann |first=Clemens |date=1983-11-08 |title=BPP and the polynomial hierarchy |url=https://dx.doi.org/10.1016/0020-0190%2883%2990044-3 |journal=Information Processing Letters |language=en |volume=17 |issue=4 |pages=215–217 |doi=10.1016/0020-0190(83)90044-3 |issn=0020-0190}}</ref> (this is the [[Sipser–Lautemann theorem]]) and '''[[RP (complexity)|RP]]'''.  However, there is some evidence that '''[[BQP]]''', the class of problems solvable in polynomial time by a [[quantum computer]], is not contained in '''PH'''.<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|url=https://www.quantamagazine.org/finally-a-problem-that-only-quantum-computers-will-ever-be-able-to-solve-20180621/|title = Finally, a Problem That Only Quantum Computers Will Ever be Able to Solve|date = 21 June 2018}}</ref>

'''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> This may simplify a potential proof of '''P''' ≠ '''NP''', since it is only necessary to separate '''P''' from the more general class '''PH'''.

'''PH''' is a subset of '''P<sup>#P</sup>''' = '''P<sup>PP</sup>''' by [[Toda's theorem]]; the class of problems that are decidable by a polynomial time [[Turing machine]] with access to a [[Sharp P|#P]] or equivalently [[PP (complexity class)|PP]] [[oracle machine|oracle]]), and also in '''[[PSPACE]]'''.

==Examples==

{{See also|Polynomial hierarchy#Problems}}
{{Empty section|date=February 2023}}

==References==
{{reflist}}

==General references==
* {{cite book | last=Bürgisser | first=Peter |authorlink = Peter Bürgisser | title=Completeness and reduction in algebraic complexity theory | zbl=0948.68082 | series=Algorithms and Computation in Mathematics | volume=7 | location=Berlin | publisher=[[Springer-Verlag]] | year=2000 | isbn=3-540-66752-0 | page=66}}
*{{CZoo|PH|P#ph}}

{{ComplexityClasses}}

[[Category:Complexity classes]]


{{comp-sci-theory-stub}}