== Формулировка задачи==
Городки [[Файл:Generalized_geography_1.png|thumb|350px| Рис. 1. Граф для игры в города в штате Мичиган]] Города (Geography) - игра, в которой игроки по очереди называют города со всего мира. Каждый город должен начинаться с той буквы, на которую заканчивается предыдущий. Повторы , повторы запрещены. Игра начинается с любого города, и заканчивается, когда игрок проигрывает и не может назвать новый город.
=== Графическая модель ===
Для визуализации задачи можно построить ориентированный граф, где каждая вершина - имя города, а ребро из А в Б означает, что город Б начинается на ту же букву, на которую заканчивается город А. Ход игрока - переход из текущей вершины в новую, ранее не посещенную, по соответствующему ребру. Проигрывает тот, кто не может сделать ни одного перехода. Ниже приведен пример такого графа для игры в городки в штате Мичиган.
РисунокДля визуализации задачи можно построить ориентированный граф, где каждая вершина - имя города, а ориентированное ребро из А в Б означает, что город Б начинается на ту же букву, на которую заканчивается город А. Ход игрока - переход из текущей вершины в новую, ранее не посещенную, по соответствующему ребру. Проигрывает тот, кто не может сделать ни одного перехода (см. рис. 1).
В обобщенных городках (Generalized Geography) используется любой ориентированный граф[[Файл:Generalized_geography_2. Игроки по очереди переходят из вершины в вершину, и проигрывает тот, кто не может сделать новый ходpng|thumb|350px| Рис.Пусть P1 - игрок, который ходит первым, и P2 - игрок, который ходит вторым. В приведенном ниже примере первый игрок имеет следующую выигрышную стратегию(изначально находится в вершине 1): переходит в вершину 2, после чего второй игрок переходит в вершину 4, так как это единственный вариант. Первый игрок переходит Пример графа для игры в вершину 5, и второй выбирает между вершинами 3 и 7. Но независимо от выбора второго игрока, первый переходит в вершину 9, откуда второй игрок никуда не может пойти.Generalized Geography]]
РисунокВ игре 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-полнаполным]].
== Доказательство ==
=== Доказательство принадлежности задачи классу PS ===
Чтобы показать, что задача язык принадлежит классы классу PS, предъявим алгоритм, работающий на полиномиальной памяти, определяющий, обладает ли игрок выигрышной стратегией находясь в вершине v графа G.
Алгоритм <tex> M(<\langle G,vb \rangle ) </tex>):
1. Если из вершины, в которой находится игрок, не ведет ни одного ребра в непосещенные ранее вершины, то вернем FALSE, мы проиграли.
=== Доказательство принадлежности задачи классу PSH ===
Для доказательства этого факта сведем задачу о выигрывании игрока Существует в выполнимости булевой КНФ-формуле формулы с пердворяющими предваряющими кванторами(эта задача [[Класс_PS|PS-трудная]]) к Generalized Geography за полиномиальное время. Для этого рассмотрим задачу о выполнимости КНФ-формулы с предваряющими кванторами как [[Интерпретация_БФ_с_кванторами_как_игры_для_двух_игроков|игру двух игроков <tex> \exists </tex> и <tex> \forall </tex>]]. Если в нашей формуле с предваряющими кванторами последний квантор - не <tex> \exists </tex>, то добавим его, введя дополнительную переменную. Таким образом для игры двух игроков <tex> \exists </tex> и <tex> \forall </tex> наша формула представима в следующем виде:<tex> \varphi = \exists x_1 \forall x_2 \exists x_3 ... \exists x_n ( \psi ) </tex> , где <tex> \psi </tex> - некая КНФ-формула. [[Файл: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 (тогда он выиграет!). На рисунке каждая скобка - отдельная вершина <tex> c_i </tex>.
Булева формула с кванторами имеет следующий вид: φ = QПосле того, как игрок <subtex>1\forall </subtex>''x''зафиксировал скобку, игрок <subtex>1\exists </sub> Q<sub>2</sub>''x''<sub>2</sub> Q<sub>3</sub>''x''<sub>3</subtex> долджен выбрать переменную, значение которой не ноль (игроки уже зафиксировали значения переменных в самом начале) и сделать переход в соответсвующую вершинку.Т.к.''Qзначение этой переменной не ноль, то игрок <subtex>k\forall </subtex>x<sub>k</sub>''не сможет никуда пойти из этой вершины (ψ) где ''Qтогда </subtex>i\exists </subtex>'' квантор ∃ или ∀. Заметимвыиграл, что любую такую формулу можно преобразовать к виду φ = ∃''x''<sub>1</sub> ∀''x''<sub>2</sub> ∃''x''<sub>3</sub> первый игрок обладает выигрышной стратегией в игре Generalized Geography)...∃''xДля этого проведем ребра из каждый скобки <subtex>kc_i </subtex>''(ψ) в вершины-переменные, добавив необходимое количество переменных с кванторами. Если булева формула возвращает TRUE после ходов игроков По-любому и Существуетучавствующие в этой скобке, то выиграл существуета от них проведем ребра к вершинам левого столбца, иначе выиграл По-любомусоответсвующим выборам TRUE или FALSE значений переменных.
Построив аналогичный граф (приведен ниже) для любой булевой формулы с кванторамиТаким образом, если игрок <tex> \exists </tex> выигрывает, то автоматически обладает выигрышной стратегией и первый игрок в Generalized Geography. Он знает, какие значения переменных надо выбрать, и в какую вершину пойти в конце. Аналогично, мы сможем свести задачу о выигрывании игрока Существует к задаче о наличии по выигрышной стратегии у первого игрока в Generalized Geographyможно узнать, какие значения переменных должен выбрать игрок <tex> \exists </tex> для того, чтобы удовлетворить формулу.
Левый столбец описывает процедуру выборки игроками значений переменныхМы свели задачу об игре игроков <tex> \exists </tex> и <tex> \forall </tex> к задаче Generalized Geography. Очевидно, если игрок выбирает TRUEсведение будет произведено за полиномиальное время. Значит, он идет в левую сторонуязык <tex> GG </tex> является PS-трудным, иначе в правуюа так как выше мы доказали его принадлежность классу PS, то и PS-полным.
Зафиксировав значения переменных, игрок По-любому (т.к. в нашей КНФ-формуле с предворяющими кванторами последний квантор Существует) выбирает скобку, значение которой может быть FALSE (тогда он выиграет!). На рисунке каждая скобка - отдельная вершина ci. == Внешние ссылки ==
После того, как игрок По-Любому зафиксировал скобку, игрок Существует выбирает переменную, значение которой не ноль (игроки уже зафиксировали значения переменных в самом начале) и делает переход в соответсвующую вершинку. Т.к[http://en. значение этой переменной не ноль, то игрок По-любому не сможет никуда пойти из этой вершиныwikipedia. Для этого проведем ребра из каждый скобки org/wiki/Generalized_geography Generalized Geography в вершины, соответствующие выбору TRUE или FALSE значений переменныханглийской википедии.]
