Доказательство PSPACE-полноты задачи конкурентного размещения

Утверждение (9.10) открывает путь в мир игровых задач. Мы воспользуемся этой связью для доказательства PSPACE-полноты задачи конкурентного размещения.

(9.11) Задача конкурентного размещения является PSPACE-полной.

Доказательство. Мы уже показали, что задача конкурентного размещения принадлежит PSPACE. Чтобы доказать ее PSPACE-полноту, мы теперь покажем, что Конкурентная задача 3-SAT ≤P Конкурентное размещение, и тем самым установим ее PSPACE-полноту.

Имеется экземпляр конкурентной задачи 3-SAT, определяемый формулой.

Каждое условие Cj имеет длину 3 и может быть записано в виде Cj = tj1 Ҏ tj2 Ҏ tj3. Как и прежде, будем считать, что количество переменных n нечетно. Также будем полагать (по естественным причинам), что никакое условие не содержит литерал одновременно с его отрицанием; в конце концов, такое условие автоматически выполняется любым логическим присваиванием.

Мы должны показать, как закодировать эту логическую структуру в графе, лежащем в основе задачи конкурентного размещения.

Экземпляр конкурентной задачи 3-SAT можно закодировать в следующем виде. Игроки поочередно выбирают значения в логическом присваивании, начиная и заканчивая игроком 1; в конце игрок 2 выигрывает, если он выберет условие Cj, котором ни одному литералу не было задано значение 1. Игрок 1 выигрывает, если игроку 2 это сделать не удастся.

В такой формулировке нам хотелось бы закодировать экземпляр задачи конкурентного размещения: игроки поочередно делают фиксированное количество ходов, и в конце существует вероятность того, что игрок 2 победит.

Но в общей формулировке задача конкурентного размещения выглядит намного более открытой. Если игроки в конкурентной задаче 3-SAT должны задавать по одной переменной в строгом порядке, игроки в задаче конкурентного размещения могут перемещаться по всему графу, выбирая любые узлы на свое усмотрение.