Связь задач с кванторами с игровыми задачами
9.5.
Доказательство PSPACE-полноты задач 547условий длины 3. Два игрока поочередно выбирают значения переменных: пер- вый игрок выбирает значение x1, затем второй игрок выбирает значение x2, потом первый выбирает значение x3 и т. д. Считается, что первый игрок побеждает, если при вычислении Ф(xp ··· , xn) будет получен результат 1, а второй — если результат равен 0.
Когда у первого игрока имеется форсированная победа в этой игре (то есть когда наш экземпляр конкурентной задачи 3-SAT имеет положительный ответ)? Тогда, когда существует такой выбор x1, что при всех вариантах выбора x2 суще- ствует такой выбор x3, что... и т. д., при котором Ф(x1, ··· , xn) дает результат 1. То есть форсированная победа первого игрока возможна в том, и только в том случае, если (в предположении, что n является нечетным числом)
⅝⅛*"⅜⅛ЧФ(х,.............
Другими словами, конкурентная задача 3-SAT эквивалентна экземпляру QSAT, определяемому по той же булевой формуле Ф, поэтому мы доказали следующее утверждение:
(9.10) QSAT
Еще по теме Связь задач с кванторами с игровыми задачами:
- ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
- 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
- Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
- ЗАДАЧА
- ЗАДАЧА: РЕШЕНИЕ
- Основные задачи.
- в) Задачи
- в) Задачи
- ПСИХОАНАЛИЗ: ЗАДАЧА
- ЗАДАЧА ДВИГАТЕЛЬНАЯ
- Основные задачи
- Правило решаемой психологической задачи.
- Задачи и упражнения
- Терапевтическая задача
- Задачи и упражнения
- 3. Задачи и функции социологии
- Основные задачи МПП.