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ítulo17. Jerarquía polinómica, pp.409–438. Sección 7.2: La Jerarquía Polinómica, pp. 161-167.
Categoría:Complejidad computacional