Es bien sabido que si entonces la jerarquía polinomio colapsa y .
Esto puede entenderse fácilmente inductivamente utilizando máquinas Oracle. La pregunta es: ¿por qué no podemos continuar el proceso inductivo más allá de un nivel constante de alternancias y demostrar (también conocido como )?
Estoy buscando una respuesta intuitiva.
Respuestas:
La prueba paraP=AltTime(O(1)) ( =PH ) es una inducción utilizando P=NP . La inducción muestra que para cualquier número natural k , P=AltTime(k) (y AltTime(O(1)) es solo su unión).
La inducción no funciona cuando el número de alternancia puede cambiar con el tamaño de entrada (es decir, cuando el número de posibles alternancias de la máquina no es un número, sino una función del tamaño de entrada, es decir, no estamos mostrando que una ejecución de la máquina en una sola entrada puede reducirse a ninguna alternancia, estamos demostrando que las ejecuciones de la máquina en todas las entradas pueden reducirse "uniformemente" a ninguna alternancia).
Veamos una declaración similar pero más simple. Queremos mostrar que la función de identidad eventualmente domina todas las funciones constantes ( f ≪ g iff para todas pero finitamente muchas n f ( n ) ≤ g ( n ) ). Se puede demostrar por inducción. Para todo k , k ≪ n (es decir, f k ≪ i d donde f k ( n ) = kid(n)=n f≪g n f(n)≤g(n) k k≪n fk≪id fk(n)=k ), pero no tenemos esto para funciones no constantes como , n 2 ≪ ̸ n .n2 n2≪̸n
fuente
Compare la jerarquía polinómica con la jerarquía para pruebas interactivas. Si para alguna k fija , tiene k alternancias en una prueba interactiva - IP ( k ) - la clase de complejidad resultante no tiene más potencia que la que obtiene con dos alternancias, es decir, IP ( k ) = IP (2 ) = AM (suponiendo que k ≥2). Sin embargo, si permite un número polinómico de alternancias, obtiene la clase de complejidad IP = PSPACE, que se cree que es mucho más grande que AM, una clase está contenida en Π 2 P, en el segundo nivel de la jerarquía polinómica. Entonces, este fenómeno realmente ocurre (aunque, hasta donde sabemos, con la jerarquía polinómica).
Esto sucede porque la reducción que toma un problema de tamaño n en IP ( k ) y lo convierte en un problema en IP (2) explota el tamaño del problema, de modo que mientras que para cualquier IP específica ( k ) el problema sigue siendo de tamaño polinómico , si deja que k varíe, la reducción resultante no genera problemas polinomiales en k .
fuente
Aquí hay una pequeña intuición sobre la brecha entre las alternancias constantes y sin límites: una operación polinomial repetida un número constante de veces es polinomial, pero repetir un número polinómico de veces puede ser exponencial. Por ejemplo, tome la multiplicación repetida en sí misma:
El número de iteraciones es lineal y la salida es exponencial. Pero si arregla n, es polinomial en el tamaño del valor inicial.
fuente
A continuación, amplío un poco el punto en la respuesta de Peter tratando de llevar a cabo la eliminación del cuantificador durante más de un número constante de pasos para ver dónde falla y si se puede salvar algo de tal intento.
Intentemos amplificarP=NP por más de un número constante de veces.
Supongamos queP=NP . Por lo tanto, existe una máquina del tiempo polinómica que resuelve Ext-Circuit-SAT (¿hay una extensión satisfactoria para un circuito dado y una asignación parcial a sus entradas?).
Más formalmente, tenemos un algoritmo polytimeA con tiempo de ejecución polinómico p(n)∈poly(n) st
Para repasar tiempos constantes, necesitamos eliminar el cuantificador de manera efectiva. Podemos hacer esto porque el teorema de Cook-Levin es un teorema constructivo, de hecho, proporciona un algoritmo de tiempo polinómicoCook st
Intentemos usar estos para extender el argumento deP=PH para obtener un algoritmo que resuelva TQBF (en realidad TQBCircuit, es decir, un problema del circuito booleano totalmente cuantificado).
La idea del algoritmo es la siguiente: usamos repetidamenteCook en A para eliminar los cuantificadores de un circuito cuantificado dado. Hay un número lineal de cuantificadores, por lo que esperamos obtener un algoritmo de tiempo polinómico (tenemos un algoritmo con muchos pasos polinomiales utilizando la subrutina de tiempo polinomial Cook ). Al final de este proceso de eliminación del cuantificador tendremos un circuito libre de cuantificadores que se puede evaluar en tiempo polinómico (el problema del valor del circuito está en P , sea CV un algoritmo de tiempo polinómico para calcular el valor del circuito de un circuito dado) .
Sin embargo, veremos que esta idea no funciona (por la misma razón señalada por Peter).
Parai de k a 1 do
SiQ="∃" ,
SiQ="∀" ,
El algoritmo resultante parece tiempo polinómico: tenemos muchos pasos polinómicos, cada paso es computable en tiempo polinómico. Sin embargo, esto no es correcto, el algoritmo no es el tiempo polinómico.
El uso de subrutinas de tiempo polinómico en un algoritmo de tiempo polinómico es tiempo polinómico. El problema es que, en general, esto no tiene que ser cierto si los valores devueltos por las subrutinas no son de tamaño polinómico en la entrada original y asumimos que hacemos asignaciones sobre los valores que regresan de las subrutinas. (En el modelo TM tenemos que leer la salida de cualquier subrutina de tiempo polinomial bit por bit.) Aquí el tamaño del valor devuelto por el algoritmoCook está aumentando (puede ser una potencia del tamaño de la entrada que se le da , la potencia exacta depende del tiempo de ejecución de A y está alrededor de p2(|input|) , así como sabemos que A no puede ser menor que el tiempo lineal, |output| es al menos |input|2 )
El problema es similar al código simple a continuación:
Cada vez que ejecutamosy=y|y| cuadramos el tamaño de y . Después de n ejecuciones tendremos una y que es x2n y tiene un tamaño n2n , obviamente no es un polinomio en el tamaño de la entrada.
Supongamos que solo consideramos fórmulas cuantificadas conk(n) alternancias cuantificadoras (donde n es el tamaño total de la fórmula cuantificada).
Supongamos queA ejecuta en el tiempo p ( p . Ej., Tiempo lineal que no se ha descartado hasta ahora), y tal vez tenga un algoritmo Cook más eficiente que genere un circuito más pequeño de tamaño l(t) en lugar de t2 , entonces obtenemos un algoritmo para ExtCircuitSat que se ejecuta en el tiempo (l∘p)O(k)(n)=l(p(l(p(…(l(p(n)))))))O(k) compositions . Incluso en el caso de que tantol yp eran lineales (pero con coeficiente total dea≥2 ) que se pueden conseguir un algoritmo que se ejecuta en tiempoΩ(n2k(n)) y sik(n)=Θ(n) se seríaΩ(n2n) similar al algoritmo de fuerza bruta (e incluso esto se basó en suponer que Cook-Levin se puede realizar en algoritmos que resultan en circuitos de tamaño lineal en el tiempo de ejecución del algoritmo).
fuente
Creo que esto se debe a que en cada nivel del PH, el número de alternancias es una constante (es decir, independiente del tamaño de entrada), mientras que en AP, el número de alternancias puede ser ilimitado (pero polinomial en el tamaño de la entrada).
fuente