¿Son los problemas completos

66

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

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?NPPSPACE

Alex ten Brink
fuente

Respuestas:

82

NPPSPACE

PSPACENPQBFPSPACESATNPPSPACENP

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(x1,,xn)nn

Φ1=(x1)(x2)(xn1)(xn)F(x1,,xn)

Φ2=(x1)(x2)(xn1(xn)F(x1,,xn)

Φ2

Φ1Φ2

Φ1NPΦ2PSPACEΦ2Φ1F2nΦ2FO(2.793n)

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.

Ryan Williams
fuente
16
Buena respuesta, y una toma interesante.
Suresh Venkat
Se me ocurre que lo anterior es un buen ejemplo de lo que queremos decir con "complejidad fina" (un programa de otoño de 2015 en el Instituto Simons). Una de las ideas clave es que la teoría de la complejidad puede verse bastante diferente cuando, en lugar de tratar de encontrar para cada problema un modelo computacional (potencialmente extraño) para el cual ese problema está "completo", uno simplemente se enfoca en comprender cuál es el mejor tiempo de ejecución posible exponente para el problema.
Ryan Williams
37

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 ' ' 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 ' ', 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.

Niel de Beaudrap
fuente
Creo que la pregunta es sobre la versión de "optimización" de los problemas NP-complete y PSPACE-complete. Por ejemplo, ¿hay alguna diferencia (en términos de complejidad) entre encontrar una solución para SAT y para QBF? Y, en general, ¿hay una caracterización de los problemas de optimización de qué versión de decisión es NP-complete o PSPACE-complete?
Lamine
@Lamine: No detecto la distinción que está haciendo en la pregunta (al menos, entre la mera decisión y la optimización total). Quizás quiere decir que el autor de la pregunta solo está interesado en la pregunta de los recursos necesarios para encontrar esa respuesta, y no está interesado en otras medidas de dificultad del problema, en cuyo caso estoy de acuerdo en que mi respuesta no responde a esta. En cualquier caso, arriba está mi respuesta a la pregunta tal como está.
Niel de Beaudrap
55
Muy buena respuesta.
Dave Clarke
La capacidad de verificar eficientemente no ayuda a calcular una solución (a menos que P = NP). NP y co-NP permiten atacar el problema a través de adivinar y verificar. Este enfoque es fácil de implementar e incluso puede ser más eficiente, pero no ayuda en el peor de los casos.
András Salamon
@ András: cierto, por lo tanto, mi énfasis en encontrar soluciones no es lo único importante en el prefacio de mi respuesta.
Niel de Beaudrap
36

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.

Lance Fortnow
fuente
20

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.

Suresh Venkat
fuente
11
Hay una competencia anual diseñada para mejorar los solucionadores de QBF . No los usé mucho.
Radu GRIGore
7

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.

n1000000

Aaron Sterling
fuente
¿Podría uno también argumentar que los problemas completos de coNP tienen el problema de (a veces) requerir una "prueba de computadora"?
Philip White
@Philip White: No creo que sea lo mismo. Decir "ajedrez un empate" está en coNP. Para decir que no, todo lo que tengo que hacer es demostrar una sola línea forzada que sea fácilmente verificable. Sin embargo, esperamos que, incluso si existe una línea de este tipo, probablemente sea muy difícil demostrar que de hecho está "forzando". Por lo tanto, el problema no garantiza la simplicidad si es solucionable en una dirección particular. "El ajedrez es un empate" probablemente requiere inherentemente una computadora para demostrar si es verdadero o falso.
Aaron Sterling
5

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.

Vijay D
fuente
0

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.

Zirui Wang
fuente