Qué tan difícil es la simulación exacta de algoritmos y una operación relacionada en clases de complejidad

Rompecabezas

Dado que el problema es largo aquí hay un caso especial que captura su sentido.

Problema: Sea A un algoritmo detrminístico para 3-SAT. Es el problema de simular completamente el algoritmo A (en cada instancia del problema). P-Space duro?

(Más precisamente, ¿hay razones para creer que esta tarea es P-Space difícil, hace algo en esta dirección a partir de conjeturas CC estándar, y hay esperanza de demostrar que esta tarea es X-difícil para alguna clase de complejidad X que se presume que es estar estrictamente por encima de NP.)

Preguntas relacionadas : are-pspace-complete-problems -herely-less-tractable-than-np-complete-problems ;

ACTUALIZACIÓN EDITADA : Hay varias interpretaciones para "Simular completamente A". Y puede haber diferentes respuestas interesantes según la interpretación. (También Ryan Williams propuso una interpretación para simular un algoritmo no determinista). Para una determinada manera de asociar un problema de decisión a la tarea computacional "Simular completamente A", Joe Fitzsimons encontró un algoritmo A para el cual este problema de decisión asociado todavía está en NP . Si "simular completamente" se refiere a ser capaz de salida de todo el registro de la computadora en un paso determinado $i$ entonces por el algoritmo de Joe parece que $P^{NP}$ es lo que se necesita. Para esta versión (creo, pero no estoy seguro), la respuesta de Ryan esboza un $P^{NP}$Argumento de dureza. Joe comentó que si a ustedes se les exige que proporcionen los registros completos (lo cual ya no es un problema de decisión), no es sorprendente que tengan que intensificar y las clases de complejidad no son las mismas.

De todos modos, si se requiere para emitir el estado de los registros a un paso prescrito $i$ entonces las respuestas de Ruan y Joe sugiere (pero de nuevo, no estoy seguro de ello) que $NP^+$ es esencialmente $P^{NP}$ . Podemos spaculate que por esta interpretación la operación empuja hacia arriba un paso mayor en el hiearachy polinomio, y que $PH^+ =PH$ .

En cualquier caso, según estas interpretaciones, la respuesta a mi pregunta teaser es NO .

Tenía en mente una interpretación más drástica para "simular completamente un algoritmo A". (Pero tal vez la interpretación de Joe y Ryan es más interesante). Mi interpretación al "simular completamente el algoritmo A" es que usted elimina el estado de los registros en cada paso . En particular, si el algoritmo no es polinómico, su salida tampoco será polinómica. Bajo esta interpretación drástica, me preguntaba si deberíamos creer que para cada algoritmo A, C A es P-SPACE difícil, y qué podemos probar.$i$$C_A$

Motivación:

Esta pregunta fue motivada por una conferencia de Paul Goldberg ( diapositivas , video , artículo ) que describe un artículo con Papadimitriou y Savani. Demostraron que se completa el espacio P para encontrar los equilibrios calculados por el algoritmo de Lemke-Howson. El problema para encontrar algún punto de equilibrio es solo PPAD completo. Esta brecha es bastante sorprendente y ya se describen resultados similares en el conocido artículo de Papadimitriu: La complejidad del argumento de paridad y otras pruebas ineficaces de existencia (1991) . (Se sabe que los problemas de PPAD completo no pueden ser NP-hard (a menos que sucedan cosas terribles, por lo que esto está muy lejos en el mundo de la complejidad en comparación con el espacio P).

De qué trata la pregunta

Mi pregunta es sobre lagunas similares para problemas de complejidad computacional aún más antiguos y más clásicos. (Tal vez esto ya sea familiar).

Dado un problema computacional podemos distinguir entre tres problemas

a) Resolver el problema algorítmicamente

b) Llegar a la misma solución que un algoritmo específico A

c) Simular todo el algoritmo A

Por supuesto, c) es al menos tan duro como b), que es al menos tan duro como a). Los resultados mencionados anteriormente muestran una brecha entre la dificultad computacional de las tareas a) yb) para el problema de los equilibrios informáticos. Nos gustaría entender la situación (y principalmente la brecha entre a) yc) para otros problemas computacionales.

La pregunta:

La forma básica de la pregunta con un ejemplo.

Comenzamos con un problema computacional, el problema X

Un ejemplo puede ser

Problema X: resolver una instancia de SAT con n variables

también especificamos

A: un algoritmo que realiza el problema X

y planteamos un nuevo problema

Problema Y: simule exactamente el algoritmo A

y estamos interesados ​​en la dificultad computacional del problema Y. Deseamos comprender la clase de tales problemas Y para todos los algoritmos A que resuelven el problema original X. Especialmente queremos saber qué tan fácil puede ser el problema Y (o qué tan difícil debe ser) ser) si se nos permite elegir el algoritmo A a voluntad.

La operación propuesta en clases de complejidad

Comience con una clase de complejidad que se describe en alguna tarea computacional. Dado un algoritmo de A para llevar a cabo cada instancia de esta tarea computacional, considerar una nueva clase de complejidad C A que se describe por la tarea de cálculo de simular completamente A . Entonces podemos (con suerte) definir un "ideal" de clases de complejidad$C$$C_A$$A$

para todos los algoritmos A}.$C^+ = \{C_A:$

Si dejamos que describa lo que una computadora digital puede hacer en tiempo polinómico (por lo que no quiero restringir la atención, por ejemplo, a problemas de decisión), entonces P + es el ideal abarcado por P en sí.$P$$P^+$$P$

Finalmente mis preguntas

Mis preguntas son:

1) ¿Tiene sentido la definición (en el sentido amplio de la palabra sentido)? ¿Es bien conocido o lo mismo que (o similar a) algo bien conocido? (Mi formulación fue informal y, en particular, cuando pasamos de problemas específicos como SAT a una clase de complejidad como NP, tenemos que preocuparnos por varias cosas que descuidé).

Las siguientes dos preguntas suponen que la definición puede tener sentido o rescatarse para tener sentido.

2) Supongamos que nos equipamos con todas las conjeturas estándar con respecto a la completitud computacional. ¿Podemos decir qué se supone que es para algunas clases de complejidad familiares? (Por ejemplo, C = N P , C = P-espacio, ..)? EDIT: Varias personas señaló que P S P A C E + = P S P A C E . Entonces, ¿podemos preguntar qué es ( P N P ) + ? es P H + = P H ?$C^+$$C=NP$$C$$PSPACE^+=PSPACE$$(P^{NP})^+$$PH^+=PH$

¿Podemos adivinar cuáles son las clases de competencia para que C + sea ​​el ideal abarcado por C ?$C$$C^+$$C$

Entonces, la pregunta de cuán fácil puede ser la tarea computacional de simular un algoritmo A para 3-SAT (cuando podemos elegir el algoritmo para hacerlo lo más fácil posible) es un caso especial interesante.

3) ¿Hay esperanza de probar algo sobre esta operación?

Por supuesto, si demuestra que todas las clases de complejidad en tienen espacio en P, esto mostrará que P = N P implica P = P S P $NP^+$$P=NP$ , lo que (creo) sería un resultado enorme y muy inesperado . Pero si muestra que todas las clases de complejidad en N P + son difíciles de decir en el tercer nivel de la Jerarquía polinómica (por ejemplo, Δ P 3 ), esto solo implicaría cosas que ya sabemos, cosas que se derivan del hecho de que P = N P hace que el PH colapse.$P=PSPACE$$NP^+$$\Delta_3^{\bf P}$$P=NP$

Problema: Sea A un algoritmo determinista para 3-SAT. ¿El problema de simular completamente el algoritmo A (en cada caso del problema) P-Space es difícil?

No entiendo la declaración de este problema. Pero creo que hay una forma natural de formalizar su pregunta más general que puede arrojar un poco de luz sobre ella. Tal vez me estoy perdiendo completamente tu punto, pero espero que aún encuentres algo interesante para leer aquí.

1) ¿Tiene sentido la definición (en el sentido amplio de la palabra sentido)? ¿Es bien conocido o lo mismo que (o similar a) algo bien conocido? (Mi formulación fue informal y, en particular, cuando pasamos de problemas específicos como SAT a una clase de complejidad como NP, tenemos que preocuparnos por varias cosas que descuidé).

Una forma de dar sentido a la tarea de simular exactamente el algoritmo $Y$ es la siguiente. Arreglemos el modelo para que sea máquinas de Turing de una sola cinta por simplicidad; Lo que diré puede aplicarse a cualquier modelo computacional típico.

Para cada algoritmo y entrada x , podemos definir su historial de cómputo H Y ( x , i , j ) : Dados enteros i y j que varían de 0 al tiempo de ejecución de Y , H Y ( x , i , j ) es igual a El contenido de la celda j de la cinta de la máquina Turing Y en la entrada $Y$$x$ $H_Y(x,i,j)$$i$$j$$0$$Y$$H_Y(x,i,j)$$j$$Y$$x$ en el paso de tiempo . (Y si la cabeza de la cinta está leyendo el $i$$j$º celular en el ª etapa, incluye que también junto con el estado de la máquina.) Por supuesto, las historias de cálculo vienen todo el tiempo en la teoría de la complejidad.$i$

Ahora, uno podría argumentar que cualquier algoritmo que puede decidir el idioma

$C_Y = \{(x,i,j,\sigma)~|~H_Y(x,i,j)=\sigma\}$

(o simular la función en todas las entradas) es la solución de la tarea exactamente algoritmo de simular Y , debido a que tiene la capacidad de imprimir cada pequeña parte de todas las posibles cálculo del algoritmo Y . Ciertamente, dado un oráculo para C $H_Y$$Y$$Y$$C_Y$ se podría hacer una simulación paso a paso de .$Y$

2) Supongamos que nos equipamos con todas las conjeturas estándar con respecto a la complejidad computacional. ¿Podemos decir qué se supone que es C + para algunas clases de complejidad familiares? (Por ejemplo, C = NP, C = espacio P, ..)? ¿Podemos adivinar cuáles son las clases de complejidad C para que C + sea el ideal abarcado por C?

Esta sigue siendo una pregunta interesante, según la propuesta anterior. Para las clases de tiempo deterministas, nada cambia. es solo P : podemos decidir C Y en polytime, para cada algoritmo de polytime. Del mismo modo E X P + = E X P . También P S P A C E + sigue siendo P S P A C E . Para las clases de complejidad temporal no deterministas, la situación se vuelve más interesante. En ese caso, un algoritmo Y puede tener múltiples historiales de cálculo, por lo que$P^+$$P$$C_Y$$EXP^+ = EXP$$PSPACE^+$$PSPACE$$Y$ ya no está bien definido. Sin embargo, todavía queremos imprimirunhistorial de cálculo, por lo que nuestra "simulación exacta" tendría que aislar un historial de cálculo específico no determinista y luego imprimir sus valores. Para unalgoritmo N P Y , se puede decir que C Y ∈ P N P : podemos usar eloráculo N P para la búsqueda binaria del "primer" historial de cómputo de aceptación (en orden lex), luego, una vez que lo hayamos obtenido, imprima los bits relevantes Para unalgoritmo N E X P Y , se puede decir C Y$H_Y$$NP$$Y$$C_Y \in P^{NP}$$NP$$NEXP$$Y$ , por razones similares.$C_Y \in EXP^{NP}$

¿Podemos poner en una clase más pequeña? No lo sé. Tenga en cuenta que no podemos simplemente redefinir$NP^+$

{ ( x , i , j , σ ) | existe un H Y tal que H Y ( x , i , j ) = σ }$C_Y =$$(x,i,j,\sigma)~|~$$H_Y$$H_Y(x,i,j)=\sigma$

para tratar de poner en N P , porque necesitamos que la cadena de historial sea la misma para todos los cuádruples que involucran x , para "simular exactamente el algoritmo$C_Y$$NP$$x$ ".$Y$

De todos modos, este problema de no poder "imprimir un testigo" a un cálculo sin ir a E X P N P surge en algunas situaciones, como la complejidad del circuito. Si N E X P tiene circuitos de tamaño polinómicas, entonces es también el caso de que C Y ∈ P / p o l y para cada no determinista 2 n k tiempo Y ? Impagliazzo, Kabanets y Wigderson$NEXP$$EXP^{NP}$$NEXP$$C_Y \in P/poly$$2^{n^k}$$Y$respondió esta pregunta afirmativamente en 2001. Su demostración es extremadamente interesante, invocando herramientas de desrandomización y diagonalización (¿por qué sería necesaria la desrandomización para tal resultado?) y resulta ser un teorema muy útil para probar los límites inferiores del circuito para funciones.$NEXP$

¿Hay esperanza de probar algo sobre esta operación?

Tal vez ... eso depende de si está satisfecho con la formalización anterior de su pregunta. Para un determinista 3-SAT algoritmo , creo que el anteriormente simulación exacta de Y problema sería P N P ( 1 ) -Hard, donde P N P ( 1 ) es tiempo polinómico con una consulta a N P . (La molesta sintaxis de StackExchange requiere que escriba (1) en lugar de la alternativa. Anteriormente dije que C Y debería ser P N P -duro, pero no estoy seguro de los detalles: puede ver cómo generalizar lo siguiente).$Y$$Y$$P^{NP(1)}$$P^{NP(1)}$$NP$$C_Y$$P^{NP}$

Damos un polytime reducción mucho-uno de cada a C Y . Dada tal L , dejemos que M sea ​​una máquina que reconoce L que realiza una sola consulta N P. WLOG, esa consulta es una fórmula SAT. También WLOG, la consulta SAT se puede "posponer" hasta el último paso del cálculo, en el siguiente sentido: hay un algoritmo de tiempo polinómico A ( x ) que imprime una fórmula F y un bit b , de modo que para todo $L \in P^{NP(1)}$$C_Y$$L$$M$$L$$NP$$A(x)$$F$$b$$x$ ,

acepta iff A ( x ) = ( F , b ) tal que ( S A T ( F ) XOR b ) = 1.$M(x)$$A(x)=(F,b)$$SAT(F)$$b$

( puede rechazar si F es satisfactoria, o puede aceptar; el bit b captura esto).$M$$F$$b$

Para simplificar, digamos que cuando finaliza su cálculo, mueve la cabeza de la cinta a la celda 1, escribe "aceptar" o "rechazar" en esa celda y realiza bucles para siempre. Luego, preguntar si ( F , T , 1 , a c c e p t ) ∈ C Y para T suficientemente grande nos dirá si se acepta F. (En general, solo necesitamos que sea eficiente calcular la instancia y de C Y que nos dirá). Tenga en cuenta que esto ya muestra que C Y es tanto N P -duro como$Y$$(F,T,1,accept) \in C_Y$$T$$F$$y$$C_Y$$C_Y$$NP$ duro; esto último es cierto porque ( F , T , 1 , r e j e c t ) ∈ C Y si$coNP$$(F,T,1,reject) \in C_Y$$F$ es no satisfiable.

La reducción final de a C Y es: dado x , ejecute A ( x ) obteniendo ( F , b ) . Si b = 0 entonces salida ( F , T , 1 , a c c e p t ) , de lo contrario si b = 1 salida ( F , T , 1 , r e j e c $L$$C_Y$$x$$A(x)$$(F,b)$$b=0$$(F,T,1,accept)$$b=1$ .$(F,T,1,reject)$

Para cada estamos produciendo (en tiempo polinómico) un y tal que M ( x ) acepta si y sólo si y ∈ C Y .$x$$y$$M(x)$$y \in C_Y$

(Gracias a Joe por exigir que sea más claro sobre esta parte).

Pero no veo (por ejemplo) cómo obtener -dureza. Para reducir Σ 2 -SAT al problema, parecería que necesitaría escribir una instancia SAT 3-CNF x que simule su algoritmo determinista Y dentro de él (donde Y está resolviendo Tautologías en varios subproblemas). Pero como Y no tiene un límite de tiempo determinado, ese 3-CNF x podría ser enorme, por lo que no necesariamente se obtiene una reducción del tiempo polinomial. A menos que me falte algo.$\Sigma_2 P$$\Sigma_2$$x$$Y$$Y$$Y$$x$

Inicialmente publiqué una respuesta incorrecta, así que espero que esto sea una mejora.

Voy a comenzar considerando el ejemplo 3SAT. En tu comentario sobre la respuesta de Ryan dices

Me interesa lo difícil que es simular un algoritmo determinista Y para 3-SAT. Y la pregunta es si no importa qué Y es, este es el espacio P difícil.

La respuesta a esto es que no es difícil para PSPACE durante al menos un poco de Y, suponiendo que NP PSPACE, pero que existen otros algoritmos para los que es difícil para PSPACE. Mostrar esto último es trivial: simplemente construimos un algoritmo que interpreta la cadena de bits que representa la fórmula 3SAT como un problema TQBF, que luego resuelve antes de resolver la instancia 3SAT. Obviamente, no hay nada especial sobre TQBF en este caso, por lo que el algoritmo puede hacerse arbitrariamente difícil de simular. Por lo tanto, solo debemos preocuparnos por los límites inferiores en la simulación de cualquier algoritmo para un problema dado, en lugar de un algoritmo específico.$\neq$

Con eso en mente, construimos el siguiente algoritmo para resolver 3SAT:

Tome un registro de bits (inicialmente todos configurados en 0) para contener una solución de prueba, junto con un registro que contenga la instancia 3SAT, un registro de contador de tamaño ⌈ log 2 ( c + 1 ) ⌉ establecido inicialmente en 1 y dos banderas bits (llame a estos el indicador de error y el indicador de aceptación). Aquí c es el número de cláusulas. El algoritmo luego procede de la siguiente manera:$n$$\lceil\log_2 (c + 1)\rceil$$c$

• Si el valor del contador de cláusulas es menor o igual que c , y la solución de prueba no es 111 ...... 1 , verifique si se cumple la cláusula k . Si no se establece el bit de falla. Incrementa el contador.$k$$c$$111......1$$k$
• Si el valor del contador de cláusulas es menor o igual que c , y la solución de prueba es 111 ...... 1 , verifique si se cumple la cláusula k . Si no es así, establezca el indicador de error. Incrementa el contador.$k$$c$$111......1$$k$
• Si excede c , y la solución de prueba no es 111 ...... 1 , verifique si el indicador de falla está configurado. Si es así, incremente la solución de prueba, restablezca el contador k a 1 y desactive el indicador de error. Si no se configuró el indicador de error, establezca el indicador de aceptación, establezca el contador de cláusula k en cero, establezca la solución de prueba en cero y pare.$k$$c$$111......1$$k$$k$
• Si excede c , y la solución de prueba es 111 ...... 1 , verifique si el indicador de falla está configurado. Si no se configuró el indicador de error, establezca el indicador de aceptación. Establezca el contador de cláusulas k en cero, establezca la solución de prueba en cero y pare.$k$$c$$111......1$$k$

Cuando el algoritmo se detiene, el estado del indicador de aceptación le indica si la fórmula 3SAT se puede satisfacer o no.

Ahora, si quiero calcular el estado del algoritmo en el momento tengo un algoritmo para calcular esto en tiempo polinómico con una sola llamada a un oráculo NP de la siguiente manera:$i$

Tenga en cuenta que para cualquier , suponiendo que el bit de aceptación aún no se haya establecido, el estado de los registros se puede calcular en tiempo polinómico, ya que el valor de k y el registro de la solución de prueba t son simplemente funciones de i . La determinación de si se establece el indicador de falla se puede hacer en tiempo polinómico, simplemente comprobando si el estado actual del registro de la solución de prueba satisface todas las cláusulas menores o iguales al valor actual de k . Si y solo si este no es el caso, se establece el indicador de error. El indicador de aceptación se establece en cero.$i$$k$$t$$i$$k$

Del mismo modo, si el bit de aceptación ya se ha establecido, el estado de los registros se puede calcular de manera eficiente, ya que todo es cero, excepto el bit de aceptación, que se establece.

Entonces, la única dureza es determinar si el bit de aceptación está configurado. Esto es equivalente a determinar si la instancia 3SAT dada tiene una solución menor que . Si lo hace, entonces el bit de aceptación debe necesariamente establecerse, y si no lo hace, entonces el bit de aceptación debe ser necesariamente cero. Claramente, este problema es en sí NP-completo.$t$

Por lo tanto, el estado del sistema en el paso puede determinarse en tiempo polinómico con una sola consulta a un oráculo NP.$i$

Actualización importante: inicialmente había leído mal la formulación de Ryan de la simulación exacta como un problema de decisión, por lo que mi afirmación de que la versión de decisión estaba en NP era incorrecta. Dado el problema de decidir si el bit en el paso i en la entrada x tal como se formula en la respuesta de Ryans, existen 3 posibilidades:$j$$i$$x$

1. Este bit es constante independientemente de si es satisfactoria. Como solo hay dos estados posibles para el sistema en este momento (ambos se pueden calcular en P) determinar si este es el caso, y si es así, si el valor es igual a σ está en P.$F$$\sigma$
2. El bit es igual a si F ∈ S A T , y de lo contrario es desigual. Este problema está claramente en NP, ya que la asignación satisfactoria de F actúa como testigo.$\sigma$$F\in SAT$$F$
3. El bit es igual a si F ∈ U N S A T en cuyo caso el problema está en coNP.$\sigma$$F\in UNSAT$

Claramente decidir cuál de estos tres es el caso se puede hacer en tiempo polinómico, simplemente comparando el valor de ese bit toma si y si F ∈ U N S A T . Por lo tanto, el problema exacto de simulación está en NP ∪ coNP. Por lo tanto, como Ryan del límite inferior y límite superior de mi pareja, suponiendo que ambos son correctos, creo que tenemos una respuesta: C Y = N P ∪ C O N P .$F\in SAT$$F\in UNSAT$$\cup$$C_Y = NP\cup coNP$

Tenga en cuenta que no hay nada especial sobre 3SAT en este caso, y lo mismo podría hacerse para cualquier problema en NP. Además, se puede usar el mismo truco para cualquier clase de complejidad no determinista, no solo NP, que parecen ser las más difíciles de simular. Para las clases deterministas, simplemente puede ejecutar el mejor algoritmo y detenerse en el paso . Con esto en mente, la simulación completa de al menos algún algoritmo determinista para un problema es tan difícil como resolver el problema en sí.$i$

Muy interesante pensamiento! Aquí hay un comentario extendido que fue demasiado largo para publicar como tal:

En cuanto a la definición en (1) como tal , es decir:

Comience con una clase de complejidad que se describe en alguna tarea computacional. Dado un algoritmo de A para llevar a cabo cada instancia de esta tarea computacional, considerar una nueva clase de complejidad C A que se describe por la tarea de cálculo de simular completamente A . Entonces podemos (con suerte) definir un "ideal" de clases de complejidad: C + = { C A : para todos los algoritmos A } .$C$$C_A$$A$$C^+ = \{C_A:$$A\}$

$C^+$$M$$M^{\prime}$$L(M) \stackrel{?}{=} L(M^{\prime})$

$M^*$$M$$M$ accepts and rejects if $M$ rejects. This only costs a linear overhead. Specifically, if $M$ runs in $t(n)$ computational steps, then $M^*$ runs in $O(t(n))$ (whereby "run," I mean "simulates $M$ exactly").

This suggests to me that if there's any serious traction to be gained here, the precise way you go about making the definition of the ideal of a complexity class is going to be fairly important. In particular, if you intend to show that the ideal of, say, $NP$ is $PSPACE$-hard, you'll have to rule out the notion of a trivial, linear-time simulation of the $NP$ machines in question.

With respect to the homotopy methods described in the talk/paper and GPS's $PSPACE$-completeness result, I believe the "gap" you're witnessing between $PPAD$-completeness and $PSPACE$-hardness is due to the distinction between finding any NE (in the sense of END OF LINE) and finding a unique NE given a specific, initial configuration (in the sense of OTHER END OF LINE).