Las clases dentro de la jerarquía tienen problemas completos (con respecto a las reducciones de tiempo polinómico ) que preguntan si las fórmulas booleanas cuantificadas se cumplen, para fórmulas con restricciones en el orden de los cuantificadores. Se sabe que la igualdad entre clases del 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 polinomial.
Definición de oráculo
Para la definición de Oracle de la jerarquía polinomial, defina
¿Dónde está el conjunto de problemas de decisión que pueden resolverse en tiempo polinomial mediante una máquina de Turing aumentada por un oráculo para algún problema completo de clase A? las clases y se definen de manera análoga. Por ejemplo, y es la clase de problemas que pueden resolverse en tiempo polinomial mediante una máquina determinista de Turing 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 polinómica, sea L un lenguaje (es decir, un problema de decisión , un subconjunto de {0,1} * ), sea p un polinomio y defina
donde hay alguna codificación estándar del par de cadenas binarias x y w como una única cadena binaria. El lenguaje L representa un conjunto de pares ordenados de cadenas, donde la primera cadena x es miembro de , y la segunda cadena w es un testigo "corto" ( ) que testifica que x es miembro de . En otras palabras, si y sólo si existe un testigo breve tal que . De manera similar, defina
Tenga en cuenta que se cumplen las leyes de De Morgan : y , donde L c es el complemento de L .
Sea C una clase de lenguajes. Amplíe estos operadores para que funcionen en clases completas de idiomas según la definición.
Nuevamente, se cumplen las leyes de De Morgan: y , donde .
Las clases NP y co-NP se pueden definir como , y , donde P es la clase de todos los lenguajes decidibles (en tiempo polinomial). La jerarquía polinómica se puede definir recursivamente como
Tenga en cuenta que , y .
Esta definición refleja la estrecha conexión entre la jerarquía polinómica y la jerarquía aritmética , donde R y RE desempeñan papeles 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 alterna es una máquina de Turing no determinista con estados no finales divididos en estados existenciales y universales. Eventualmente aceptará su configuración actual si: está en un estado existencial y puede realizar la transición a alguna configuración eventualmente aceptante; o está en un estado universal y cada transición es hacia alguna configuración que finalmente se acepta; o está en un estado de aceptación. [3]
Definimos como la clase de lenguajes aceptados por una máquina de Turing alternante en tiempo polinómico, de modo que el estado inicial es un estado existencial y cada camino que la máquina puede tomar se intercambia como máximo k – 1 veces entre estados existencial y universal. Definimos de 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 existencial y universal, de modo que solo requerimos que nuestra máquina de Turing alterna funcione en tiempo polinómico, entonces tenemos la definición de la clase AP , que es igual a PSPACE . [5]
Relaciones entre clases en la jerarquía polinómica
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ética y analítica, cuyas inclusiones se sabe que son apropiadas, queda abierta la cuestión de si alguna de estas inclusiones es apropiada, aunque se cree ampliamente que todas lo son. Si hay alguno , o si hay alguno , entonces la jerarquía colapsa al nivel k : para todos ,. [6] En particular, tenemos las siguientes implicaciones que involucran problemas no resueltos:
Generalmente se piensa que la cuestión del colapso hasta el primer nivel es extremadamente difícil. La mayoría de los investigadores no creen en un colapso, ni siquiera al segundo nivel.
Se sabe que PH está contenido en PSPACE , pero no se sabe si las dos clases son iguales. Una reformulación útil de este problema es que PH = PSPACE si y sólo si la lógica de segundo orden sobre estructuras finitas no obtiene poder adicional al agregar un operador de cierre transitivo sobre relaciones de relaciones (es decir, sobre las variables de segundo orden). [8]
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 . [9]
Cada clase en la jerarquía polinomial contiene problemas completos (problemas completos bajo reducciones de muchos uno en tiempo polinomial). Además, cada clase en la jerarquía polinómica tiene subreducciones cerradas : lo que significa que para una clase C en la jerarquía y un idioma , si , entonces también. Estos dos hechos juntos implican que si es un problema completo para , entonces y . Por ejemplo, . En otras palabras, si un lenguaje se define en base a algún oráculo en C , entonces podemos asumir que está definido en base a un problema completo para C. Por tanto, los problemas completos actúan como "representantes" de la clase para la que son completos.
El teorema de Sipser-Lautemann establece que la clase BPP está contenida en el segundo nivel de la jerarquía polinómica.
El teorema de Kannan establece que para cualquier k , no está contenido en TAMAÑO (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 es la minimización de circuitos : dado un número k y un circuito A que calcula una función booleana f , determine si hay un circuito con como máximo k puertas que calcula la misma función f . Sea C el conjunto de todos los circuitos booleanos. el idioma
es decidible en tiempo polinomial. el idioma
es el lenguaje de minimización de circuitos. porque L es decidible en tiempo polinómico y porque, dado , si y sólo si existe un circuito B tal que para todas las entradas x , .
Un problema completo es la satisfacibilidad de 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 booleana 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
Es decir, ¿existe una asignación de valores a variables en X 1 tal que, para todas las asignaciones de valores en X 2 , existe una asignación de valores a variables en X 3 , ... f es verdadera? La variante anterior está completa para . La variante en la que el primer cuantificador es "para todos", el segundo es "existe", etc., es completa para . Cada idioma es un subconjunto del problema obtenido al eliminar la restricción de k – 1 alternancias, el problema completo de PSPACE TQBF .
En este Compendio se puede encontrar una lista estilo Garey/Johnson de problemas que se sabe que están completos para el segundo nivel y superiores de la jerarquía polinomial.
Arora, Sanjeev; Barac, Booz (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, "Demostración del teorema 1.9"
^ Completitud en la jerarquía de tiempo polinomial Un compendio, M. Schaefer, C. Umans
^ Arora y Barak, páginas 99-100
^ Arora y Barak, págs.100
^ Arora y Barak, págs.100
^ Arora y Barak, 2009, Teorema 5.4
^ Hemaspaandra, carril (2018). "17.5 Clases de complejidad". En Rosen, Kenneth H. (ed.). Manual de matemáticas discretas y combinatorias . Matemáticas discretas y sus aplicaciones (2ª ed.). Prensa CRC. págs. 1308-1314. ISBN9781351644051.
^ Ferrarotti, Flavio; Van den Bussche, enero; Virtema, Jonni (2018). "Expresividad dentro de la lógica de cierre transitivo de segundo orden". DROPS-IDN/V2/Document/10.4230/LIPIcs.CSL.2018.22 . Schloss-Dagstuhl - Leibniz Zentrum für Informatik. doi : 10.4230/LIPIcs.CSL.2018.22 . S2CID 4903744.