En la teoría de la complejidad computacional , la jerarquía polinomial (a veces llamada jerarquía polinomial-temporal ) es una jerarquía de clases de complejidad que generalizan las clases NP y co-NP . [1] Cada clase de la jerarquía está incluida en PSPACE . La jerarquía se puede definir utilizando máquinas oráculo o alternando máquinas de Turing . Es una contraparte limitada por recursos a la jerarquía aritmética y la jerarquía analítica de la lógica matemática.. La unión de las clases en la jerarquía se denomina PH .
Las clases dentro de la jerarquía tienen problemas completos (con respecto a las reducciones de tiempo polinomial ) que preguntan si se cumplen las fórmulas booleanas cuantificadas , para fórmulas con restricciones en el orden del cuantificador. Se sabe que la igualdad entre clases en el mismo nivel o niveles consecutivos en la jerarquía implicaría un "colapso" de la jerarquía a ese nivel.
Definiciones
Existen múltiples definiciones equivalentes de las clases de la jerarquía polinómica.
Definición de Oracle
Para la definición de oráculo de la jerarquía polinomial, defina
donde P es el conjunto de problemas de decisión que se pueden resolver en tiempo polinomial . Entonces para i ≥ 0 defina
dónde es el conjunto de problemas de decisión que se pueden resolver en tiempo polinomial por una máquina de Turing aumentada por un oráculo para algún problema completo de la clase A; las clases y se definen de forma análoga. Por ejemplo,, y es la clase de problemas que se pueden resolver en tiempo polinomial con un oráculo para algún problema NP-completo. [2]
Definición de fórmulas booleanas cuantificadas
Para la definición existencial / universal de la jerarquía polinomial, sea L un lenguaje (es decir, un problema de decisión , un subconjunto de {0,1} * ), sea p un polinomio y defina
dónde es algún estándar de codificación de la pareja de cadenas binarias x y w como una sola cadena binaria. L representa un conjunto de pares ordenados de cadenas, donde la primera cadena x es miembro de, y la segunda cadena w es un "corto" () testigo testificando que x es miembro de. En otras palabras,si y solo si existe un breve testimonio w tal que. Del mismo modo, defina
Tenga en cuenta que las leyes de De Morgan se mantienen: y , Donde L c es el complemento de L .
Sea C una clase de lenguajes. Extienda estos operadores para que funcionen en clases completas de lenguajes según la definición
Una vez más, las leyes de De Morgan sostienen: y , dónde .
Las clases NP y co-NP se pueden definir como, y , donde P es la clase de todos los lenguajes decidibles (en tiempo polinómico) factibles. La jerarquía polinomial se puede definir de forma recursiva como
Tenga en cuenta que , y .
Esta definición refleja la estrecha conexión entre la jerarquía polinomial y la jerarquía aritmética , donde R y RE juegan roles análogos a P y NP , respectivamente. La jerarquía analítica también se define de manera similar para dar una jerarquía de subconjuntos de los números reales.
Definición de máquinas de Turing alternas
Una máquina de Turing alternante es una máquina de Turing no determinista con estados no finales divididos en estados existenciales y universales. Eventualmente está aceptando de su configuración actual si: está en un estado existencial y puede pasar a alguna configuración de aceptación eventual; o, está en un estado universal y cada transición es hacia alguna configuración eventualmente aceptada; o está en un estado de aceptación. [3]
Definimos ser la clase de lenguajes aceptados por una máquina de Turing alternante en tiempo polinomial, de modo que el estado inicial es un estado existencial y cada camino que la máquina puede tomar cambia como máximo k - 1 veces entre estados existenciales y universales. Definimosde manera similar, excepto que el estado inicial es un estado universal. [4]
Si omitimos el requisito de como máximo k - 1 intercambios entre los estados existenciales y universales, de modo que solo requiramos que nuestra máquina de Turing alterna se ejecute en tiempo polinomial, entonces tenemos la definición de la clase AP , que es igual a PSPACE . [5]
Relaciones entre clases en la jerarquía polinomial
La unión de todas las clases en la jerarquía polinómica es la clase de complejidad PH .
Las definiciones implican las relaciones:
A diferencia de las jerarquías aritméticas y analíticas, cuyas inclusiones se sabe que son adecuadas, es una cuestión abierta si alguna de estas inclusiones es adecuada, aunque se cree ampliamente que todas lo son. Si alguna, o si alguno , entonces la jerarquía colapsa al nivel k : para todos, . [6] En particular, tenemos las siguientes implicaciones que involucran problemas no resueltos:
Relaciones con otras clases
La jerarquía polinomial es una analogía (con una complejidad mucho menor) de la jerarquía exponencial y la jerarquía aritmética .
Se sabe que PH está contenido dentro de PSPACE , pero no se sabe si las dos clases son iguales. Una reformulación útil de este problema es que PH = PSPACE si y solo si la lógica de segundo orden sobre estructuras finitas no obtiene poder adicional de la adición de un operador de cierre transitivo .
Si la jerarquía polinomial tiene problemas completos , entonces solo tiene un número finito de niveles distintos. Dado que hay problemas de PSPACE-completo , sabemos que si PSPACE = PH, entonces la jerarquía polinomial debe colapsar, ya que un problema de PSPACE-completo sería un-problema completo para algunos k . [8]
Cada clase en la jerarquía polinomial contiene -problemas completos (problemas completos bajo polinomios-tiempo muchos-uno reducciones). Además, cada clase en la jerarquía polinomial se cierra bajo-reducciones : significa que para una clase C en la jerarquía y un idioma, Si , luego también. Estos dos hechos juntos implican que si es un problema completo para , luego , y . Por ejemplo,. En otras palabras, si se define un lenguaje basado en algún oráculo en C , entonces podemos suponer que se define sobre la base de un problema completo para C . Los problemas completos, por tanto, actúan como "representantes" de la clase para la que están completos.
El teorema de Sipser-Lautemann establece que la clase BPP está contenida en el segundo nivel de la jerarquía polinomial.
El teorema de Kannan establece que para cualquier k ,no está contenido en SIZE (n k ).
El teorema de Toda establece que la jerarquía polinómica está contenida en P #P .
Problemas
- Un ejemplo de un problema natural en es la minimización del circuito : dado un número k y un circuito A que calcule una función booleana f , determine si hay un circuito con como máximo k puertas que calcule la misma función f . Sea C el conjunto de todos los circuitos booleanos. El idioma
es decidible en tiempo polinomial. El idioma
- Un problema completo para es satisfacibilidad para fórmulas booleanas cuantificadas con k - 1 alternancias de cuantificadores (abreviado QBF k o QSAT k ). Esta es la versión del problema de satisfacibilidad booleano para. En este problema, se nos da una fórmula booleana f con variables divididas en k conjuntos X 1 , ..., X k . Tenemos que determinar si es cierto que
- En este Compendio se puede encontrar una lista al estilo de Garey / Johnson de problemas que se sabe que están completos para el segundo y los niveles superiores de la jerarquía polinómica .
Ver también
- EXPTIME
- Jerarquía exponencial
- Jerarquía aritmética
Referencias
- ^ Arora y Barak, 2009, págs. 97
- ^ Completitud en la jerarquía del tiempo polinómico A Compendio, M. Schaefer, C. Umans
- ^ Arora y Barak, págs. 99-100
- ^ Arora y Barak, págs.100
- ^ Arora y Barak, págs.100
- ^ Arora y Barak, 2009, Teorema 5.4
- ^ Hemaspaandra, Lane (2018). "17.5 Clases de complejidad". En Rosen, Kenneth H. (ed.). Manual de Matemática Discreta y Combinatoria . Matemáticas discretas y sus aplicaciones (2ª ed.). Prensa CRC. págs. 1308-1314. ISBN 9781351644051.
- ^ Arora y Barak, 2009, reivindicación 5.5
Referencias generales
- Arora, Sanjeev; Barak, Boaz (2009). Teoría de la complejidad: un enfoque moderno . Prensa de la Universidad de Cambridge. ISBN 978-0-521-42426-4.
sección 1.4, "Máquinas como cuerdas y la máquina de Turing universal" y 1.7, "Prueba del teorema 1.9"
- AR Meyer y LJ Stockmeyer . El problema de equivalencia para expresiones regulares con cuadratura requiere espacio exponencial. En Proceedings of the 13th IEEE Symposium on Switching and Automata Theory , págs. 125-129, 1972. El artículo que introdujo la jerarquía polinomial.
- LJ Stockmeyer . La jerarquía de tiempo polinomial . Ciencias de la Computación Teórica , vol. 3, págs. 1–22, 1976.
- C. Papadimitriou . Complejidad computacional. Addison-Wesley, 1994. Capítulo 17. Jerarquía polinomial , págs. 409–438.
- Michael R. Garey y David S. Johnson (1979). Computadoras e intratabilidad: una guía para la teoría de NP-Completeness . WH Freeman. ISBN 0-7167-1045-5. Sección 7.2: La jerarquía polinomial, págs. 161-167.