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.
Famous quotes containing the words formula and/or game:
“Hidden away amongst Aschenbach’s writing was a passage directly asserting that nearly all the great things that exist owe their existence to a defiant despite: it is despite grief and anguish, despite poverty, loneliness, bodily weakness, vice and passion and a thousand inhibitions, that they have come into being at all. But this was more than an observation, it was an experience, it was positively the formula of his life and his fame, the key to his work.”
—Thomas Mann (18751955)
“Wild Bill was indulging in his favorite pastime of a friendly game of cards in the old No. 10 saloon. For the second time in his career, he was sitting with his back to an open door. Jack McCall walked in, shot him through the back of the head, and rushed from the place, only to be captured shortly afterward. Wild Bill’s dead hand held aces and eights, and from that time on this has been known in the West as “the dead man’s hand.””
—State of South Dakota, U.S. public relief program (1935-1943)