フォーミュラゲーム

数式ゲームとは、次のような完全量化ブール式で表される人工的なゲームである。${\displaystyle \exists x_{1}\forall x_{2}\exists x_{3}\ldots \psi }$。

1人のプレイヤー（E）は、式を満たすように値を選択することを目標とする。${\displaystyle \psi }$真であり、存在量化されている変数に対して値を選択します。${\displaystyle \exists }$相手プレイヤー（A）の目標は、以下の式を完成させることである。${\displaystyle \psi }$false であり、普遍的に量化されている変数の値を選択します。${\displaystyle \forall }$プレイヤーは、量指定子の順序に従って順番に、元の数式における次の束縛変数に値を割り当てます。すべての変数に値が割り当てられた後、結果として得られる式が真であれば、プレイヤーEの勝ちとなります。

計算複雑性理論において、FORMULA-GAME言語はすべての式として定義される。${\displaystyle \Phi }$プレイヤーEは、ゲームにおいて以下の戦略で勝利する。${\displaystyle \Phi }$. FORMULA-GAME は、真の量化ブール式とまったく同じ決定問題であるため、PSPACE 完全です。プレイヤー E は、ゲームでプレイヤーが行わなければならないすべての選択に、次の真理値割り当てがある場合にのみ、勝利戦略を持ちます。${\displaystyle \psi }$プレイヤーAがどのような選択をしても、それは真実である。

• Sipser, Michael. (2006). 計算理論入門. ボストン: Thomson Course Technology.