Juego de las fórmulas

En teoría de la complejidad computacional, el juego de las fórmulas es un juego artificial representado por una fórmula booleana totalmente cuantificada. Los turnos de los jugadores se alternan y el espacio de movimientos posibles se denota mediante variables ligadas. Si una variable se cuantifica universalmente, la fórmula que sigue tiene el mismo valor de verdad que la fórmula que comienza con el cuantificador universal, independientemente del movimiento realizado. Si una variable se cuantifica existencialmente, la fórmula siguiente tiene el mismo valor de verdad que la fórmula que comienza con el cuantificador existencial para al menos un movimiento disponible en el turno. Los turnos se alternan y un jugador pierde si no puede moverse en su turno.

El lenguaje FÓRMULA-GAME definido como todas las fórmulas $\Phi$ tal que el Jugador 1 tenga una estrategia ganadora, es PSPACE-completo.

Referencias

• Sipser, Michael. (2006). Introduction to the Theory of Computation. Boston: Thomson Course Technology.

• Datos: Q5470340