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