Decidir si una fórmula booleana cuantificada como
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 en verdadero y luego, en el siguiente movimiento, el jugador dos podría decida establecer 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 .
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.
¿Sigue siendo PSPACE completo?
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 .
fuente