Формула игры

Игра -формула — это искусственная игра, представленная полностью количественной логической формулой, такой как $\exists x_{1}\forall x_{2}\exists x_{3}\ldots \psi$.

Один игрок (E) имеет цель выбрать значения, чтобы составить формулу $\psi$ true, и выбирает значения для переменных, которые экзистенциально определены с помощью $\exists$. Противостоящий игрок (А) имеет цель составить формулу $\psi$ false, и выбирает значения для переменных, которые имеют универсальную количественную оценку с помощью $\forall$. Игроки ходят по очереди в соответствии с порядком кванторов, каждый из которых присваивает значение следующей связанной переменной в исходной формуле. Как только всем переменным будут присвоены значения, игрок E выигрывает, если полученное выражение истинно.

В теории сложности вычислений язык ФОРМУЛА-ИГРА определяется как все формулы $\Phi$ так что у игрока E есть выигрышная стратегия в игре, представленная $\Phi$. FORMULA-GAME является PSPACE-полной , поскольку это точно такая же проблема принятия решения, что и истинная количественная булева формула . Игрок Е имеет выигрышную стратегию именно тогда, когда каждый выбор, который он должен сделать в игре, имеет истинное задание, которое делает $\psi$ верно, независимо от того, какой выбор сделает Игрок А.

Ссылки

• Сипсер, Майкл. (2006). Введение в теорию вычислений . Бостон: Технология курса Томсона.