En la teoría de la complejidad computacional , la clase de complejidad PH es la unión de todas las clases de complejidad en la jerarquía polinomial :
El PH fue definido por primera vez por Larry Stockmeyer . [1] Es un caso especial de jerarquía de máquina de Turing alterna acotada . Está contenido en P #P = P PP (por el teorema de Toda ; la clase de problemas que son decidibles por una máquina de Turing de tiempo polinomial con acceso a un oráculo #P o equivalentemente PP ), y también en PSPACE .
PH tiene una caracterización lógica simple : es el conjunto de lenguajes expresables por lógica de segundo orden .
PH contiene casi todas las clases de complejidad conocidas dentro de PSPACE ; en particular, contiene P , NP y co-NP . Incluso contiene clases probabilísticas como BPP y RP . Sin embargo, existe alguna evidencia de que BQP , la clase de problemas que una computadora cuántica puede resolver en tiempo polinomial , no está contenida en PH . [2] [3]
P = NP si y solo si P = PH . [4] Esto puede simplificar una prueba potencial de P ≠ NP , ya que solo es necesario separar P de la clase PH más general .
Referencias
- ^ Stockmeyer, Larry J. (1977). "La jerarquía polinomial-temporal". Theor. Computación. Sci . 3 : 1–22. doi : 10.1016 / 0304-3975 (76) 90061-X . Zbl 0353.02024 .
- ^ Aaronson, Scott (2009). "BQP y la jerarquía polinomial". Proc. 42º Simposio de Teoría de la Computación (STOC 2009) . Asociación de Maquinaria Informática . págs. 141–150. arXiv : 0910.4698 . doi : 10.1145 / 1806689.1806711 . ECCC TR09-104 .
- ^ https://www.quantamagazine.org/finally-a-problem-that-only-quantum-computers-will-ever-be-able-to-solve-20180621/
- ^ Hemaspaandra, Lane (2018). "17.5 Clases de complejidad". En Rosen, Kenneth H. (ed.). Manual de Matemática Discreta y Combinatoria . Matemáticas discretas y sus aplicaciones (2ª ed.). Prensa CRC. págs. 1308-1314. ISBN 9781351644051.
Referencias generales
- Bürgisser, Peter (2000). Completitud y reducción en la teoría de la complejidad algebraica . Algoritmos y Computación en Matemáticas. 7 . Berlín: Springer-Verlag . pag. 66. ISBN 3-540-66752-0. Zbl 0948.68082 .
- Complejidad Zoo : PH