Эта игра EXPSPACE-завершена?

10

Пусть будет полиномиальный детерминированный машина , которая может задавать вопросы некоторым оракулом А . Первоначально A пусто, но это можно изменить после игры, которая будет описана ниже. Позвольте x быть некоторой строкой.MAAx

Рассмотрим следующую игру Алисы и Боба. Первоначально Алиса и Боб имеют и m B долларов соответственно. Алиса хочет M A ( x ) = 1, а Боб хочет M A ( x ) = 0 .mAmBMA(x)=1MA(x)=0

На каждом этапе игры игрок может добавить одну строку в ; это стоит один доллар. Также игрок может пропустить свой шаг.A

Игра заканчивается, если оба игрока тратят все деньги или если какой-то игрок пропустил шаг, когда он или она в проигрышной позиции (что определяется текущим значением ).MA(x)

Вопрос: проблема определения победителя этой игры для данного являетсяM,x,mA,mB

EXPSPACE -полное задание?

Обратите внимание , что может спросить (за принадлежность к А ) только строкам полиномиальной длины , так что нет смысла Алисы или Боб , чтобы добавить более длинные строки в А . Следовательно, эта проблема находится в EXPSPACE . MAA

Алексей Милованов
источник

Ответы:

7

MΣ(x)SSmA

Лэнс Фортноу
источник