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:
“Ideals possess the strange quality that if they were completely realized they would turn into nonsense. One could easily follow a commandment such as “Thou shalt not kill” to the point of dying of starvation; and I might establish the formula that for the proper functioning of the mesh of our ideals, as in the case of a strainer, the holes are just as important as the mesh.”
—Robert Musil (1880–1942)
“I have a notion that gamblers are as happy as most people, being always excited; women, wine, fame, the table, even ambition, sate now & then, but every turn of the card & cast of the dice keeps the gambler alive—besides one can game ten times longer than one can do any thing else.”
—George Gordon Noel Byron (1788–1824)