Mostra la font per a PH (Complexitat)

En [[Complexitat computacional|teoria de la complexitat]], la '''classe de complexitat PH''' és la unió de totes les classes de complexitat dins la jerarquia polinòmica:<blockquote><math>{\mathrm  {PH}}=\bigcup _{{k\in {\mathbb  {N}}}}\Delta _{k}^{{\mathrm  {P}}}</math></blockquote>[[Larry Stockmeyer]] va ser el primer en definir aquesta classe.<ref>{{Ref-publicació|cognom=Stockmeyer|nom=Larry J.|article=The polynomial-time hierarchy|publicació=Theoretical Computer Science|url=https://linkinghub.elsevier.com/retrieve/pii/030439757690061X|volum=3|exemplar=1|data=1976-10|pàgines=1–22|doi=10.1016/0304-3975(76)90061-x|issn=0304-3975}}</ref> És un cas especial de [[màquina de Turing fitada]]. També es pot definir com el conjunt de [[Llenguatge formal|llenguatges expressats]] per [[lògica de segon ordre]].<ref>{{Ref-web|url=https://complexityzoo.uwaterloo.ca/Complexity_Zoo:P#ph|títol=Complexity Zoo:P - Complexity Zoo|consulta=2018-11-30|llengua=en}}</ref>

== Relació amb d'altres classes ==
Està continguda a '''P<sup>#P</sup>''' = '''P<sup>PP</sup>'''  i també dins [[PSPACE]].

PH conté la majoria de classes dins de PSPACE, en particular conté [[P (complexitat)|P]], [[NP (Complexitat)|NP]] i [[Co-NP (Complexitat)|co-NP]]. També conté classes probabilístiques com [[BPP (complexitat)|BPP]] i [[RP (Complexitat)|RP]]. Tot i això, hi ha evidències que la classe [[BQP (complexitat)|BQP]] no està dins de PH.<ref>{{Ref-publicació|cognom=Aaronson|nom=Scott|article=BQP and the polynomial hierarchy|publicació=Proc. 42nd Symposium on Theory of Computing (STOC 2009). Association for Computing Machinery|url=http://dl.acm.org/citation.cfm?id=1806689.1806711|data=2010-06-05|editorial=ACM|pàgines=141–150|doi=10.1145/1806689.1806711}}</ref>

Se sap que P = NP [[si i només si]] P = PH.

== Referències ==
{{referències}}

{{classes de complexitat}}

{{autoritat}}
[[Categoria:Classes de complexitat]]