В чем сложность этой игры?

10

Это обобщение моего предыдущего вопроса .

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

Рассмотрим следующую игру Алисы и Боба. Первоначально Алиса и Боб имеют мA и мВ долларов соответственно. Алиса хочет MA(Икс)знак равно1 а Боб хочет MA(Икс)знак равно0 .

На каждом этапе игры игрок может добавить некоторую строку Y в A ; это стоит е(Y) доллара, где е:{0,1}*N - вычислимая функция за полиномиальное время. Также игрок может пропустить свой шаг.

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

Вопрос: проблема определения победителя этой игры для данного M,е,Икс,мA,мВ является

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

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

В моем предыдущем вопросе добавление каждой строки к A стоит один доллар (т.е. е1 ). Тогда (как это было показано Ланс Фортноу ) эта игра принадлежит EXPH и даже PSPACE , если мAзнак равномВ .

Алексей Милованов
источник
Можете ли вы объяснить, почему вы внесли это изменение в проблему? Алиса может проверить, может ли она позволить себе заплатить за все строки в (как определено в ответе Ланса на вашу другую проблему) за полиномиальное время. Как это сразу не решает проблему? S
Стелла Бидерман
@StellaBiderman Алиса действительно может проверить это за полиномиальное время. Однако если ей не хватает денег, то теперь это не означает, что она может делать только полиномиальные шаги (как это было в предыдущей игре).
Алексей Милованов
Если она не может позволить себе , сможет ли она когда-нибудь победить противника, который всегда пропускает свой ход? Может быть, в настройке игры есть что-то, чего я не понимаю. S
Стелла Бидерман
1
@Stella Да, потому что они могут быть другими путями принятия. Например, предположим, что если , то M останавливается и принимает. В этом случае S = { x 1 } . Но если х 1 , то M может запросить х 2 и принять , если х 2 . В этом случае достаточно, если у Алисы достаточно спондуликса для х 2 . x1AMS={x1}Икс1AMИкс2Икс2AИкс2
domotorp

Ответы:

5

Это должно быть EXPSPACE-завершено. Я обрисую, как добиться экспоненциального числа чередований, не сводя к этому ни одной задачи, полной EXPSPACE, но отсюда все должно быть просто завершено.

Обозначим слова в оракуле после T округлений через AT , поэтому изначально A0знак равно . Обозначим слова, запрошенные через MAT через QT . Главное наблюдение состоит в том, что тот , кто теряет с AT , можно предположить , что добавить что - то от QT к A . Это потому, что в этой игре каждый ход стоит денег, мы хотим двигаться как можно меньше; нет смысла делать ход, пока мы не выиграем. Но это также подразумевает, что если мы проигрываем, нет смысла добавлять что-либо извне QT .

Для простоты предположим, что M выполняется ровно за 2N шагов, а на шагах 2я и 2я+1 он запрашивает слово длины ровно я . Функция стоимости е будет просто 2-я для слов длины я . Игра будет такой , что Алиса всегда нужно добавить нечетные слова длины и Боб всегда нужно добавить даже слов длины к A . Предположим, что N нечетно, а Алиса изначально проигрывает.

Бюджеты мA и мВ будет установлен так , что она может выбрать только один из длины N слов запрашивать с помощью MA0 , чтобы быть добавлены к A . Игра будет такой, что это сделает ее победителем, поэтому Бобу придется двигаться. Опять же из - за бюджетных ограничений, он должен будет выбрать именно один из длины N-1 слова опрашивается MA1 , которые будут добавлены к A . После добавления любого из них MA2 запросит два новых слова длиной N (одинаковые, независимо от того, к какому слову Боб добавлен)A ) и Боб победит. Алиса будет вынуждена добавить ровно один из этих новой длиныN словA , чтобы сделать ее выиграть.

Игра продолжается таким образом, который можно представить как следование ветвям полного бинарного дерева глубины N , хотя в каждом ветвящемся узле один из игроков (определяется по которому по четности глубины узла) должен сделать выбор о том, какое слово , чтобы добавить к A . После того, как они пройдут по дереву, у них закончится бюджет. Если на каком-либо этапе игры один из них решает добавить какое-то слово, которое короче (например, Алиса длиной К<N слова из Q0на первом шаге), затем, если другой игрок (в нашем примере Боб) просто играет всегда самое длинное слово, которое он может в двоичном дереве, у него останется немного денег в конце, и мы сделаем игру, чтобы он мог использовать это побеждать. (Обратите внимание, что у Алисы также может быть немного денег, но у Боба их будет больше, поэтому мы разрабатываем конечную игру так, чтобы, если у одного из них было больше денег, этот игрок мог выиграть.)

Таким образом, Алиса решает экспоненциально много пар слов нечетной длины, а Боб - экспоненциально много слов четной длины, которые из каждой пары идут в A , и они делают этот выбор поочередно.

domotorp
источник
Спасибо за ваш ответ. Я задал вам несколько вопросов по электронной почте.
Алексей Милованов