Пусть будет полиномиальный детерминированный машина , которая может задавать вопросы некоторым оракулом А . Первоначально A пусто, но это можно изменить после игры, которая будет описана ниже. Позвольте x быть некоторой строкой.
Рассмотрим следующую игру Алисы и Боба. Первоначально Алиса и Боб имеют и m B долларов соответственно. Алиса хочет M A ( x ) = 1, а Боб хочет M A ( x ) = 0 .
На каждом этапе игры игрок может добавить одну строку в ; это стоит один доллар. Также игрок может пропустить свой шаг.
Игра заканчивается, если оба игрока тратят все деньги или если какой-то игрок пропустил шаг, когда он или она в проигрышной позиции (что определяется текущим значением ).
Вопрос: проблема определения победителя этой игры для данного является
EXPSPACE -полное задание?
Обратите внимание , что может спросить (за принадлежность к А ) только строкам полиномиальной длины , так что нет смысла Алисы или Боб , чтобы добавить более длинные строки в А . Следовательно, эта проблема находится в EXPSPACE .
источник