Formula game
Encyclopedia
A formula game is an artificial game represented by a fully quantified Boolean formula
. Players' turns alternate and the space of possible moves is denoted by bound variables. If a variable is universally quantified
, the formula following it has the same truth value as the formula beginning with the universal quantifier regardless of the move taken. If a variable is existentially quantified
, the formula following it has the same truth value as the formula beginning with the existential quantifier for at least one move available at the turn. Turns alternate, and a player loses if he cannot move at his turn. In computational complexity
theory, the language FORMULA-GAME is defined as all formulas
such that Player 1 has a winning strategy in the game represented by 
. FORMULA-GAME is PSPACE-complete
.
True quantified Boolean formula
In computational complexity theory, the language TQBF is a formal language consisting of the true quantified Boolean formulas. A quantified Boolean formula is a formula in quantified propositional logic where every variable is quantified , using either existential or universal quantifiers, at the...
. Players' turns alternate and the space of possible moves is denoted by bound variables. If a variable is universally quantified
Universal quantification
In predicate logic, universal quantification formalizes the notion that something is true for everything, or every relevant thing....
, the formula following it has the same truth value as the formula beginning with the universal quantifier regardless of the move taken. If a variable is existentially quantified
Existential quantification
In predicate logic, an existential quantification is the predication of a property or relation to at least one member of the domain. It is denoted by the logical operator symbol ∃ , which is called the existential quantifier...
, the formula following it has the same truth value as the formula beginning with the existential quantifier for at least one move available at the turn. Turns alternate, and a player loses if he cannot move at his turn. In computational complexity
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...
theory, the language FORMULA-GAME is defined as all formulas
such that Player 1 has a winning strategy in the game represented by . FORMULA-GAME is PSPACE-completePSPACE-complete
In complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be reduced to it in polynomial time...
.