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