Jerarquía polinómica
Apariencia
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[editar]
Referencias[editar]
Bibliografía[editar]
- 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.