17
правок
Изменения
ссылки
=== Доказательство принадлежности задачи классу PSH ===
Для доказательства этого факта сведем [[Интерпретация_БФ_с_кванторами_как_игры_для_двух_игроков|задачу об игре двух игроков ∃ и ∀ ]] в булевой КНФ-формуле с предваряющими кванторами (эта задача [[Класс_PS|PS-трудная]]) к Generalized Geography за полиномиальное время.
Для игры двух игроков ∃ и ∀ наша формула представима в следующем виде: φ = ∃''x''<sub>1</sub> ∀''x''<sub>2</sub> ∃''x''<sub>3</sub> ...∃''x<sub>n</sub>''(ψ) , где ψ - некая КНФ-формула.
