Это обобщение моего предыдущего вопроса .
Пусть будет полиномиальный детерминированный машина , которая может задавать вопросы некоторым оракулом . Первоначально пусто, но это можно изменить после игры, которая будет описана ниже. Позвольте x быть некоторой строкой.
Рассмотрим следующую игру Алисы и Боба. Первоначально Алиса и Боб имеют и долларов соответственно. Алиса хочет а Боб хочет .
На каждом этапе игры игрок может добавить некоторую строку в ; это стоит доллара, где - вычислимая функция за полиномиальное время. Также игрок может пропустить свой шаг.
Игра заканчивается, если оба игрока тратят все деньги или если какой-то игрок пропустил шаг, когда он или она в проигрышной позиции (что определяется текущим значением ).
Вопрос: проблема определения победителя этой игры для данного является
EXPSPACE -полное задание?
Обратите внимание , что может спросить (за принадлежность к ) только строкам полиномиальной длины , так что нет смысла Алисы или Боб , чтобы добавить более длинные строки в . Следовательно, эта проблема находится в EXPSPACE .
В моем предыдущем вопросе добавление каждой строки к стоит один доллар (т.е. ). Тогда (как это было показано Ланс Фортноу ) эта игра принадлежит EXPH и даже PSPACE , если .
источник
Ответы:
Это должно быть EXPSPACE-завершено. Я обрисую, как добиться экспоненциального числа чередований, не сводя к этому ни одной задачи, полной EXPSPACE, но отсюда все должно быть просто завершено.
Обозначим слова в оракуле послеT округлений через AT , поэтому изначально A0= ∅ . Обозначим слова, запрошенные через MAT через QT . Главное наблюдение состоит в том, что тот , кто теряет с AT , можно предположить , что добавить что - то от QT к A . Это потому, что в этой игре каждый ход стоит денег, мы хотим двигаться как можно меньше; нет смысла делать ход, пока мы не выиграем. Но это также подразумевает, что если мы проигрываем, нет смысла добавлять что-либо извне QT .
Для простоты предположим, чтоM выполняется ровно за 2 н шагов, а на шагах 2 я и 2 я + 1 он запрашивает слово длины ровно я . Функция стоимости е будет просто 2- я для слов длины я . Игра будет такой , что Алиса всегда нужно добавить нечетные слова длины и Боб всегда нужно добавить даже слов длины к A . Предположим, что N нечетно, а Алиса изначально проигрывает.
БюджетымA и мВ будет установлен так , что она может выбрать только один из длины N слов запрашивать с помощью MA0 , чтобы быть добавлены к A . Игра будет такой, что это сделает ее победителем, поэтому Бобу придется двигаться. Опять же из - за бюджетных ограничений, он должен будет выбрать именно один из длины n - 1 слова опрашивается MA1 , которые будут добавлены к A . После добавления любого из них MA2 запросит два новых слова длиной N (одинаковые, независимо от того, к какому слову Боб добавлен)A ) и Боб победит. Алиса будет вынуждена добавить ровно один из этих новой длиныN словA , чтобы сделать ее выиграть.
Игра продолжается таким образом, который можно представить как следование ветвям полного бинарного дерева глубиныN , хотя в каждом ветвящемся узле один из игроков (определяется по которому по четности глубины узла) должен сделать выбор о том, какое слово , чтобы добавить к A . После того, как они пройдут по дереву, у них закончится бюджет. Если на каком-либо этапе игры один из них решает добавить какое-то слово, которое короче (например, Алиса длиной к < п слова из Q0 на первом шаге), затем, если другой игрок (в нашем примере Боб) просто играет всегда самое длинное слово, которое он может в двоичном дереве, у него останется немного денег в конце, и мы сделаем игру, чтобы он мог использовать это побеждать. (Обратите внимание, что у Алисы также может быть немного денег, но у Боба их будет больше, поэтому мы разрабатываем конечную игру так, чтобы, если у одного из них было больше денег, этот игрок мог выиграть.)
Таким образом, Алиса решает экспоненциально много пар слов нечетной длины, а Боб - экспоненциально много слов четной длины, которые из каждой пары идут вA , и они делают этот выбор поочередно.
источник