Изменения
Нет описания правки
=== Доказательство принадлежности задачи классу 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> выигрывает, то автоматически обладает выигрышной стратегией и первый игрок в Generalized Geography. Он знает, какие значения переменных надо выбрать, и в какую вершину пойти в конце. Аналогично, по выигрышной стратегии первого игрока в Generalized Geography можно узнать, какие значения переменных должен выбрать игрок <tex> \exists </tex> для того, чтобы удовлетворить формулу.
Мы свели задачу об игре игроков <tex> \exists </tex> и <tex> \forall </tex> к задаче Generalized Geography. Очевидно, сведение будет произведено за полиномиальное время. Значит, язык <tex> GG </tex> является PS-трудным, а так как выше мы доказали его принадлежность классу PS, то и PS-полным. == Внешние ссылки == [http://en.wikipedia.org/wiki/Generalized_geography Generalized Geography в английской википедии. ]
