<<
>>

Связь задач с кванторами с игровыми задачами

Не приходится удивляться томy, что между задачами с кванторами и игровыми задачами существует тесная связь. В самом деле, задачу QSAT можно было бы эк- вивалентно определить как задачу принятия решения о том, имеет ли первый игрок форсированный выигрыш в следующем «игровом варианте» 3-SAT: допустим, мы фиксируем формулу Ф(x1, ··· , xn), которая состоит, как и в QSAT, из конъюнкции

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

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Связь задач с кванторами с игровыми задачами:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  11. Основные задачи
  12. Правило решаемой психологической задачи.
  13. Задачи и упражнения
  14. Терапевтическая задача
  15. Задачи и упражнения
  16. 3. Задачи и функции социологии
  17. Основные задачи МПП.