Jerarquía polinómica
From Wikipedia, the free encyclopedia
En teoría de complejidad computacional, la jerarquía polinómica (a veces llamada jerarquía de tiempo polinómico) es una jerarquía de clases de complejidad que generaliza las clases P, NP y co-NP a máquinas de oráculo.
Es una contrapartida de recurso-acotado a la jerarquía aritmética y jerarquía analítica de la lógica matemática.
Véase también
Referencias
Bibliografía
- Un. R. Meyer y L. J. Stockmeyer. El Problema de Equivalencia para Expresiones Regulares con Cuadrar Requiere Espacio Exponencial. En Proceedings del 13.º Simposio de IEEE encima Cambiando y Automata Teoría, pp. 125–129, 1972. El papel que introdujo la jerarquía polinómica.
- L. J. Stockmeyer. La jerarquía de tiempo polinómico. Informática teórica, vol. 3, pp. 1–22, 1976.
- C. Papadimitriou. Complejidad computacional. Addison-Wesley, 1994. Capítulo 17. Jerarquía polinómica, pp. 409–438.
- Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. Sección 7.2: La Jerarquía Polinómica, pp. 161-167.
Datos: Q2103021
