Изменения

Для визуализации задачи можно построить ориентированный граф, где каждая вершина - имя города, а ориентированное ребро из А в Б означает, что город Б начинается на ту же букву, на которую заканчивается город А. Ход игрока - переход из текущей вершины в новую, ранее не посещенную, по соответствующему ребру. Проигрывает тот, кто не может сделать ни одного перехода (см. рис. 1). [[Файл:Generalized_geography_1Generalized_geography_2.png|thumb|350px| Рис. 2. Пример графа для игры в Generalized Geography]]

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

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

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

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

Для доказательства этого факта сведем задачу о выполнимости булевой КНФ-формулы с предваряющими кванторами в форме КНФ (эта задача [[Класс_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]]

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

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

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

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

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

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

Мы свели задачу о выполнимости булевой формулы с предваряющими кванторами к задача [http://en.wikipedia.org/wiki/Generalized_geography Generalized Geographyв английской википедии. Значит, язык GG является PS-трудным, а так как выше мы доказали его принадлежность классу PS, то и PS-полным.]