Доказательство PSPACE-полноты задач - PSPACE: класс задач за пределами NP

В начале изучения NP нам пришлось доказать NP-полноту первой задачи прямо из определения NP. После того как Кук и Левин сделали это для выполнимости, ученые могли применить эту схему сведения ко многим другим NP-полным задачам.

Вскоре после публикации результатов для NP аналогичные события происходили и для PSPACE. Вспомните, что мы определили PSPACE-полноту по прямой аналогии с NP-полнотой в разделе 9.1. Естественной аналогией для задачи выполнимости булевых схем или 3-SAT для PSPACE является задача QSAT; Стокмейер и Мейер (1973) доказали:

(9.9) Задача QSAT является PSPACE-полной.

Базовая PSPACE-полная задача служит хорошим “корнем”, от которого начинается поиск других PSPACE-полных задач. По четкой аналогии с NP из определения легко увидеть, что если задача Y является PSPACE-полной и задача X в PSPACE обладает свойством Y≤_PX, то задача X также является PSPACE-полной.

В этом разделе мы приведем пример такого доказательства PSPACE-полноты для задачи конкурентного размещения; для этого задача QSAT будет сведена к задаче конкурентного размещения. Помимо установления сложности задачи конкурентного размещения, сведение также дает представление о том, как следует подходить к демонстрации PSPACE-полноты для игр вообще на основании их близкой связи с кванторами.

Заметим, что PSPACE-полнота задачи построения плана также может быть продемонстрирована сведением от QSAT, но здесь это доказательство не приводится.

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

Не приходится удивляться ТОМУ, что между задачами с кванторами и игровыми задачами существует тесная связь. В самом деле, задачу QSAT можно было бы эквивалентно определить как задачу принятия решения о том, имеет ли первый игрок форсированный выигрыш в следующем “игровом варианте” 3-SAT: допустим, мы фиксируем формулу Ф(х₁, ..., x_n), которая состоит, как и в QSAT, из конъюнкции условий длины 3. Два игрока поочередно выбирают значения переменных: первый игрок выбирает значение х₁, затем второй игрок выбирает значение x₂, потом первый выбирает значение х₃ и т. д. Считается, что первый игрок побеждает, если при вычислении Ф(х₁, ..., x_n) будет получен результат 1, а второй — если результат равен 0.

Когда у первого игрока имеется форсированная победа в этой игре (то есть когда наш экземпляр конкурентной задачи 3-SAT имеет положительный ответ)? Тогда, когда существует такой выбор х₁, что при всех вариантах выбора х₂ существует такой выбор х₃, что... и т. д., при котором Ф(х₁, ..., x_n) дает результат 1. То есть форсированная победа первого игрока возможна в том, и только в том случае, если (в предположении, что n является нечетным числом)

Другими словами, конкурентная задача 3-SAT эквивалентна экземпляру QSAT, определяемому по той же булевой формуле Ф, поэтому мы доказали следующее утверждение:

(9.10) QSAT ≤_р Конкурентная задача3-SAT и Конкурентная задача3-SAT≤_рQSAT.

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

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

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

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

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

C₁ Λ C₂ Λ ... Λ C_k.

Каждое условие C_j имеет длину 3 и может быть записано в виде Как и прежде, будем считать, что количество переменных n нечетно. Также будем полагать (по естественным причинам), что никакое условие не содержит литерал одновременно с его отрицанием; в конце концов, такое условие автоматически выполняется любым логическим присваиванием. Мы должны показать, как закодировать эту логическую структуру в графе, лежащем в основе задачи конкурентного размещения.

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

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

Для решения этой проблемы мы воспользуемся значениями b_i узлов, которые будут ограничивать возможности перемещения игроков при любой “разумной” стратегии. Иначе говоря, все будет настроено так, что при отклонении любого из игроков от конкретного узкого пути он моментально проигрывает.

Как и в случае с более сложными сведениями NР-полноты в главе 8, наше построение будет содержать регуляторы, представляющие присваивание переменным, и другие регуляторы для представления условий. Переменные будут кодироваться следующим образом: для каждой переменной х_i в графе G определяются два узла v_i, v'_i, а также ребро (v_i, v'_i), как показано на рис. 9.2. Выбор v_i представляет присваивание х_i = 1; выбор v'_i представляет х_i = 0. Ограничение, согласно которому выбранные переменные должны образовать независимое множество, естественным образом предотвращают одновременный выбор v_i и v'_i. В этой точке никакие другие ребра не определяются.

Рис. 9.2. Сведение конкурентной задачи 3-SAT к задаче конкурентного размещения

Как заставить игроков задавать переменные по порядку — сначала х₁, затем х₂ и т. д.? Значения v₁ и v'₁задаются настолько высокими, что если игрок 1 не выберет их, он немедленно проиграет. Для v₂ и v'₂устанавливаются значения поменьше, и т. д. А именно: для с ≥ k + 2 мы определяем значения узлов b_vi и b_v'i, равными с^1+n-i. Граница, которую игрок 2 пытается достичь, определяется равной

Прежде чем переходить к условиям, остановимся на игре, которая играется на этом графе. Первым ходом игрок 1 должен выбрать один из узлов v₁ или v'₁ (тем самым отказываясь от другого); в противном случае игрок 2 немедленно выберет один из этих узлов для своего следующего хода и немедленно выиграет. Аналогичным образом вторым ходом игрок 2 должен выбрать один из узлов v₂ или v'₂, иначе игрок 1 выберет его следующим ходом; и тогда, даже если игрок 2 заберет все остальные узлы графа, он не сможет выполнить границу B. Продолжая индукцию, мы видим, что для предотвращения неизбежного проигрыша игрок, делающий i-й ход, должен выбрать один из узлов v_i или v'_i. С таким выбором узлов мы добиваемся ровно того эффекта, который был нужен: игроки должны задавать переменные по очереди. И каким же будет результат для этого графа? Игрок 2 завершает игру с суммой c^n-1 + c^n-3 + ... + с² = B - 1: он проиграл на одну единицу!

Завершим аналогию с конкурентной задачей 3-SAT, предоставляя игроку 2 один последний ход, которым он может попытаться выиграть. Для каждого условия С_j определяется узел с_j со значением b_cj = 1 и ребром, связанным с каждым из его литералов, следующим образом: если t = х_i, добавляется ребро (с_j, v_i); если добавляется ребро (с_j, v'_i). Другими словами, мы присоединяем с_j к узлу, который представляет литерал t.

Так определяется полный граф G. Мы можем убедиться в том, что из-за малых значений добавление узлов условий не изменило то свойство, что игроки начинают с выбора узлов переменных {v_i, v'_i} в правильном порядке. Однако после того, как это будет сделано, игрок 2 победит в том, и только в том случае, если он сможет выбрать узел условия с_j, не смежный ни с одним узлом выбранной переменной, — другими словами, в том, и только в том случае, если логическое присваивание, попеременно определяемое игроками, не выполняет никакого условия.

Таким образом, игрок 2 может победить в определенном нами экземпляре задачи конкурентного размещения в том, и только в том случае, если он сможет победить в исходном экземпляре конкурентной задачи 3-SAT. Сведение завершено. ■