# Formula game

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Formula_game
> Markdown URL: https://mediated.wiki/source/Formula_game.md
> Source: https://en.wikipedia.org/wiki/Formula_game
> Source revision: 1194426861
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

A '''formula game''' is an artificial game represented by a [fully quantified Boolean formula](/source/True_quantified_Boolean_formula) such as <math>\exists x_1 \forall x_2 \exists x_3 \ldots \psi</math>.

One player (E) has the goal of choosing values so as to make the formula <math>\psi</math> true, and selects values for the variables that are [existentially quantified](/source/Existential_quantification) with <math>\exists</math>.  The opposing player (A) has the goal of making the formula <math>\psi</math> false, and selects values for the variables that are [universally quantified](/source/Universal_quantification) with <math>\forall</math>.  The players take turns according to the order of the quantifiers, each assigning a value to the next [bound variable](/source/bound_variables) in the original formula.  Once all variables have been assigned values, Player E wins if the resulting expression is true.

In [computational complexity theory](/source/computational_complexity_theory), the language FORMULA-GAME is defined as all formulas <math>\Phi</math> such that Player E has a winning strategy in the game represented by <math>\Phi</math>. FORMULA-GAME is [PSPACE-complete](/source/PSPACE-complete) because it is exactly the same decision problem as [True quantified Boolean formula](/source/True_quantified_Boolean_formula).  Player E has a winning strategy exactly when every  choice they must make in a game has a truth assignment that makes <math>\psi</math> true, no matter what choice Player A makes.

==References==

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

Category:Satisfiability problems
Category:Boolean algebra
Category:PSPACE-complete problems

{{comp-sci-stub}}

---
Adapted from the Wikipedia article [Formula game](https://en.wikipedia.org/wiki/Formula_game) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Formula_game?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.