PH (complexidade)
Na teoria da complexidade computacional, a classe de complexidade de PH é a união de todas as classes de complexidade na hierarquia polinomial:
O PH foi primeiramente definido por Larry Stockmeyer.[1] é um caso especial de hierarquia de limitado alternando máquina de Turing. Ele está contido em P#P = PPP (por Toda teorema; a classe de problemas que são decidível por um tempo polinomial máquina de Turing com acesso a um #P ou equivalentemente PP oracle), e também em PSPACE.
O PH tem uma simples lógica de caracterização: é o conjunto de idiomas que podem ser expressadas através de segunda ordem lógica.
PH contém quase todas as classes conhecidas de complexidade dentro de PSPACE; em particular, contém P, NPe co-NP. Ele ainda contém classes probabilística como BPP e RP. No entanto, há algumas evidências de que BQP, a classe de problemas resolvidos em tempo polinomial por um computador quântico, não está contido no PH.[2]
P = NP se e somente se P = PH. Isso pode simplificar a um potencial de prova de P ≠ NP, pois só é necessário separar a P a partir do mais geral da classe de PH.
Referências[editar | editar código-fonte]
- ↑ Stockmeyer, Larry J. (1977). «The polynomial-time hierarchy». Theor. Comput. Sci. 3: 1–22. Zbl 0353.02024. doi:10.1016/0304-3975(76)90061-X
- ↑ Aaronson, Scott (2009). «BQP and the Polynomial Hierarchy». Proc. 42nd Symposium on Theory of Computing (STOC 2009). Association for Computing Machinery. pp. 141–150. arXiv:0910.4698
. doi:10.1145/1806689.1806711. Predefinição:ECCC
Referências gerais[editar | editar código-fonte]
- Bürgisser, Peter (2000). Completeness and reduction in algebraic complexity theory. Col: Algorithms and Computation in Mathematics. 7. Berlin: Springer-Verlag. p. 66. ISBN 3-540-66752-0. Zbl 0948.68082
- A complexidade do Zoo: PH