Jerarquía polinómica
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.
| Control de autoridades |
|
|---|
Datos: Q2103021
Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.