PS-полнота задачи Generalized geography — различия между версиями
Sancho (обсуждение | вклад) (предвАряющий) |
Sancho (обсуждение | вклад) (логический ляп :)) |
||
| Строка 3: | Строка 3: | ||
=== Графическая модель === | === Графическая модель === | ||
| − | Для визуализации задачи можно построить ориентированный граф, где каждая вершина - имя города, а ребро из А в Б означает, что город Б начинается на ту же букву, на которую заканчивается город А. Ход игрока - переход из текущей вершины в новую, ранее не посещенную, по соответствующему ребру. Проигрывает тот, кто не может сделать ни одного перехода. Например, граф для игры в | + | Для визуализации задачи можно построить ориентированный граф, где каждая вершина - имя города, а ориентированное ребро из А в Б означает, что город Б начинается на ту же букву, на которую заканчивается город А. Ход игрока - переход из текущей вершины в новую, ранее не посещенную, по соответствующему ребру. Проигрывает тот, кто не может сделать ни одного перехода. Например, граф для игры в города в штате Мичиган может выглядеть так: |
[[Файл:Generalized_geography_1.png]] | [[Файл:Generalized_geography_1.png]] | ||
| Строка 9: | Строка 9: | ||
В игре Generalized Geography (Обобщенные города) мы заменяем граф с городами на некоторый абстрактный ориентированный граф. Игроки по очереди переходят из вершины в вершину, и проигрывает тот, кто не может сделать новый ход (перейти в ранее не посещенную вершину). | В игре Generalized Geography (Обобщенные города) мы заменяем граф с городами на некоторый абстрактный ориентированный граф. Игроки по очереди переходят из вершины в вершину, и проигрывает тот, кто не может сделать новый ход (перейти в ранее не посещенную вершину). | ||
| − | Рассмотрим пример такой игры. Пусть P1 - игрок, который ходит первым, и P2 - игрок, который ходит вторым. Здесь | + | Рассмотрим пример такой игры. Пусть P1 - игрок, который ходит первым, и P2 - игрок, который ходит вторым. Игра начинается с первой вершины. Здесь игрок P1 обладает следующей выигрышной стратегией: делает ход в вершину 2, после чего P2 переходит в вершину 4, так как это единственный вариант. Первый игрок ходит в вершину 5, и второй выбирает между вершинами 3 и 7. Но независимо от выбора игрока P2, P1 может перейти в вершину 9, откуда второй игрок никуда не может пойти. |
[[Файл:Generalized_geography_2.png]] | [[Файл:Generalized_geography_2.png]] | ||
| Строка 20: | Строка 20: | ||
=== Доказательство принадлежности задачи классу PS === | === Доказательство принадлежности задачи классу PS === | ||
| − | Чтобы показать, что | + | Чтобы показать, что язык принадлежит классу PS, предъявим алгоритм, работающий на полиномиальной памяти, определяющий, обладает ли игрок выигрышной стратегией находясь в вершине v графа G. |
Алгоритм M(<G,v>): | Алгоритм M(<G,v>): | ||
| Строка 32: | Строка 32: | ||
=== Доказательство принадлежности задачи классу PSH === | === Доказательство принадлежности задачи классу PSH === | ||
| − | Для доказательства этого факта сведем задачу | + | Для доказательства этого факта сведем задачу об игре двух игроков ∃ и ∀ в булевой КНФ-формуле с предваряющими кванторами (эта задача PS-трудная) к Generalized Geography за полиномиальное время. |
| − | + | Для игры двух игроков ∃ и ∀ наша формула представима в следующем виде: φ = ∃''x''<sub>1</sub> ∀''x''<sub>2</sub> ∃''x''<sub>3</sub> ...∃''x<sub>n</sub>''(ψ) , где ψ - некая КНФ-формула. | |
[[Файл:Generalized_geography_3.png]] | [[Файл:Generalized_geography_3.png]] | ||
| − | Для любой формулы можно построить граф, аналогичный | + | Для любой такой КНФ-формулы с предваряющими кванторами можно построить граф, аналогичный приведенному на рисунке. Рассмотрим этот граф, и докажем, что это сведение задачи об игре игроков ∃ и ∀ к задаче Generalized Geography. |
Левый столбец в этом графе описывает процедуру выборки игроками ∃ и ∀ значений переменных, если игрок выбирает TRUE, он идет в левую сторону, иначе в правую. | Левый столбец в этом графе описывает процедуру выборки игроками ∃ и ∀ значений переменных, если игрок выбирает TRUE, он идет в левую сторону, иначе в правую. | ||
| Строка 44: | Строка 44: | ||
Зафиксировав значения переменных, игрок ∀ (т.к. в нашей КНФ-формуле с предваряющими кванторами последний квантор ∃) выбирает скобку, значение которой должно быть FALSE (тогда он выиграет!). На рисунке каждая скобка - отдельная вершина c<sub>i</sub>. | Зафиксировав значения переменных, игрок ∀ (т.к. в нашей КНФ-формуле с предваряющими кванторами последний квантор ∃) выбирает скобку, значение которой должно быть FALSE (тогда он выиграет!). На рисунке каждая скобка - отдельная вершина c<sub>i</sub>. | ||
| − | После того, как игрок ∀ зафиксировал скобку, игрок ∃ долджен выбрать переменную, значение которой не ноль (игроки уже зафиксировали значения переменных в самом начале) и сделать переход в соответсвующую вершинку. Т.к. значение этой переменной не ноль, то игрок ∀ не сможет никуда пойти из этой вершины (тогда ∃ выиграл, первый игрок обладает выигрышной стратегией в игре Generalized Geography). Для этого проведем ребра из каждый скобки c<sub>i</sub> в вершины, | + | После того, как игрок ∀ зафиксировал скобку, игрок ∃ долджен выбрать переменную, значение которой не ноль (игроки уже зафиксировали значения переменных в самом начале) и сделать переход в соответсвующую вершинку. Т.к. значение этой переменной не ноль, то игрок ∀ не сможет никуда пойти из этой вершины (тогда ∃ выиграл, первый игрок обладает выигрышной стратегией в игре Generalized Geography). Для этого проведем ребра из каждый скобки c<sub>i</sub> в вершины-переменные, учавствующие в этой скобке, а от них проведем ребра к вершинам левого столбца, соответсвующим выборам TRUE или FALSE значений переменных. |
| − | Таким образом, если игрок ∃ выигрывает, то автоматически обладает выигрышной стратегией и первый игрок в Generalized Geography. Он знает, какие значения переменных надо выбрать, и в какую вершину пойти в конце. Аналогично, по выигрышной стратегии первого игрока в Generalized Geography можно узнать, какие значения переменных должен выбрать игрок ∃ для того, чтобы | + | Таким образом, если игрок ∃ выигрывает, то автоматически обладает выигрышной стратегией и первый игрок в Generalized Geography. Он знает, какие значения переменных надо выбрать, и в какую вершину пойти в конце. Аналогично, по выигрышной стратегии первого игрока в Generalized Geography можно узнать, какие значения переменных должен выбрать игрок ∃ для того, чтобы удовлетворить формулу. |
| − | Мы свели задачу | + | Мы свели задачу об игре игроков ∃ и ∀ к задаче Generalized Geography. Значит, язык GG является PS-трудным, а так как выше мы доказали его принадлежность классу PS, то и PS-полным. |
Версия 17:47, 29 марта 2010
Содержание
Формулировка задачи
Города (Geography) - игра, в которой игроки по очереди называют города со всего мира. Каждый город должен начинаться с той буквы, на которую заканчивается предыдущий, повторы запрещены. Игра начинается с любого города, и заканчивается, когда игрок проигрывает и не может назвать новый город.
Графическая модель
Для визуализации задачи можно построить ориентированный граф, где каждая вершина - имя города, а ориентированное ребро из А в Б означает, что город Б начинается на ту же букву, на которую заканчивается город А. Ход игрока - переход из текущей вершины в новую, ранее не посещенную, по соответствующему ребру. Проигрывает тот, кто не может сделать ни одного перехода. Например, граф для игры в города в штате Мичиган может выглядеть так:
В игре Generalized Geography (Обобщенные города) мы заменяем граф с городами на некоторый абстрактный ориентированный граф. Игроки по очереди переходят из вершины в вершину, и проигрывает тот, кто не может сделать новый ход (перейти в ранее не посещенную вершину).
Рассмотрим пример такой игры. Пусть P1 - игрок, который ходит первым, и P2 - игрок, который ходит вторым. Игра начинается с первой вершины. Здесь игрок P1 обладает следующей выигрышной стратегией: делает ход в вершину 2, после чего P2 переходит в вершину 4, так как это единственный вариант. Первый игрок ходит в вершину 5, и второй выбирает между вершинами 3 и 7. Но независимо от выбора игрока P2, P1 может перейти в вершину 9, откуда второй игрок никуда не может пойти.
Утверждение
Язык GG = { <G, b> | первый игрок в графе G, начиная игру с вершины b обладает выигрышной стратегией } является PS-полным.
Доказательство
Доказательство принадлежности задачи классу PS
Чтобы показать, что язык принадлежит классу PS, предъявим алгоритм, работающий на полиномиальной памяти, определяющий, обладает ли игрок выигрышной стратегией находясь в вершине v графа G.
Алгоритм M(<G,v>):
1. Если из вершины, в которой находится игрок, не ведет ни одного ребра в непосещенные ранее вершины, то вернем FALSE, мы проиграли.
2. Иначе запустим этот же алгоритм от всех вершин, в которые можно пойти, и если везде вернется TRUE, вернем FALSE, куда бы мы ни пошли, второй игрок выиграет. Если же хоть из одной вершины функция вернула FALSE, то вернем TRUE, в этой вершине второй игрок проигрывает.
Этот алгоритм перебором находит выигрышную стратегию для первого игрока, и очевидно, требует полиномиальную память: на каждом шаге одна или более вершин помечаются как посещенные, и более не обрабатываются.
Доказательство принадлежности задачи классу PSH
Для доказательства этого факта сведем задачу об игре двух игроков ∃ и ∀ в булевой КНФ-формуле с предваряющими кванторами (эта задача PS-трудная) к Generalized Geography за полиномиальное время.
Для игры двух игроков ∃ и ∀ наша формула представима в следующем виде: φ = ∃x1 ∀x2 ∃x3 ...∃xn(ψ) , где ψ - некая КНФ-формула.
Для любой такой КНФ-формулы с предваряющими кванторами можно построить граф, аналогичный приведенному на рисунке. Рассмотрим этот граф, и докажем, что это сведение задачи об игре игроков ∃ и ∀ к задаче Generalized Geography.
Левый столбец в этом графе описывает процедуру выборки игроками ∃ и ∀ значений переменных, если игрок выбирает TRUE, он идет в левую сторону, иначе в правую.
Зафиксировав значения переменных, игрок ∀ (т.к. в нашей КНФ-формуле с предваряющими кванторами последний квантор ∃) выбирает скобку, значение которой должно быть FALSE (тогда он выиграет!). На рисунке каждая скобка - отдельная вершина ci.
После того, как игрок ∀ зафиксировал скобку, игрок ∃ долджен выбрать переменную, значение которой не ноль (игроки уже зафиксировали значения переменных в самом начале) и сделать переход в соответсвующую вершинку. Т.к. значение этой переменной не ноль, то игрок ∀ не сможет никуда пойти из этой вершины (тогда ∃ выиграл, первый игрок обладает выигрышной стратегией в игре Generalized Geography). Для этого проведем ребра из каждый скобки ci в вершины-переменные, учавствующие в этой скобке, а от них проведем ребра к вершинам левого столбца, соответсвующим выборам TRUE или FALSE значений переменных.
Таким образом, если игрок ∃ выигрывает, то автоматически обладает выигрышной стратегией и первый игрок в Generalized Geography. Он знает, какие значения переменных надо выбрать, и в какую вершину пойти в конце. Аналогично, по выигрышной стратегии первого игрока в Generalized Geography можно узнать, какие значения переменных должен выбрать игрок ∃ для того, чтобы удовлетворить формулу.
Мы свели задачу об игре игроков ∃ и ∀ к задаче Generalized Geography. Значит, язык GG является PS-трудным, а так как выше мы доказали его принадлежность классу PS, то и PS-полным.
