¿Por qué P = NP no implica P = AP (es decir, P = PSPACE)?

18

Es bien sabido que si P=NP entonces la jerarquía polinomio colapsa y P=PH .

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 P=AltTime(nO(1)) (también conocido como AP=PSPACE )?

Estoy buscando una respuesta intuitiva.

José
fuente
1
Consulte también las preguntas relacionadas cstheory.stackexchange.com/questions/2032/… y cstheory.stackexchange.com/questions/5463/…
András Salamon
44
Se sabe que la NL=coNL pero se sospecha que AL (es decir, P ) no es igual a NL .
sdcvvc

Respuestas:

32

La prueba para P=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 ki d donde f k ( n ) = kid(n)=nfgn f(n)g(n)kknfkidfk(n)=k), pero no tenemos esto para funciones no constantes como , n 2̸ n .n2n2≪̸n

Kaveh
fuente
22

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 .

Peter Shor
fuente
11

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:

v = 2
for(i=1 to n)
  v = v*v

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.

Patey Ludovic
fuente
4

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 amplificar P=NP por más de un número constante de veces.

Supongamos que P=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 polytime A con tiempo de ejecución polinómico p(n)poly(n) st

Dado un circuito booleano φ , y una asignación parcial τ a las entradas,
A devuelve "sí" si hay una extensión de τ que satisface φ , y devuelve "no" en caso contrario.

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ómico Cook st

Dado un DTM M recibir dos entradas, y tres números unarios n , m , y t ,
Cook(M,n,m,t) devuelve un circuito booleano de tamaño O(t2) que simula M en las entradas de longitud (n,m) para t pasos.

Intentemos usar estos para extender el argumento de P=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 repetidamente Cook 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).

  • Sea φ un circuito cuantificado (inicializado a la fórmula cuantificada dada).
  • Deje k el número de cuantificadores en φ .
  • Para i de k a 1 do

    • Deje ψ = Qxkσ(x1,...,xk) sea la última cuantificador y la parte libre de cuantificador.
    • Si Q="" ,

      1. Calcular C=Cook(A,|σ|,|x1|+...+|xk1|,p) ,
      2. Sustituya los bits de entrada con σ en el circuito C ,
      3. Reemplace ψ con C en φ .
    • Si Q="" ,

      1. Considere ψ como ¬xk¬σ ,
      2. Calcular C=Cook(A,|¬σ|,|x1|+...+|xk1|,p) ,
      3. Sustituya los bits de entrada con ¬σ en el circuito C ,
      4. Reemplace ψ con ¬C en φ .
  • Calcule y devuelva CV(φ) .

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 algoritmo Cook 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:

  • Dado x ,
  • Deje n=|x|,
  • Deje y=x ,
  • Para i de 1 a n do
    • Deje y=y|y|, (es decir, concatenación de |y| copias de y )
  • Regresar y

Cada vez que ejecutamos y=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 con k(n) alternancias cuantificadoras (donde n es el tamaño total de la fórmula cuantificada).

Supongamos que A 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 (lp)O(k)(n)=l(p(l(p((l(p(n)))))))O(k) compositions . Incluso en el caso de que tantolyperan lineales (pero con coeficiente total dea2) 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).

Kaveh
fuente
¡Realmente me gusta esta respuesta!
Tayfun Pay
@kaveh ¿Qué sucede si mientras l ( t ) = O ( t ), entonces, necesitamos al menos un tiempo exponencial doble para N P N P N P ? Su argumento parece sugerir esa posibilidad mientras sabemos que P S P A C E está en E X P y, entonces, ¿cómo recuperar el exponencial simple? p(n)=2Ω(n)l(t)=O(t)NPNPNPPSPACEEXP
T ....
3

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).

MS Dousti
fuente