¿Esta variación de TQBF todavía está completa en PSPACE?

31

Decidir si una fórmula booleana cuantificada como

X1X2X3Xnorteφ(X1,X2,...,Xnorte),

siempre se evalúa como verdadero es un problema clásico completo de PSPACE. Esto puede verse como un juego entre dos jugadores, con movimientos alternos. El primer jugador decide el valor de verdad de las variables impares y el segundo jugador decide el valor de verdad de las variables pares. El primer jugador intenta hacer que φ falso y el segundo jugador intenta que sea verdadero. Decidir quién tiene una estrategia ganadora es PSPACE completo.

Estoy pensando en un problema similar con dos jugadores, uno tratando de hacer una fórmula booleana φ verdadera y la otra tratando de hacer que sea falsa. La diferencia es que en un movimiento, un jugador puede elegir una variable y un valor de verdad (por ejemplo, como el primer movimiento, el jugador uno podría decidir establecer X8 en verdadero y luego, en el siguiente movimiento, el jugador dos podría decida establecer X3 en falso). Esto significa que los jugadores pueden decidir cuál de las variables (de aquellas a las que aún no se les ha asignado un valor de verdad) quieren asignar un valor de verdad, en lugar de tener que jugar el juego en el orden X1,...,Xnorte .

Al problema se le da una fórmula booleana φ en variables para decidir si el jugador uno (tratando de hacerlo falso) o el jugador dos (tratando de hacerlo verdadero) tiene una estrategia ganadora. Claramente, este problema todavía está en PSPACE, ya que el árbol del juego tiene una profundidad lineal.norte

¿Sigue siendo PSPACE completo?

JWM
fuente

Respuestas:

35

Es un juego de Satisfacción de restricciones no ordenadas y es completo para PSPACE y recientemente se ha demostrado que es completo para PSPACE ; Se puede encontrar una prueba en:

Lauri Ahlroth y Pekka Orponen, Juegos de satisfacción de restricciones no ordenadas . Lecture Notes in Computer Science Volume 7464, 2012, pp 64-75.

Abstracto:Consideramos juegos de satisfacción de restricciones de dos jugadores en sistemas de restricciones booleanas, en los que los jugadores se turnan para seleccionar una de las variables disponibles y establecerla en verdadero o falso, con el objetivo de maximizar (para el Jugador I) o minimizar (para el Jugador II) el número de restricciones satisfechas. A diferencia de los juegos de asignación de variables de tipo QBF estándar, no imponemos ningún orden en el que se jueguen las variables. Esto hace que la configuración del juego sea más natural, pero también más difícil de controlar. Proporcionamos estrategias de aproximación de factor constante y tiempo polinómico para el jugador I cuando las restricciones son funciones de paridad o funciones de umbral con un umbral pequeño en comparación con la aridad de las restricciones. Además, demostramos que el problema de determinar si el jugador I puede satisfacer todas las restricciones es PSPACE completo incluso en esta configuración desordenada,

Del contenido:


do={do1,...,dometro}X={X1,...,Xnorte}do

Un juego en continúa para que en cada turno el jugador se mueva, seleccione una de las variables no seleccionadas previamente y le asigne un valor de verdad. El jugador I comienza y el juego termina cuando todas las variables tienen asignado un valor. En la versión de decisión de GBF , la pregunta es si el Jugador I tiene una estrategia ganadora integral, mediante la cual puede satisfacer todas las cláusulas sin importar lo que haga el Jugador II. En el caso positivo, decimos que la instancia es compatible con GBF. ..do

... Teorema 4 : El problema de decidir la satisfacción de GBF de una fórmula booleana es PSPACE-complete.

EDITAR : Daniel Grier ha descubierto que el resultado también fue resuelto por Schaefer en los años 70, consulte su respuesta en esta página para obtener la referencia (y votarlo :-). Schaefer demostró que el juego aún está completo para PSPACE, incluso si está restringido a fórmulas CNF positivas (es decir, fórmulas proposicionales en forma conjuntiva normal en la que no se producen variables negadas) con un máximo de 11 variables en cada conjunción.

Marzio De Biasi
fuente
27

También puede valer la pena señalar que este problema también fue resuelto en los años 70 por Thomas Schaefer en  Complejidad de los problemas de decisión basados ​​en juegos finitos de información perfecta para dos personas . De hecho, demuestra un resultado ligeramente más fuerte en que el lenguaje permanece completo en PSPACE incluso cuando está restringido a fórmulas positivas de CNF.

Daniel Grier
fuente
2
¡Interesante! (¿Ahlroth y Orponen no lo sabían? Por cierto, citan otro artículo de Schaefer: sobre la complejidad de algunos juegos de información perfecta para dos personas (1978) que contiene los conocidos resultados de integridad de PSPACE de Geography y Node-Kayles). ¿Hay una copia gratuita del documento disponible? (el vinculado está más allá de paywall).
Marzio De Biasi
Lamentablemente, no lo creo. Recuerdo que una vez intenté encontrar una copia que no estaba detrás de un muro de pago durante algún tiempo con poco éxito.
Daniel Grier
Por cierto, ¡felicidades por tu buen resultado en la integridad de PSPACE de Poset Games!
Marzio De Biasi
Por lo que puedo decir, el documento de 1978 (Sobre la complejidad de algunas personas ...) es la versión de revista del artículo STOC de 1976 (Complejidad de los problemas de decisión ...), que cita.
András Salamon
10

Probamos que este juego es completo para PSPACE para 5-CNF pero tiene un algoritmo de tiempo lineal para 2-CNF. El mejor resultado anterior fue el 6-CNF de Ahlroth y Orponen.

Puede encontrar el documento de la conferencia en ISAAC 2018 .

Actualización: 16 de noviembre de 2019

Probamos que el juego es manejable para 3-CNF bajo algunas restricciones sobre 3-CNF. También conjeturamos radicalmente que este juego también es manejable sin restricciones en 3-CNF. Puede encontrar la versión inicial en ECCC .

Lutfar Rahman Milu
fuente