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