¿Son los problemas completos

En la actualidad, no es factible resolver un problema completo o un problema completo P S P A C E en el caso general de entradas grandes. Sin embargo, ambos se pueden resolver en tiempo exponencial y espacio polinómico.$NP$$PSPACE$

Dado que no podemos construir computadoras no deterministas o 'afortunadas', ¿tiene alguna diferencia si un problema es -completo o P S P A C E -complete?$NP$$PSPACE$

$NP$$PSPACE$

$PSPACE$$NP$$QBF$$PSPACE$$SAT$$NP$$PSPACE$$NP$

Permítame ser un defensor del diablo y darle un ejemplo en el que un problema resulta ser "más difícil" que el otro, pero resulta ser "más manejable" que el otro.

$F(x_1,\ldots,x_{n})$$n$$n$

$\Phi_1 = (\exists x_1)(\exists x_2)\cdots (\exists x_{n-1})(\exists x_{n})F(x_1,\ldots,x_{n})$

$\Phi_2 = (\exists x_1)(\forall x_2)\cdots (\exists x_{n-1}(\forall x_{n})F(x_1,\ldots,x_{n})$

$\Phi_2$

$\Phi_1$$\Phi_2$

$\Phi_1$$NP$$\Phi_2$$PSPACE$$\Phi_2$$\Phi_1$$F$$2^n$$\Phi_2$$F$$O(2^{.793 n})$

La intuición es que agregar cuantificadores universales en realidad restringe el problema , lo que hace que sea más fácil de resolver, en lugar de más difícil. El algoritmo de búsqueda del árbol de juego depende en gran medida de tener cuantificadores alternos y no puede manejar cuantificaciones arbitrarias. Aún así, el punto sigue siendo que los problemas a veces pueden volverse "más simples" bajo una medida de complejidad, aunque puedan parecer "más difíciles" bajo otra medida.

Sí importa, porque hay más en juego que si podemos o no encontrar soluciones. También es de interés si podemos verificar las soluciones. Se pueden hacer otras distinciones cualitativas entre la dificultad de los problemas, pero para NP frente a clases de mayor complejidad, esta sería la que yo identificaría como la más importante.

Para problemas de decisión, problemas para los cuales cada instancia tiene una respuesta ' SÍ ' o ' NO ', NP es precisamente la clase de problemas para los cuales podemos verificar de manera eficiente una supuesta prueba de que una instancia dada es una instancia ' SÍ ', determinísticamente, si Se nos presenta uno. Por ejemplo, si tiene una asignación satisfactoria de variables para una instancia de 3-SAT, esa asignación le permite probar eficientemente que la instancia es satisfactoria. Una tarea tan satisfactoria puede ser difícil de encontrar, pero una vez que tenga una, puede demostrar fácilmente a los demás que la instancia es satisfactoria simplemente haciendo que verifiquen la solución que ha encontrado.

Del mismo modo, para coNP , existen pruebas comprobables de manera eficiente para instancias ' NO '; y para problemas en NP  ∩  coNP , puede hacer ambas cosas. Pero para los problemas completos de PSPACE , no existen tales procedimientos, a menos que pueda probar algunas igualdades bastante espectaculares de las clases de complejidad.

No sabemos cómo construir problemas difíciles de caso promedio a partir de problemas NP completos (el peor de los casos), pero podemos hacer esto para PSPACE (ver Köbler y Schuler (1998) ) para crear problemas incluso sobre la distribución uniforme que no puede ser resuelto en la mayoría de las entradas a menos que todo PSPACE sea fácil de calcular.

Desde un punto de vista práctico, es importante recordar que NP-Completeness no es una barrera para muchos problemas en la práctica. Las herramientas gemelas de los solucionadores de SAT y CPLEX (para la programación lineal de enteros) son lo suficientemente potentes y bien diseñadas que a menudo es posible resolver grandes instancias de problemas NP-completos al enmarcar el problema como un ILP adecuado o por reducción a SAT.

No conozco solucionadores similares bien diseñados para problemas en PSPACE.

Puede pensarlo de esta manera: ¿un problema de matemáticas tiene una prueba que sea legible para los humanos, o inherentemente requiere una "prueba de computadora"? Ejemplos: ¿es la posición inicial de las damas un empate? (Respuesta: sí.) ¿Es la posición inicial del ajedrez una victoria para las blancas? (Respuesta: desconocida, pero la mayoría de los graduados piensan que es un empate).

La prueba de que la posición inicial de los inspectores es un empate en última instancia requiere que uno acepte que la computadora realmente verificó con precisión muchos casos especiales. Si alguna vez existe una prueba sobre el ajedrez, probablemente requerirá que los lectores humanos acepten que una computadora verificó correctamente casos aún más especiales. Y bien puede ser que no haya un método más corto para probar esas declaraciones. Esos son problemas en PSPACE. Si un problema es "justo" en NP, entonces (intuitivamente) un ser humano podría tener toda la prueba en su cabeza. Ese humano podría necesitar ser un matemático muy especializado, por supuesto.

$n^{1000000}$

Además del comentario de Suresh, parece haber una gran diferencia en la práctica. Hay heurísticas que logran explotar la estructura de instancias prácticas de SAT y obtener un rendimiento excelente (aquí me refiero a los solucionadores de aprendizaje de cláusulas basadas en conflictos). La misma heurística no produce mejoras de rendimiento similares en los solucionadores QBF.

La diferencia entre prueba y verificación también aparece. Algunos solucionadores SAT (como MiniSAT 1.14 y muchos otros) producen pruebas. La producción de pruebas en solucionadores QBF actuales no es trivial. (La siguiente declaración es de rumores) Hay grandes instancias en la competencia QBF en las que los solucionadores aparentemente producen resultados diferentes. En ausencia de solucionadores que generen pruebas, no sabemos qué resultado es correcto.

Si observa el rendimiento práctico en SAT y ajedrez, entonces hay una diferencia: los problemas con NP completo son más manejables que los problemas con PSPACE completo. Los solucionadores de SAT de hoy pueden manejar más de mil variables, pero el mejor motor de ajedrez, en la misma cantidad de tiempo, solo puede calcular menos de 20 movimientos.

Supongo que esto se debe a la estructura de los problemas. Sí, si solo enumera soluciones, la resolución SAT es súper lenta. Pero debido a que no tiene la alternancia del cuantificador, las personas descubren estructuras en la fórmula y, por lo tanto, evitan gran parte de la enumeración. Creo que Ryan Williams pasó por alto este punto.

Con la alternancia del cuantificador, sí, existen métodos inteligentes de poda, pero aún así la estructura no es tan rica como la de una fórmula CNF.

Déjame predecir el futuro. La resolución SAT llegará a P al examinar la fórmula y esencialmente evitará la búsqueda, mientras que el ajedrez llegará a P al capitalizar la búsqueda en el árbol de juego.