PH (Complexitat)

De Viquipèdia
Salta a la navegació Salta a la cerca

En teoria de la complexitat, la classe de complexitat PH és la unió de totes les classes de complexitat dins la jerarquia polinòmica:

Larry Stockmeyer va ser el primer en definir aquesta classe.[1] És un cas especial de màquina de Turing fitada. També es pot definir com el conjunt de llenguatges expressats per lògica de segon ordre.[2]

Relació amb d'altres classes[modifica]

Està continguda a P#P = PPP i també dins PSPACE.

PH conté la majoria de classes dins de PSPACE, en particular conté P, NP i co-NP. També conté classes probabilístiques com BPP i RP. Tot i això, hi ha evidències que la classe BQP no està dins de PH.[3]

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

Referències[modifica]

  1. Stockmeyer, Larry J. «The polynomial-time hierarchy». Theoretical Computer Science, 3, 1, 1976-10, pàg. 1–22. DOI: 10.1016/0304-3975(76)90061-x. ISSN: 0304-3975.
  2. «Complexity Zoo:P - Complexity Zoo» (en anglès). Arxivat de l'original el 2018-01-19. [Consulta: 30 novembre 2018].
  3. Aaronson, Scott «BQP and the polynomial hierarchy». Proc. 42nd Symposium on Theory of Computing (STOC 2009). Association for Computing Machinery. ACM, 05-06-2010, pàg. 141–150. DOI: 10.1145/1806689.1806711.