Игра для 2 игроков - полиномиальное пространство завершено

Question

Таким образом, есть игровое поле для беспокойства, и каждое место на доске имеет целое число.Первый игрок выбирает номер из строки 1, а второй игрок выбирает номер из строки 2, и они чередуются до тех пор, пока не останется больше строк.Затем они складывают все числа и игрок 1 выигрывает, если сумма равна предварительно определенной сумме S, в противном случае игрок 2 выигрывает.Стратегия выигрыша для игрока 1 для определенной доски и суммы (B, S) заключается в том, если игрок 1 может выиграть независимо от того, что делает игрок 2.Я хочу показать, что эта проблема полна PSpace

Итак, сначала я должен показать, что она в PSpace, что, на мой взгляд, довольно просто, потому что общее количество ходов связано с размером доски, чтоэто п ^ 2.

Я застреваю, когда показываю, что это сложно для PSpace, хотя я знаю, что мне нужно переходить с QSAT, но я не могу понять, как.Кто-то может помочь?

РЕДАКТИРОВАТЬ: Ну, на самом деле я не знаю, что я должен сократить с QSAT, но после поиска вокруг, кажется, что QSAT является наиболее вероятным кандидатом.Многие другие игры для двух игроков, география которых является наиболее ярким примером, уменьшают QSAT, поэтому я решил, что это тоже нужно.Однако не стесняйтесь поправлять меня, если я ошибаюсь по этому поводу.

Answer 1

Если вы выбираете сокращение от QSAT, ваша задача начинается с формулы.

Вам необходимо создать экземпляр вашей игры, чтобы отрицание этой формулы было тавтологией именно в том случае, если у игрока 1 есть выигрышная стратегия. Роль игрока 2 заключается прежде всего в том, чтобы фиксировать оценки универсально количественных булевых переменных; игрок 1 играет аналогичную роль в отношении экзистенциально количественных булевых переменных.

Вам нужно проявить изобретательность при заполнении стола, чтобы игрок 1 мог получить только нулевую сумму в случае тавтологии. Также убедитесь, что количество необходимых вам строк таблицы является линейным по числу вхождений кванторов в формуле.

[SPOILER 1 запускается] Помните, что мы обсуждаем в режиме домашней работы. Теперь я добавлю почти все детали к подсказке, но скрою три технических недостатка в решении, которое, как я ожидаю, вы найдете, как только вы поймете детали. Пожалуйста, постарайтесь найти как можно больше и предложить свои исправления как можно большему в комментарии.

Сначала посмотрите на QSAT в терминах теории игр. Без ограничения общности предположим, что количественное булево предложение (формула без свободных переменных) записано со всеми квантификаторами впереди; сначала несколько экзистенциально квантифицированных переменных, затем несколько универсальных, затем еще один блок экзистенциальных и так далее. Первый игрок начинает играть, присваивая (подставляя) определенные логические значения первым нескольким экзистенциально количественным переменным (всему первому блоку, останавливаясь только тогда, когда формула после замены начинается с крайнего левого универсального квантификатора. Затем игрок 2 обрабатывает первый блок универсального квантификация также: тогда игрок 1 продолжает то, что первоначально было вторым блоком экзистенциальной квантификации и т. д. Игрок 1 выигрывает, если формула, после того, как все переменные были определены, оценивается как «истина», в противном случае игрок 2 выигрывает.

В эту игру QSAT также можно играть численно, если вы предполагаете некоторое кодирование формул, чтобы каждая формула имела уникальный номер на основе синтаксиса (чтобы можно было эффективно определить число из формулы, а также формулу из числа) , Вместо обмена формулами игроки будут обмениваться числами (кодами формул).

Теперь представьте, что мы хотим преобразовать эту QSAT-подобную игру в вашу настольную игру. Каждый ряд будет обозначать ход одного игрока (для одного блока квантификаторов одного типа). Каждое место в ряду будет представлять возможный ход этого игрока из любой позиции в предыдущем ряду; более конкретно, числовая разница , созданная ходом: код формулы после перемещения минус код формулы перед перемещением. Таким образом, промежуточный итог всегда равен формуле в том виде, в каком он есть на данном этапе игры.

В качестве специального исключения измените все местоположения в последнем ряду, дополнительно вычитая код формулы true. Таким образом, общая сумма завершенной настольной игры будет равна 0, если игрок 1 выиграл, и ненулевой в противном случае. Это желаемое снижение количественной формулы тавтологичности для вашей настольной игры. [СПОЙЛЕР 1 заканчивается]