Английская Википедия:Formula game

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

A formula game is an artificial game represented by a fully 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 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 with <math>\forall</math>. 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, 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 because it is exactly the same decision problem as 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.

Шаблон:Comp-sci-stub