A formula game is an artificial game represented by a fully quantified Boolean formula.

true, and selects values for the variables that are existentially quantified false, and selects values for the variables that are universally quantified. The players take turns according to the order of the quantifiers, each assigning a value to the next bound variable in the original formula. Once all variables have been assigned values, Player E wins if the resulting expression is true.

In computational complexity theory. FORMULA-GAME is PSPACE-complete because it is exactly the same decision problem as True quantified Boolean formula true, no matter what choice Player A makes.

References

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