Викиконспекты - Вклад участника [ru]

PS-полнота задачи Generalized geography

2010-03-30T09:46:13Z

Sancho: tex tex tex

== Формулировка задачи==

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

Города (Geography) - игра, в которой игроки по очереди называют города со всего мира. Каждый город должен начинаться с той буквы, на которую заканчивается предыдущий, повторы запрещены. Игра начинается с любого города, и заканчивается, когда игрок проигрывает и не может назвать новый город.

=== Графическая модель ===

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

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

В игре Generalized Geography (Обобщенные города) мы заменяем граф с городами на некоторый абстрактный ориентированный граф. Игроки по очереди переходят из вершины в вершину, и проигрывает тот, кто не может сделать новый ход (перейти в ранее не посещенную вершину).

Рассмотрим пример. Пусть 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, b \rangle ) </tex> :

1. Если из вершины, в которой находится игрок, не ведет ни одного ребра в непосещенные ранее вершины, то вернем FALSE, мы проиграли.

2. Иначе запустим этот же алгоритм от всех вершин, в которые можно пойти, и если везде вернется TRUE, вернем FALSE, куда бы мы ни пошли, второй игрок выиграет. Если же хоть из одной вершины функция вернула FALSE, то вернем TRUE, в этой вершине второй игрок проигрывает.

Этот алгоритм перебором находит выигрышную стратегию для первого игрока, и очевидно, требует полиномиальную память: на каждом шаге одна или более вершин помечаются как посещенные, и более не обрабатываются.

=== Доказательство принадлежности задачи классу PSH ===

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

Если в нашей формуле с предваряющими кванторами последний квантор - не <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| Модель графа для сведения задачи об игре двух игроков <tex> \exists </tex> и <tex> \forall </tex> к задаче GG]]

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

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

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

Мы свели задачу об игре игроков <tex> \exists </tex> и <tex> \forall </tex> к задаче Generalized Geography. Очевидно, сведение будет произведено за полиномиальное время. Значит, язык GG является PS-трудным, а так как выше мы доказали его принадлежность классу PS, то и PS-полным.

PS-полнота задачи Generalized geography

2010-03-30T09:39:25Z

Sancho: tex tex tex

== Формулировка задачи==

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

Города (Geography) - игра, в которой игроки по очереди называют города со всего мира. Каждый город должен начинаться с той буквы, на которую заканчивается предыдущий, повторы запрещены. Игра начинается с любого города, и заканчивается, когда игрок проигрывает и не может назвать новый город.

=== Графическая модель ===

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

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

В игре Generalized Geography (Обобщенные города) мы заменяем граф с городами на некоторый абстрактный ориентированный граф. Игроки по очереди переходят из вершины в вершину, и проигрывает тот, кто не может сделать новый ход (перейти в ранее не посещенную вершину).

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

== Утверждение ==

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

== Доказательство ==
=== Доказательство принадлежности задачи классу PS ===

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

Алгоритм M(<G,v>):

1. Если из вершины, в которой находится игрок, не ведет ни одного ребра в непосещенные ранее вершины, то вернем FALSE, мы проиграли.

2. Иначе запустим этот же алгоритм от всех вершин, в которые можно пойти, и если везде вернется TRUE, вернем FALSE, куда бы мы ни пошли, второй игрок выиграет. Если же хоть из одной вершины функция вернула FALSE, то вернем TRUE, в этой вершине второй игрок проигрывает.

Этот алгоритм перебором находит выигрышную стратегию для первого игрока, и очевидно, требует полиномиальную память: на каждом шаге одна или более вершин помечаются как посещенные, и более не обрабатываются.

=== Доказательство принадлежности задачи классу PSH ===

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

Если в нашей формуле с предваряющими кванторами последний квантор - не <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| Модель графа для сведения задачи об игре двух игроков <tex> \exists </tex> и <tex> \forall </tex> к задаче GG]]

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

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

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

Мы свели задачу об игре игроков <tex> \exists </tex> и <tex> \forall </tex> к задаче Generalized Geography. Очевидно, сведение будет произведено за полиномиальное время. Значит, язык GG является PS-трудным, а так как выше мы доказали его принадлежность классу PS, то и PS-полным.

PS-полнота задачи Generalized geography

2010-03-29T21:23:16Z

Sancho: /* Графическая модель */

== Формулировка задачи==

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

Города (Geography) - игра, в которой игроки по очереди называют города со всего мира. Каждый город должен начинаться с той буквы, на которую заканчивается предыдущий, повторы запрещены. Игра начинается с любого города, и заканчивается, когда игрок проигрывает и не может назвать новый город.

=== Графическая модель ===

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

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

В игре Generalized Geography (Обобщенные города) мы заменяем граф с городами на некоторый абстрактный ориентированный граф. Игроки по очереди переходят из вершины в вершину, и проигрывает тот, кто не может сделать новый ход (перейти в ранее не посещенную вершину).

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

== Утверждение ==

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

== Доказательство ==
=== Доказательство принадлежности задачи классу PS ===

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

Алгоритм M(<G,v>):

1. Если из вершины, в которой находится игрок, не ведет ни одного ребра в непосещенные ранее вершины, то вернем FALSE, мы проиграли.

2. Иначе запустим этот же алгоритм от всех вершин, в которые можно пойти, и если везде вернется TRUE, вернем FALSE, куда бы мы ни пошли, второй игрок выиграет. Если же хоть из одной вершины функция вернула FALSE, то вернем TRUE, в этой вершине второй игрок проигрывает.

Этот алгоритм перебором находит выигрышную стратегию для первого игрока, и очевидно, требует полиномиальную память: на каждом шаге одна или более вершин помечаются как посещенные, и более не обрабатываются.

=== Доказательство принадлежности задачи классу PSH ===

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

Для игры двух игроков ∃ и ∀ наша формула представима в следующем виде: φ = ∃''x''1 ∀''x''2 ∃''x''3 ...∃''xn''(ψ) , где ψ - некая КНФ-формула.

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

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

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

Зафиксировав значения переменных, игрок ∀ (т.к. в нашей КНФ-формуле с предваряющими кванторами последний квантор ∃) выбирает скобку, значение которой должно быть FALSE (тогда он выиграет!). На рисунке каждая скобка - отдельная вершина ci.

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

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

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

PS-полнота задачи Generalized geography

2010-03-29T15:13:34Z

Sancho: ссылки

== Формулировка задачи==

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

Города (Geography) - игра, в которой игроки по очереди называют города со всего мира. Каждый город должен начинаться с той буквы, на которую заканчивается предыдущий, повторы запрещены. Игра начинается с любого города, и заканчивается, когда игрок проигрывает и не может назвать новый город.

=== Графическая модель ===

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

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

В игре Generalized Geography (Обобщенные города) мы заменяем граф с городами на некоторый абстрактный ориентированный граф. Игроки по очереди переходят из вершины в вершину, и проигрывает тот, кто не может сделать новый ход (перейти в ранее не посещенную вершину).

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

== Утверждение ==

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

== Доказательство ==
=== Доказательство принадлежности задачи классу PS ===

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

Алгоритм M(<G,v>):

1. Если из вершины, в которой находится игрок, не ведет ни одного ребра в непосещенные ранее вершины, то вернем FALSE, мы проиграли.

2. Иначе запустим этот же алгоритм от всех вершин, в которые можно пойти, и если везде вернется TRUE, вернем FALSE, куда бы мы ни пошли, второй игрок выиграет. Если же хоть из одной вершины функция вернула FALSE, то вернем TRUE, в этой вершине второй игрок проигрывает.

Этот алгоритм перебором находит выигрышную стратегию для первого игрока, и очевидно, требует полиномиальную память: на каждом шаге одна или более вершин помечаются как посещенные, и более не обрабатываются.

=== Доказательство принадлежности задачи классу PSH ===

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

Для игры двух игроков ∃ и ∀ наша формула представима в следующем виде: φ = ∃''x''1 ∀''x''2 ∃''x''3 ...∃''xn''(ψ) , где ψ - некая КНФ-формула.

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

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

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

Зафиксировав значения переменных, игрок ∀ (т.к. в нашей КНФ-формуле с предваряющими кванторами последний квантор ∃) выбирает скобку, значение которой должно быть FALSE (тогда он выиграет!). На рисунке каждая скобка - отдельная вершина ci.

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

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

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

PS-полнота задачи Generalized geography

2010-03-29T15:08:48Z

Sancho: ссылки

== Формулировка задачи==

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

Города (Geography) - игра, в которой игроки по очереди называют города со всего мира. Каждый город должен начинаться с той буквы, на которую заканчивается предыдущий, повторы запрещены. Игра начинается с любого города, и заканчивается, когда игрок проигрывает и не может назвать новый город.

=== Графическая модель ===

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

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

В игре Generalized Geography (Обобщенные города) мы заменяем граф с городами на некоторый абстрактный ориентированный граф. Игроки по очереди переходят из вершины в вершину, и проигрывает тот, кто не может сделать новый ход (перейти в ранее не посещенную вершину).

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

== Утверждение ==

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

== Доказательство ==
=== Доказательство принадлежности задачи классу PS ===

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

Алгоритм M(<G,v>):

1. Если из вершины, в которой находится игрок, не ведет ни одного ребра в непосещенные ранее вершины, то вернем FALSE, мы проиграли.

2. Иначе запустим этот же алгоритм от всех вершин, в которые можно пойти, и если везде вернется TRUE, вернем FALSE, куда бы мы ни пошли, второй игрок выиграет. Если же хоть из одной вершины функция вернула FALSE, то вернем TRUE, в этой вершине второй игрок проигрывает.

Этот алгоритм перебором находит выигрышную стратегию для первого игрока, и очевидно, требует полиномиальную память: на каждом шаге одна или более вершин помечаются как посещенные, и более не обрабатываются.

=== Доказательство принадлежности задачи классу PSH ===

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

Для игры двух игроков ∃ и ∀ наша формула представима в следующем виде: φ = ∃''x''1 ∀''x''2 ∃''x''3 ...∃''xn''(ψ) , где ψ - некая КНФ-формула.

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

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

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

Зафиксировав значения переменных, игрок ∀ (т.к. в нашей КНФ-формуле с предваряющими кванторами последний квантор ∃) выбирает скобку, значение которой должно быть FALSE (тогда он выиграет!). На рисунке каждая скобка - отдельная вершина ci.

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

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

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

PS-полнота задачи Generalized geography

2010-03-29T15:00:10Z

Sancho: рисунки подписи

== Формулировка задачи==

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

Города (Geography) - игра, в которой игроки по очереди называют города со всего мира. Каждый город должен начинаться с той буквы, на которую заканчивается предыдущий, повторы запрещены. Игра начинается с любого города, и заканчивается, когда игрок проигрывает и не может назвать новый город.

=== Графическая модель ===

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

[[Файл:Generalized_geography_2.png|thumb|350px| Пример графа для игры в Generalized 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 за полиномиальное время.

Для игры двух игроков ∃ и ∀ наша формула представима в следующем виде: φ = ∃''x''1 ∀''x''2 ∃''x''3 ...∃''xn''(ψ) , где ψ - некая КНФ-формула.

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

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

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

Зафиксировав значения переменных, игрок ∀ (т.к. в нашей КНФ-формуле с предваряющими кванторами последний квантор ∃) выбирает скобку, значение которой должно быть FALSE (тогда он выиграет!). На рисунке каждая скобка - отдельная вершина ci.

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

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

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

PS-полнота задачи Generalized geography

2010-03-29T14:54:51Z

Sancho: рисунки |thumb|350px

== Формулировка задачи==

[[Файл:Generalized_geography_1.png|thumb|350px]]

Города (Geography) - игра, в которой игроки по очереди называют города со всего мира. Каждый город должен начинаться с той буквы, на которую заканчивается предыдущий, повторы запрещены. Игра начинается с любого города, и заканчивается, когда игрок проигрывает и не может назвать новый город.

=== Графическая модель ===

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

[[Файл:Generalized_geography_2.png|thumb|350px]]

В игре 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 за полиномиальное время.

Для игры двух игроков ∃ и ∀ наша формула представима в следующем виде: φ = ∃''x''1 ∀''x''2 ∃''x''3 ...∃''xn''(ψ) , где ψ - некая КНФ-формула.

[[Файл:Generalized_geography_3.png|thumb|350px]]

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

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

Зафиксировав значения переменных, игрок ∀ (т.к. в нашей КНФ-формуле с предваряющими кванторами последний квантор ∃) выбирает скобку, значение которой должно быть FALSE (тогда он выиграет!). На рисунке каждая скобка - отдельная вершина ci.

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

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

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

PS-полнота задачи Generalized geography

2010-03-29T14:47:14Z

Sancho: логический ляп :)

== Формулировка задачи==
Города (Geography) - игра, в которой игроки по очереди называют города со всего мира. Каждый город должен начинаться с той буквы, на которую заканчивается предыдущий, повторы запрещены. Игра начинается с любого города, и заканчивается, когда игрок проигрывает и не может назвать новый город.

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

[[Файл:Generalized_geography_1.png]]

В игре Generalized Geography (Обобщенные города) мы заменяем граф с городами на некоторый абстрактный ориентированный граф. Игроки по очереди переходят из вершины в вершину, и проигрывает тот, кто не может сделать новый ход (перейти в ранее не посещенную вершину).

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

[[Файл:Generalized_geography_2.png]]

== Утверждение ==

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

== Доказательство ==
=== Доказательство принадлежности задачи классу PS ===

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

Алгоритм M(<G,v>):

1. Если из вершины, в которой находится игрок, не ведет ни одного ребра в непосещенные ранее вершины, то вернем FALSE, мы проиграли.

2. Иначе запустим этот же алгоритм от всех вершин, в которые можно пойти, и если везде вернется TRUE, вернем FALSE, куда бы мы ни пошли, второй игрок выиграет. Если же хоть из одной вершины функция вернула FALSE, то вернем TRUE, в этой вершине второй игрок проигрывает.

Этот алгоритм перебором находит выигрышную стратегию для первого игрока, и очевидно, требует полиномиальную память: на каждом шаге одна или более вершин помечаются как посещенные, и более не обрабатываются.

=== Доказательство принадлежности задачи классу PSH ===

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

Для игры двух игроков ∃ и ∀ наша формула представима в следующем виде: φ = ∃''x''1 ∀''x''2 ∃''x''3 ...∃''xn''(ψ) , где ψ - некая КНФ-формула.

[[Файл:Generalized_geography_3.png]]

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

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

Зафиксировав значения переменных, игрок ∀ (т.к. в нашей КНФ-формуле с предваряющими кванторами последний квантор ∃) выбирает скобку, значение которой должно быть FALSE (тогда он выиграет!). На рисунке каждая скобка - отдельная вершина ci.

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

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

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

PS-полнота задачи Generalized geography

2010-03-29T14:19:45Z

Sancho: предвАряющий

== Формулировка задачи==
Города (Geography) - игра, в которой игроки по очереди называют города со всего мира. Каждый город должен начинаться с той буквы, на которую заканчивается предыдущий, повторы запрещены. Игра начинается с любого города, и заканчивается, когда игрок проигрывает и не может назвать новый город.

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

[[Файл:Generalized_geography_1.png]]

В игре Generalized Geography (Обобщенные города) мы заменяем граф с городами на некоторый абстрактный ориентированный граф. Игроки по очереди переходят из вершины в вершину, и проигрывает тот, кто не может сделать новый ход (перейти в ранее не посещенную вершину).

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

[[Файл:Generalized_geography_2.png]]

== Утверждение ==

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

== Доказательство ==
=== Доказательство принадлежности задачи классу PS ===

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

Алгоритм M(<G,v>):

1. Если из вершины, в которой находится игрок, не ведет ни одного ребра в непосещенные ранее вершины, то вернем FALSE, мы проиграли.

2. Иначе запустим этот же алгоритм от всех вершин, в которые можно пойти, и если везде вернется TRUE, вернем FALSE, куда бы мы ни пошли, второй игрок выиграет. Если же хоть из одной вершины функция вернула FALSE, то вернем TRUE, в этой вершине второй игрок проигрывает.

Этот алгоритм перебором находит выигрышную стратегию для первого игрока, и очевидно, требует полиномиальную память: на каждом шаге одна или более вершин помечаются как посещенные, и более не обрабатываются.

=== Доказательство принадлежности задачи классу PSH ===

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

Булева формула с кванторами имеет следующий вид: φ = Q1''x''1 Q2''x''2 Q3''x''3 ...''Qkxk''(ψ) где ''Qi'' квантор ∃ или ∀, а ψ - некоторая булева формула. Заметим, что любую такую формулу можно преобразовать к виду φ = ∃''x''1 ∀''x''2 ∃''x''3 ...∃''xn''(ψ) , добавив необходимое количество переменных с кванторами. Представим получившуюся формулу как игру игроков ∃ и ∀. Игрок ∃ здесь - первый игрок в Generalized Geography, а игрок ∀ - второй. Таким образом, если ∃ выигрывает в своей игре, то первый игрок обладает выигрышной стратегией в игре Generalized Geography. Осталось по булевой формуле с предваряющими кванторами получить соотвествующий граф для игры в Generalized Geography.

[[Файл:Generalized_geography_3.png]]

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

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

Зафиксировав значения переменных, игрок ∀ (т.к. в нашей КНФ-формуле с предваряющими кванторами последний квантор ∃) выбирает скобку, значение которой должно быть FALSE (тогда он выиграет!). На рисунке каждая скобка - отдельная вершина ci.

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

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

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

PS-полнота задачи Generalized geography

2010-03-29T13:57:22Z

Sancho: рефакторинг 1

== Формулировка задачи==
Города (Geography) - игра, в которой игроки по очереди называют города со всего мира. Каждый город должен начинаться с той буквы, на которую заканчивается предыдущий, повторы запрещены. Игра начинается с любого города, и заканчивается, когда игрок проигрывает и не может назвать новый город.

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

[[Файл:Generalized_geography_1.png]]

В игре Generalized Geography (Обобщенные города) мы заменяем граф с городами на некоторый абстрактный ориентированный граф. Игроки по очереди переходят из вершины в вершину, и проигрывает тот, кто не может сделать новый ход (перейти в ранее не посещенную вершину).

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

[[Файл:Generalized_geography_2.png]]

== Утверждение ==

Сформулируем задачу так: по данному ориентированному графу выяснить, обладает ли первый игрок выигрышной стратегией, стартуя в вершине с номером х.

Эта задача PS-полна.

== Доказательство ==
=== Доказательство принадлежности задачи классу PS ===

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

Алгоритм M(<G,v>):

1. Если из вершины, в которой находится игрок, не ведет ни одного ребра в непосещенные ранее вершины, то вернем FALSE, мы проиграли.

2. Иначе запустим этот же алгоритм от всех вершин, в которые можно пойти, и если везде вернется TRUE, вернем FALSE, куда бы мы ни пошли, второй игрок выиграет. Если же хоть из одной вершины функция вернула FALSE, то вернем TRUE, в этой вершине второй игрок проигрывает.

Этот алгоритм перебором находит выигрышную стратегию для первого игрока, и очевидно, требует полиномиальную память: на каждом шаге одна или более вершин помечаются как посещенные, и более не обрабатываются.

=== Доказательство принадлежности задачи классу PSH ===

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

Булева формула с кванторами имеет следующий вид: φ = Q1''x''1 Q2''x''2 Q3''x''3 ...''Qkxk''(ψ) где ''Qi'' квантор ∃ или ∀, а ψ - некоторая булева формула. Заметим, что любую такую формулу можно преобразовать к виду φ = ∃''x''1 ∀''x''2 ∃''x''3 ...∃''xn''(ψ) , добавив необходимое количество переменных с кванторами. Представим получившуюся формулу как игру игроков ∃ и ∀. Игрок ∃ здесь - первый игрок в Generalized Geography, а игрок ∀ - второй. Таким образом, если ∃ выигрывает в своей игре, то первый игрок обладает выигрышной стратегией в игре Generalized Geography. Осталось по булевой формуле с предваряющими кванторами получить соотвествующий граф для игры в Generalized Geography.

[[Файл:Generalized_geography_3.png]]

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

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

Зафиксировав значения переменных, игрок ∀ (т.к. в нашей КНФ-формуле с предворяющими кванторами последний квантор ∃) выбирает скобку, значение которой должно быть FALSE (тогда он выиграет!). На рисунке каждая скобка - отдельная вершина ci.

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

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

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

PS-полнота задачи Generalized geography

2010-03-29T13:07:39Z

Sancho: рисунок в доказательстве

== Формулировка задачи==
Города (Geography) - игра, в которой игроки по очереди называют города со всего мира. Каждый город должен начинаться с той буквы, на которую заканчивается предыдущий, повторы запрещены. Игра начинается с любого города, и заканчивается, когда игрок проигрывает и не может назвать новый город.

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

[[Файл:Generalized_geography_1.png]]

В игре Generalized Geography (Обобщенные города) мы заменяем граф с городами на некоторый абстрактный ориентированный граф. Игроки по очереди переходят из вершины в вершину, и проигрывает тот, кто не может сделать новый ход (перейти в ранее не посещенную вершину).

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

[[Файл:Generalized_geography_2.png]]

== Утверждение ==

Сформулируем задачу так: по данному ориентированному графу выяснить, обладает ли первый игрок выигрышной стратегией, стартуя в вершине с номером х.

Эта задача PS-полна.

== Доказательство ==
=== Доказательство принадлежности задачи классу PS ===

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

Алгоритм M(<G,v>):

1. Если из вершины, в которой находится игрок, не ведет ни одного ребра в непосещенные ранее вершины, то вернем FALSE, мы проиграли.

2. Иначе запустим этот же алгоритм от всех вершин, в которые можно пойти, и если везде вернется TRUE, вернем FALSE, куда бы мы ни пошли, второй игрок выиграет. Если же хоть из одной вершины функция вернула FALSE, то вернем TRUE, в этой вершине второй игрок проигрывает.

Этот алгоритм перебором находит выигрышную стратегию для первого игрока, и очевидно, требует полиномиальную память: на каждом шаге одна или более вершин помечаются как посещенные, и более не обрабатываются.

=== Доказательство принадлежности задачи классу PSH ===

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

Булева формула с кванторами имеет следующий вид: φ = Q1''x''1 Q2''x''2 Q3''x''3 ...''Qkxk''(ψ) где ''Qi'' квантор ∃ или ∀. Заметим, что любую такую формулу можно преобразовать к виду φ = ∃''x''1 ∀''x''2 ∃''x''3 ...∃''xk''(ψ) , добавив необходимое количество переменных с кванторами. Если булева формула возвращает TRUE после ходов игроков По-любому и Существует, то выиграл Существует, иначе выиграл По-любому.

[[Файл:Generalized_geography_3.png]]

Построив граф, аналогичный приведенному на рисунке, для любой булевой формулы с кванторами, мы сможем свести задачу о выигрывании игрока Существует к задаче о наличии выигрышной стратегии у первого игрока в Generalized Geography.

Левый столбец описывает процедуру выборки игроками значений переменных, если игрок выбирает TRUE, он идет в левую сторону, иначе в правую.

Зафиксировав значения переменных, игрок По-любому (т.к. в нашей КНФ-формуле с предворяющими кванторами последний квантор Существует) выбирает скобку, значение которой может быть FALSE (тогда он выиграет!). На рисунке каждая скобка - отдельная вершина ci.

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

Файл:Generalized geography 3.png

2010-03-29T12:58:52Z

Sancho:

PS-полнота задачи Generalized geography

2010-03-29T12:30:09Z

Sancho: рисунки

== Формулировка задачи==
Города (Geography) - игра, в которой игроки по очереди называют города со всего мира. Каждый город должен начинаться с той буквы, на которую заканчивается предыдущий, повторы запрещены. Игра начинается с любого города, и заканчивается, когда игрок проигрывает и не может назвать новый город.

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

[[Файл:Generalized_geography_1.png]]

В игре Generalized Geography (Обобщенные города) мы заменяем граф с городами на некоторый абстрактный ориентированный граф. Игроки по очереди переходят из вершины в вершину, и проигрывает тот, кто не может сделать новый ход (перейти в ранее не посещенную вершину).

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

[[Файл:Generalized_geography_2.png]]

== Утверждение ==

Сформулируем задачу так: по данному ориентированному графу выяснить, обладает ли первый игрок выигрышной стратегией, стартуя в вершине с номером х.

Эта задача PS-полна.

== Доказательство ==
=== Доказательство принадлежности задачи классу PS ===

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

Алгоритм M(<G,v>):

1. Если из вершины, в которой находится игрок, не ведет ни одного ребра в непосещенные ранее вершины, то вернем FALSE, мы проиграли.

2. Иначе запустим этот же алгоритм от всех вершин, в которые можно пойти, и если везде вернется TRUE, вернем FALSE, куда бы мы ни пошли, второй игрок выиграет. Если же хоть из одной вершины функция вернула FALSE, то вернем TRUE, в этой вершине второй игрок проигрывает.

Этот алгоритм перебором находит выигрышную стратегию для первого игрока, и очевидно, требует полиномиальную память: на каждом шаге одна или более вершин помечаются как посещенные, и более не обрабатываются.

=== Доказательство принадлежности задачи классу PSH ===

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

Булева формула с кванторами имеет следующий вид: φ = Q1''x''1 Q2''x''2 Q3''x''3 ...''Qkxk''(ψ) где ''Qi'' квантор ∃ или ∀. Заметим, что любую такую формулу можно преобразовать к виду φ = ∃''x''1 ∀''x''2 ∃''x''3 ...∃''xk''(ψ) , добавив необходимое количество переменных с кванторами. Если булева формула возвращает TRUE после ходов игроков По-любому и Существует, то выиграл существует, иначе выиграл По-любому.

Построив аналогичный граф (приведен ниже) для любой булевой формулы с кванторами, мы сможем свести задачу о выигрывании игрока Существует к задаче о наличии выигрышной стратегии у первого игрока в Generalized Geography.

Левый столбец описывает процедуру выборки игроками значений переменных, если игрок выбирает TRUE, он идет в левую сторону, иначе в правую.

Зафиксировав значения переменных, игрок По-любому (т.к. в нашей КНФ-формуле с предворяющими кванторами последний квантор Существует) выбирает скобку, значение которой может быть FALSE (тогда он выиграет!). На рисунке каждая скобка - отдельная вершина ci.

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

Файл:Generalized geography 2.png

2010-03-29T12:26:34Z

Sancho:

Файл:Generalized geography 1.png

2010-03-29T12:24:35Z

Sancho:

PS-полнота задачи Generalized geography

2010-03-29T11:56:14Z

Sancho: /* Утверждение */

== Формулировка задачи==
Городки (Geography) - игра, в которой игроки по очереди называют города со всего мира. Каждый город должен начинаться с той буквы, на которую заканчивается предыдущий. Повторы запрещены. Игра начинается с любого города, и заканчивается, когда игрок проигрывает и не может назвать новый город.

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

Рисунок

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

Рисунок.

== Утверждение ==

Сформулируем задачу так: по данному ориентированному графу выяснить, обладает ли первый игрок выигрышной стратегией, стартуя в вершине с номером х.

Эта задача PS-полна.

== Доказательство ==
=== Доказательство принадлежности задачи классу PS ===

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

Алгоритм M(<G,v>):

1. Если из вершины, в которой находится игрок, не ведет ни одного ребра в непосещенные ранее вершины, то вернем FALSE, мы проиграли.

2. Иначе запустим этот же алгоритм от всех вершин, в которые можно пойти, и если везде вернется TRUE, вернем FALSE, куда бы мы ни пошли, второй игрок выиграет. Если же хоть из одной вершины функция вернула FALSE, то вернем TRUE, в этой вершине второй игрок проигрывает.

Этот алгоритм перебором находит выигрышную стратегию для первого игрока, и очевидно, требует полиномиальную память: на каждом шаге одна или более вершин помечаются как посещенные, и более не обрабатываются.

=== Доказательство принадлежности задачи классу PSH ===

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

Булева формула с кванторами имеет следующий вид: φ = Q1''x''1 Q2''x''2 Q3''x''3 ...''Qkxk''(ψ) где ''Qi'' квантор ∃ или ∀. Заметим, что любую такую формулу можно преобразовать к виду φ = ∃''x''1 ∀''x''2 ∃''x''3 ...∃''xk''(ψ) , добавив необходимое количество переменных с кванторами. Если булева формула возвращает TRUE после ходов игроков По-любому и Существует, то выиграл существует, иначе выиграл По-любому.

Построив аналогичный граф (приведен ниже) для любой булевой формулы с кванторами, мы сможем свести задачу о выигрывании игрока Существует к задаче о наличии выигрышной стратегии у первого игрока в Generalized Geography.

Левый столбец описывает процедуру выборки игроками значений переменных, если игрок выбирает TRUE, он идет в левую сторону, иначе в правую.

Зафиксировав значения переменных, игрок По-любому (т.к. в нашей КНФ-формуле с предворяющими кванторами последний квантор Существует) выбирает скобку, значение которой может быть FALSE (тогда он выиграет!). На рисунке каждая скобка - отдельная вершина ci.

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

Теория сложности (старая трешовая версия)

2010-03-12T22:46:41Z

Sancho:

== Лекция 1 ==
*[[Класс DSPACE]]
*[[Теорема о емкостной иерархии]]

== Лекция 2 ==
*[[Теорема Кука]]

== Лекция 3 ==
*[[Теорема Ладнера]]
*[[Теорема Левина]]
*[[Теорема Бейкера-Гилла-Соловэя]]

== Практика 3 ==
*[[NP-полнота задачи о сумме подмножества]]
*[[NP-полнота задачи о рюкзаке]]

== Практика, которой на самом деле не было ==
*[[NP-полнота задачи о раскраске графа]]

== Лекция 4 ==
*[[PS-полнота задачи Generalized geography]]