PS-полнота задачи Generalized geography - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:25:09Z

rollbackEdits.php mass rollback

103.251.167.21 в 04:56, 1 сентября 2022

2022-09-01T04:56:27Z

192.168.0.2 в 13:20, 1 апреля 2010

2010-04-01T13:20:41Z

192.168.0.2: small fix

2010-04-01T13:13:04Z

small fix

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

2010-04-01T13:05:27Z

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

192.168.0.2: рис1, 2, 3.

2010-03-30T15:16:28Z

рис1, 2, 3.

Sancho: tex tex tex

2010-03-30T09:46:13Z

tex tex tex

Sancho: tex tex tex

2010-03-30T09:39:25Z

tex tex tex

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

2010-03-29T21:23:16Z

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

Sancho: ссылки

2010-03-29T15:13:34Z

ссылки

← Предыдущая		Версия 16:25, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	== Формулировка задачи==		== Формулировка задачи==

← Предыдущая		Версия 04:56, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	== Формулировка задачи==		== Формулировка задачи==

← Предыдущая		Версия 13:20, 1 апреля 2010
Строка 52:		Строка 52:

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

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

← Предыдущая		Версия 13:05, 1 апреля 2010
Строка 51:		Строка 51:
	Таким образом, если игрок <tex> \exists </tex> выигрывает, то автоматически обладает выигрышной стратегией и первый игрок в Generalized Geography. Он знает, какие значения переменных надо выбрать, и в какую вершину пойти в конце. Аналогично, по выигрышной стратегии первого игрока в Generalized Geography можно узнать, какие значения переменных должен выбрать игрок <tex> \exists </tex> для того, чтобы удовлетворить формулу.		Таким образом, если игрок <tex> \exists </tex> выигрывает, то автоматически обладает выигрышной стратегией и первый игрок в Generalized Geography. Он знает, какие значения переменных надо выбрать, и в какую вершину пойти в конце. Аналогично, по выигрышной стратегии первого игрока в Generalized Geography можно узнать, какие значения переменных должен выбрать игрок <tex> \exists </tex> для того, чтобы удовлетворить формулу.

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

@@ Строка 1: / Строка 1: @@
 == Формулировка задачи==
-[[Файл:Generalized_geography_1.png|thumb|350px| Граф для игры в города в штате Мичиган]]
+[[Файл:Generalized_geography_1.png|thumb|350px| Рис. 1. Граф для игры в города в штате Мичиган]]
 Города (Geography) - игра, в которой игроки по очереди называют города со всего мира. Каждый город должен начинаться с той буквы, на которую заканчивается предыдущий, повторы запрещены. Игра начинается с любого города, и заканчивается, когда игрок проигрывает и не может назвать новый город.
@@ Строка 7: / Строка 7: @@
 === Графическая модель ===
-Для визуализации задачи можно построить ориентированный граф, где каждая вершина - имя города, а ориентированное ребро из А в Б означает, что город Б начинается на ту же букву, на которую заканчивается город А. Ход игрока - переход из текущей вершины в новую, ранее не посещенную, по соответствующему ребру. Проигрывает тот, кто не может сделать ни одного перехода.
+Для визуализации задачи можно построить ориентированный граф, где каждая вершина - имя города, а ориентированное ребро из А в Б означает, что город Б начинается на ту же букву, на которую заканчивается город А. Ход игрока - переход из текущей вершины в новую, ранее не посещенную, по соответствующему ребру. Проигрывает тот, кто не может сделать ни одного перехода (см. рис. 1).
-[[Файл:Generalized_geography_2.png|thumb|350px| Пример графа для игры в Generalized Geography]]
+[[Файл:Generalized_geography_2.png|thumb|350px| Рис. 2. Пример графа для игры в Generalized Geography]]
 В игре Generalized Geography (Обобщенные города) мы заменяем граф с городами на некоторый абстрактный ориентированный граф. Игроки по очереди переходят из вершины в вершину, и проигрывает тот, кто не может сделать новый ход (перейти в ранее не посещенную вершину).
-Рассмотрим пример. Пусть P1 - игрок, который ходит первым, и  P2 - игрок, который ходит вторым. Игра начинается с первой вершины. Здесь игрок P1 обладает следующей выигрышной стратегией: делает ход в вершину 2, после чего P2 переходит в вершину 4, так как это единственный вариант. Первый игрок ходит в вершину 5, и второй выбирает между вершинами 3 и 7. Но независимо от выбора игрока P2, P1 может перейти в вершину 9, откуда второй игрок никуда не может пойти.
+Рассмотрим пример (рис. 2). Пусть P1 - игрок, который ходит первым, и  P2 - игрок, который ходит вторым. Игра начинается с первой вершины. Здесь игрок P1 обладает следующей выигрышной стратегией: делает ход в вершину 2, после чего P2 переходит в вершину 4, так как это единственный вариант. Первый игрок ходит в вершину 5, и второй выбирает между вершинами 3 и 7. Но независимо от выбора игрока P2, P1 может перейти в вершину 9, откуда второй игрок никуда не может пойти.
 == Утверждение ==
@@ Строка 39: / Строка 39: @@
 <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]]
+[[Файл:Generalized_geography_3.png|thumb|350px| Рис. 3. Модель графа для сведения задачи об игре двух игроков <tex> \exists </tex> и <tex> \forall </tex> к задаче GG]]
-Для любой такой КНФ-формулы с предваряющими кванторами можно построить граф, аналогичный приведенному на рисунке. Рассмотрим этот граф, и докажем, что это сведение задачи об игре игроков <tex> \exists </tex> и <tex> \forall </tex> к задаче Generalized Geography.
+Для любой такой КНФ-формулы с предваряющими кванторами можно построить граф, аналогичный приведенному на рисунке 3. Рассмотрим этот граф, и докажем, что это сведение задачи об игре игроков <tex> \exists </tex> и <tex> \forall </tex> к задаче Generalized Geography.
 Левый столбец в этом графе описывает процедуру выборки игроками <tex> \exists </tex> и <tex> \forall </tex> значений переменных, если игрок выбирает TRUE, он идет в левую сторону, иначе в правую.

@@ Строка 17: / Строка 17: @@
 == Утверждение ==
-Язык GG = { <G, b> | первый игрок в графе G, начиная игру с вершины b, обладает выигрышной стратегией } является [[Класс_PS|PS-полным]].
+Язык <tex> GG = \{ \langle G, b \rangle | </tex> первый игрок в графе <tex> G </tex>, начиная игру с вершины <tex> b </tex>, обладает выигрышной стратегией <tex> \} </tex> является [[Класс_PS|PS-полным]].
 == Доказательство ==
@@ Строка 24: / Строка 24: @@
 Чтобы показать, что язык принадлежит классу PS, предъявим алгоритм, работающий на полиномиальной памяти, определяющий, обладает ли игрок выигрышной стратегией находясь в вершине v графа G.
-Алгоритм M(<G,v>):
+Алгоритм <tex> M ( \langle G, b \rangle ) </tex> :
 . Если из вершины, в которой находится игрок, не ведет ни одного ребра в непосещенные ранее вершины, то вернем FALSE, мы проиграли.

@@ Строка 34: / Строка 34: @@
 === Доказательство принадлежности задачи классу PSH ===
-Для доказательства этого факта сведем [[Интерпретация_БФ_с_кванторами_как_игры_для_двух_игроков|задачу об игре двух игроков ∃ и ∀]] в булевой КНФ-формуле с предваряющими кванторами (эта задача [[Класс_PS|PS-трудная]]) к Generalized Geography за полиномиальное время.
+Для доказательства этого факта сведем [[Интерпретация_БФ_с_кванторами_как_игры_для_двух_игроков|задачу об игре двух игроков <tex> \exists </tex> и <tex> \forall </tex>]] в булевой КНФ-формуле с предваряющими кванторами (эта задача [[Класс_PS|PS-трудная]]) к Generalized Geography за полиномиальное время.
-Для игры двух игроков ∃ и ∀ наша формула представима в следующем виде: φ = ∃''x''<sub>1</sub> ∀''x''<sub>2</sub> ∃''x''<sub>3</sub> ...∃''x<sub>n</sub>''(ψ) , где ψ - некая КНФ-формула.
+Если в нашей формуле с предваряющими кванторами последний квантор - не <tex> \exists </tex>, то добавим его, введя дополнительную переменную. Таким образом для игры двух игроков <tex> \exists </tex> и <tex> \forall </tex> наша формула представима в следующем виде:
-[[Файл:Generalized_geography_3.png|thumb|350px| Модель графа для сведения задачи об игре двух игроков ∃ и ∀ к задаче GG]]
+[[Файл:Generalized_geography_3.png|thumb|350px| Модель графа для сведения задачи об игре двух игроков <tex> \exists </tex> и <tex> \forall </tex> к задаче GG]]
-Для любой такой КНФ-формулы с предваряющими кванторами можно построить граф, аналогичный приведенному на рисунке. Рассмотрим этот граф, и докажем, что это сведение задачи об игре игроков ∃ и ∀ к задаче Generalized Geography.
+Для любой такой КНФ-формулы с предваряющими кванторами можно построить граф, аналогичный приведенному на рисунке. Рассмотрим этот граф, и докажем, что это сведение задачи об игре игроков <tex> \exists </tex> и <tex> \forall </tex> к задаче Generalized Geography.
-Левый столбец в этом графе описывает процедуру выборки игроками ∃ и ∀ значений переменных, если игрок выбирает TRUE, он идет в левую сторону, иначе в правую.
+Левый столбец в этом графе описывает процедуру выборки игроками <tex> \exists </tex> и <tex> \forall </tex> значений переменных, если игрок выбирает TRUE, он идет в левую сторону, иначе в правую.
-Зафиксировав значения переменных, игрок ∀ (т.к. в нашей КНФ-формуле с предваряющими кванторами последний квантор ∃) выбирает скобку, значение которой должно быть FALSE (тогда он выиграет!). На рисунке каждая скобка - отдельная вершина c<sub>i</sub>.
+Зафиксировав значения переменных, игрок <tex> \forall </tex> (т.к. в нашей КНФ-формуле с предваряющими кванторами последний квантор <tex> \exists </tex>) выбирает скобку, значение которой должно быть FALSE (тогда он выиграет!). На рисунке каждая скобка - отдельная вершина <tex> c_i </tex>.
-После того, как игрок ∀ зафиксировал скобку, игрок ∃ долджен выбрать переменную, значение которой не ноль (игроки уже зафиксировали значения переменных в самом начале) и сделать переход в соответсвующую вершинку. Т.к. значение этой переменной не ноль, то игрок ∀ не сможет никуда пойти из этой вершины (тогда ∃ выиграл, первый игрок обладает выигрышной стратегией в игре Generalized Geography). Для этого проведем ребра из каждый скобки c<sub>i</sub> в вершины-переменные, учавствующие в этой скобке, а от них проведем ребра к вершинам левого столбца, соответсвующим выборам TRUE или FALSE значений переменных.
+После того, как игрок <tex> \forall </tex> зафиксировал скобку, игрок <tex> \exists </tex> долджен выбрать переменную, значение которой не ноль (игроки уже зафиксировали значения переменных в самом начале) и сделать переход в соответсвующую вершинку. Т.к. значение этой переменной не ноль, то игрок <tex> \forall </tex> не сможет никуда пойти из этой вершины (тогда <tex> \exists </tex> выиграл, первый игрок обладает выигрышной стратегией в игре Generalized Geography). Для этого проведем ребра из каждый скобки <tex> c_i </tex> в вершины-переменные, учавствующие в этой скобке, а от них проведем ребра к вершинам левого столбца, соответсвующим выборам TRUE или FALSE значений переменных.
-Таким образом, если игрок ∃ выигрывает, то автоматически обладает выигрышной стратегией и первый игрок в Generalized Geography. Он знает, какие значения переменных надо выбрать, и в какую вершину пойти в конце. Аналогично, по выигрышной стратегии первого игрока в Generalized Geography можно узнать, какие значения переменных должен выбрать игрок ∃ для того, чтобы удовлетворить формулу.
+Таким образом, если игрок <tex> \exists </tex> выигрывает, то автоматически обладает выигрышной стратегией и первый игрок в Generalized Geography. Он знает, какие значения переменных надо выбрать, и в какую вершину пойти в конце. Аналогично, по выигрышной стратегии первого игрока в Generalized Geography можно узнать, какие значения переменных должен выбрать игрок <tex> \exists </tex> для того, чтобы удовлетворить формулу.
-Мы свели задачу об игре игроков ∃ и ∀ к задаче Generalized Geography. Значит, язык GG является PS-трудным, а так как выше мы доказали его принадлежность классу PS, то и PS-полным.
+Мы свели задачу об игре игроков <tex> \exists </tex> и <tex> \forall </tex> к задаче Generalized Geography. Очевидно, сведение будет произведено за полиномиальное время. Значит, язык GG является PS-трудным, а так как выше мы доказали его принадлежность классу PS, то и PS-полным.