• Source: Formula game

      • A formula game is an artificial game represented by a fully quantified Boolean formula such as



      ∃

      x

      1


      ∀

      x

      2


      ∃

      x

      3


      …
      ψ


      {\displaystyle \exists x_{1}\forall x_{2}\exists x_{3}\ldots \psi }

      .
      One player (E) has the goal of choosing values so as to make the formula



      ψ


      {\displaystyle \psi }

      true, and selects values for the variables that are existentially quantified with



      ∃


      {\displaystyle \exists }

      . The opposing player (A) has the goal of making the formula



      ψ


      {\displaystyle \psi }

      false, and selects values for the variables that are universally quantified with



      ∀


      {\displaystyle \forall }

      . 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



      Φ


      {\displaystyle \Phi }

      such that Player E has a winning strategy in the game represented by



      Φ


      {\displaystyle \Phi }

      . 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



      ψ


      {\displaystyle \psi }

      true, no matter what choice Player A makes.


      References


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

    Kata Kunci Pencarian: