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:
“So, if we must give a general formula applicable to all kinds of soul, we must describe it as the first actuality [entelechy] of a natural organized body.”
—Aristotle (384–323 B.C.)
“The family environment in which your children are growing up is different from that in which you grew up. The decisions our parents made and the strategies they used were developed in a different context from what we face today, even if the “content” of the problem is the same. It is a mistake to think that our own experience as children and adolescents will give us all we need to help our children. The rules of the game have changed.”
—Lawrence Kutner (20th century)