Изменения

Для визуализации задачи можно построить ориентированный граф, где каждая вершина - имя города, а ориентированное ребро из А в Б означает, что город Б начинается на ту же букву, на которую заканчивается город А. Ход игрока - переход из текущей вершины в новую, ранее не посещенную, по соответствующему ребру. Проигрывает тот, кто не может сделать ни одного перехода. Например, граф для игры в городки города в штате Мичиган может выглядеть так:

Рассмотрим пример такой игры. Пусть P1 - игрок, который ходит первым, и P2 - игрок, который ходит вторым. Игра начинается с первой вершины. Здесь первый игрок P1 обладает следующей выигрышной стратегией(игра начинается с первой вершины): делает ход в вершину 2, после чего второй игрок P2 переходит в вершину 4, так как это единственный вариант. Первый игрок ходит в вершину 5, и второй выбирает между вершинами 3 и 7. Но независимо от выбора второго игрокаP2, первый P1 может перейти в вершину 9, откуда второй игрок никуда не может пойти.

Чтобы показать, что задача язык принадлежит классы классу PS, предъявим алгоритм, работающий на полиномиальной памяти, определяющий, обладает ли игрок выигрышной стратегией находясь в вершине v графа G.

Для доказательства этого факта сведем задачу о выполнимости об игре двух игроков ∃ и ∀ в булевой формулы КНФ-формуле с предваряющими кванторами в форме КНФ (эта задача PS-трудная) к Generalized Geography за полиномиальное время. Для этого воспользуемся тем, что булеву формулу с кванторами можно интерпретировать как игру двух игроков ∃ и ∀.

Булева формула с кванторами имеет следующий вид: φ = Q₁''x''₁ Q₂''x''₂ Q₃''x''₃ ...''Q_kx_k''(ψ) где ''Q_i'' квантор Для игры двух игроков ∃ или и ∀, а ψ - некоторая булева наша формула. Заметим, что любую такую формулу можно преобразовать к виду представима в следующем виде: φ = ∃''x''₁ ∀''x''₂ ∃''x''₃ ...∃''x_n''(ψ) , добавив необходимое количество переменных с кванторами. Представим получившуюся формулу как игру игроков ∃ и ∀. Игрок ∃ здесь где ψ - первый игрок в Generalized Geography, а игрок ∀ некая КНФ- второй. Таким образом, если ∃ выигрывает в своей игре, то первый игрок обладает выигрышной стратегией в игре Generalized Geography. Осталось по булевой формуле с предваряющими кванторами получить соотвествующий граф для игры в Generalized Geographyформула.

Для любой такой КНФ-формулы с предваряющими кванторами можно построить граф, аналогичный графу, приведенному на рисунке. Рассмотрим этот граф, и докажем, что это сведение задачи о выполнимости булевой формулы об игре игроков ∃ и ∀ к задаче Generalized Geography.

После того, как игрок ∀ зафиксировал скобку, игрок ∃ долджен выбрать переменную, значение которой не ноль (игроки уже зафиксировали значения переменных в самом начале) и сделать переход в соответсвующую вершинку. Т.к. значение этой переменной не ноль, то игрок ∀ не сможет никуда пойти из этой вершины (тогда ∃ выиграл, первый игрок обладает выигрышной стратегией в игре Generalized Geography). Для этого проведем ребра из каждый скобки c_i в вершины-переменные, противоположные выбору учавствующие в этой скобке, а от них проведем ребра к вершинам левого столбца, соответсвующим выборам TRUE или FALSE значений переменных.

Таким образом, если игрок ∃ выигрывает, то автоматически обладает выигрышной стратегией и первый игрок в Generalized Geography. Он знает, какие значения переменных надо выбрать, и в какую вершину пойти в конце. Аналогично, по выигрышной стратегии первого игрока в Generalized Geography можно узнать, какие значения переменных должен выбрать игрок ∃ для того, чтобы формула выполниласьудовлетворить формулу.

Мы свели задачу о выполнимости булевой формулы с предваряющими кванторами об игре игроков ∃ и ∀ к задача задаче Generalized Geography. Значит, язык GG является PS-трудным, а так как выше мы доказали его принадлежность классу PS, то и PS-полным.