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

• EXPTIME
• Jerarquía aritmética

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