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

Рассмотрим естественные примеры задач из PSPACE, которые, как принято считать, не принадлежат ни NP, ни co-NP.

Как и в случае с NP, чтобы разобраться в структуре PSPACE, можно рассмотреть конкретные задачи — самые сложные в классе. Задача X называется PSPACE-полной, если (i) она принадлежит PSPACE и (ii) для всех задач Y в PSPACE выполняется Y ≤_P X.

Оказывается, как и в случае с NP, существует широкий диапазон естественных задач, которые являются PSPACE-полными. Многие базовые задачи в области искусственного интеллекта являются PSPACE-полными; ниже описаны три категории таких задач.

Задачи построения плана

Задачи построения плана отражают процесс взаимодействия со сложной средой для достижения заданных целей. К каноническим примерам такого рода относятся крупные логистические операции, связанные с перемещением людей, оборудования и материалов. Например, при координации помощи при стихийных бедствиях может быть принято решение о том, что на определенной высоте над уровнем моря нужны двадцать машин “скорой помощи”. Но чтобы решить эту задачу, нужно сначала подогнать десять снегоуборочных машин для расчистки дороги; этот этап, в свою очередь, требует заправки снегоуборочных машин и доставки водителей; но если израсходовать топливо для снегоуборочных машин, его может не хватить для “скорой помощи”; а если... в общем, вы поняли. Военные операции также требуют координации в большом масштабе, и методы автоматизированного планирования из области искусственного интеллекта успешно применялись для решения таких задач.

Очень похожие проблемы встречаются в сложных головоломках для одного игрока: например, в кубике Рубика или головоломке “15” — сетке 4 х 4 с 15 перемещаемыми плитками 1, 2, ..., 15 и одним пустым местом — перемещая плитки, игрок должен выстроить числа по возрастанию. (Вместо машин “скорой помощи” и снегоуборочных машин в этой задаче речь идет о таких операциях, как перемещение плитки 6 на одну позицию влево; но для этого нужно убрать с пути плитку 11, а для этого нужно переместить 9, которая находится в хорошем месте; и т. д.) Даже эти “игрушечные” задачи порой оказываются весьма нетривиальными и часто используются в области искусственного интеллекта для тестирования координационных алгоритмов.

Как же с учетом сказанного определить задачу построения плана на достаточно общем уровне, включающем все эти примеры? И у головоломок, и у помощи при стихийных бедствиях имеются некоторые общие абстрактные черты: есть ряд условий, которые достигаются в результате принятия решений, и множество допустимых операций, которые к этим условиям применяются. Таким образом, окружение моделируется множеством С = {С₁, ..., C_n} условий: общее “состояние окружающего мира” задается подмножеством условий, действующих на данный момент. Для взаимодействия с окружением используются операторы, образующие множество {O₁, ..., O_k}. Каждый оператор O_i определяется множеством предусловий, которые должны выполняться для выполнения O_i; списком добавления — множеством условий, которые станут истинными после выполнения O_i; и списком удаления — множеством условий, которые перестают действовать после выполнения O Например, при моделировании головоломки “15” можно определить условие для каждого возможного положения каждой плитки и оператор для перемещения каждой плитки между двумя парами соседних положений; предусловие для оператора заключается в том, что в двух указанных позициях должны находиться плитка и пустое место.

Обобщенная задача выглядит так: дано множество С₀ начальных условий и множество С* целевых условий; возможно ли применить последовательность операторов, начиная с С₀, и достичь ситуации, в которой выполняются только условия С* (и никакие другие)? Назовем эту формулировку задачей построения плана.

Кванторы

Как вы убедились в задаче 3-SAT, проверка возможности одновременного выполнения множества дизъюнктивных условий создает немалые трудности. С добавлением кванторов задача только усложняется.

Пусть Ф(х₁, ..., x_n) — булева формула вида

где каждый компонент С_i является дизъюнкцией трех литералов (другими словами, это экземпляр задачи 3-SAT). Для простоты будем считать, что n — нечетное число; задается вопрос:

То есть мы хотим знать, существует ли для x₁ такой выбор, что для обоих вариантов выбора х₂ существует выбор х₃... и т. д., чтобы в итоге выполнялось Ф? Назовем эту задачу задачей 3-SAT с кванторами, или сокращенно QSAT.

Для сравнения, исходная задача 3-SAT задавала вопрос:

Другими словами, в задаче 3-SAT было достаточно найти одно значение для булевых переменных.

Следующий пример демонстрирует рассуждения, лежащие в основе экземпляра QSAT. Предположим, имеется формула

и задается вопрос:

Ответ на вопрос положителен: мы присваиваем х₁ такое значение, чтобы для обоих вариантов х₂ можно было задать х₃ так, чтобы выполнялось Ф. А именно: можно присвоить х₁ = 1; если затем х₂ присваивается 1, то х₃ можно присвоить 0 (с выполнением всех условий); а если х₂ присваивается 0, х₃ можно присвоить 1 (снова с выполнением всех условий).

Задачи такого типа с кванторами возникают естественным образом как разновидность ситуационного планирования — мы хотим знать, можно ли принять такое решение (выбор х₁), чтобы для всех возможных реакций (выбор х₂) можно было принять решение (выбор х₃)... и т. д.

Игры

В 1996 и 1997 годах в СМИ чемпиона мира по шахматам Гарри Каспарова называли защитником человеческой расы, когда он противостоял программе IBM Deep Blue в двух шахматных матчах. Даже один этот пример убедительно показывает, что интеллектуальные игры стали одним из самых заметных успехов в области современного искусственного интеллекта.

Многие игры для двух участников естественным образом укладываются в следующую схему: игроки ходят по очереди, и первый, кто достигает конкретной цели, выигрывает (такой целью может быть мат королю, захват всех шашек противника, построение ряда из четырех фишек и т. д.). Кроме того, часто существует естественная полиномиальная верхняя граница для максимально возможной длины игры.

Задача конкурентного размещения, упоминавшаяся в главе 1, естественно укладывается в эту структуру (а заодно показывает, что игры могут пригодиться не только для времяпрепровождения, но и в конкурентных ситуациях в повседневной жизни). Вспомните, что в задаче конкурентного размещения задается граф G с неотрицательным значением b, связанным с каждым узлом i. Два игрока поочередно выбирают узлы G, так что множество выбранных узлов в любой момент образует независимое множество. Игрок 2 побеждает, если ему удастся выбрать узлы с суммарным значением не менее B для заданной границы B; игрок 1 побеждает, если ему удастся этому помешать. Вопрос: существует ли для заданного графа G и границы B стратегия, с которой игрок 2 может обеспечить себе выигрыш?