Изменения

[[Файл:Generalized_geography_1.png|thumb|350px| Рис. 1. Граф для игры в города в штате Мичиган]]

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

[[Файл:Generalized_geography_2.png|thumb|350px| Рис. 2. Пример графа для игры в Generalized Geography]]

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

Язык <tex> GG = \{ <\langle G, b\rangle | </tex> | первый игрок в графе <tex> G</tex>, начиная игру с вершины <tex> b</tex>, обладает выигрышной стратегией <tex> \} </tex> является [[Класс_PS|PS-полным]].

Алгоритм <tex> M(<\langle G,vb \rangle ) </tex>):

Для доказательства этого факта сведем задачу об игре двух игроков ∃ и ∀ в о выполнимости булевой КНФ-формуле формулы с предваряющими кванторами (эта задача [[Класс_PS|PS-трудная]]) к Generalized Geography за полиномиальное время. Для этого рассмотрим задачу о выполнимости КНФ-формулы с предваряющими кванторами как [[Интерпретация_БФ_с_кванторами_как_игры_для_двух_игроков|игру двух игроков <tex> \exists </tex> и <tex> \forall </tex>]].

Для игры двух игроков ∃ и ∀ наша формула представима Если в следующем виде: φ = ∃''x''нашей формуле с предваряющими кванторами последний квантор - не <subtex>1\exists </subtex> ∀''x'', то добавим его, введя дополнительную переменную. Таким образом для игры двух игроков <subtex>2\exists </subtex> ∃''x''и <subtex>3\forall </subtex> наша формула представима в следующем виде:<tex> \varphi = \exists x_1 \forall x_2 \exists x_3 ...∃''x\exists x_n ( \psi ) <sub/tex>n, где <tex> \psi </subtex>''(ψ) , где ψ - некая КНФ-формула.

[[Файл:Generalized_geography_3.png|thumb|350px| Рис. 3. Модель графа для сведения задачи об игре двух игроков ∃ <tex> \exists </tex> и ∀ <tex> \forall </tex> к задаче GG]]

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

Левый столбец в этом графе описывает процедуру выборки игроками ∃ <tex> \exists </tex> и ∀ <tex> \forall </tex> значений переменных, если игрок выбирает TRUE, он идет в левую сторону, иначе в правую.

Зафиксировав значения переменных, игрок ∀ <tex> \forall </tex> (т.к. в нашей КНФ-формуле с предваряющими кванторами последний квантор ∃<tex> \exists </tex>) выбирает скобку, значение которой должно быть FALSE (тогда он выиграет!). На рисунке каждая скобка - отдельная вершина c<subtex>ic_i </subtex>.

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

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

Мы свели задачу об игре игроков ∃ <tex> \exists </tex> и ∀ <tex> \forall </tex> к задаче Generalized Geography. Очевидно, сведение будет произведено за полиномиальное время. Значит, язык <tex> GG </tex> является PS-трудным, а так как выше мы доказали его принадлежность классу PS, то и PS-полным. == Внешние ссылки == [http://en.wikipedia.org/wiki/Generalized_geography Generalized Geography в английской википедии. ]