Juego de fórmula

Un juego de fórmula es un juego artificial representado por una fórmula booleana totalmente cuantificada, como por ejemplo:${\displaystyle \exists x_{1}\forall x_{2}\exists x_{3}\ldots \psi }$.

Un jugador (E) tiene el objetivo de elegir valores de manera que se cumpla la fórmula.${\displaystyle \psi }$verdadero, y selecciona valores para las variables que se cuantifican existencialmente con${\displaystyle \exists }$El jugador contrario (A) tiene el objetivo de hacer la fórmula${\displaystyle \psi }$falso, y selecciona valores para las variables que se cuantifican universalmente con${\displaystyle \forall }$Los jugadores se turnan según el orden de los cuantificadores, asignando cada uno un valor a la siguiente variable ligada en la fórmula original. Una vez que todas las variables han recibido valores, el jugador E gana si la expresión resultante es verdadera.

En la teoría de la complejidad computacional , el lenguaje FORMULA-GAME se define como todas las fórmulas${\displaystyle \Phi }$de tal manera que el Jugador E tenga una estrategia ganadora en el juego representado por${\displaystyle \Phi }$. FORMULA-GAME es PSPACE-completo porque es exactamente el mismo problema de decisión que True quantified Boolean formula . El jugador E tiene una estrategia ganadora exactamente cuando cada elección que debe hacer en un juego tiene una asignación de verdad que hace que${\displaystyle \psi }$Es cierto, independientemente de la decisión que tome el Jugador A.

• Sipser, Michael. (2006). Introducción a la teoría de la computación . Boston: Thomson Course Technology.