В теоретической информатике недетерминированная логика ограничений — это комбинаторная система, в которой рёбрам взвешенного неориентированного графа дана ориентация , при условии соблюдения определённых ограничений. Можно изменить эту ориентацию шагами, в которых одно ребро меняет направление, при условии соблюдения тех же ограничений. Это форма обратимой логики , в которой каждая последовательность изменений ориентации рёбер может быть отменена.
Задачи реконфигурации для логики ограничений, требующие последовательности ходов для соединения определенных состояний, соединения всех состояний или изменения направления указанного ребра, как было доказано, являются PSPACE-полными . Эти результаты по сложности формируют основу для доказательств того, что различные игры и головоломки являются PSPACE-полными или PSPACE-сложными.
В простейшей версии недетерминированной логики ограничений каждое ребро неориентированного графа имеет вес один или два. (Веса также можно изобразить графически, нарисовав ребра веса один красными, а ребра веса два — синими.) Граф должен быть кубическим : каждая вершина инцидентна трем ребрам, и, кроме того, каждая вершина должна инцидентна четному числу красных ребер. [2]
Ребра должны быть ориентированы таким образом, чтобы по крайней мере две единицы веса были ориентированы на каждую вершину: должно быть либо по крайней мере одно входящее синее ребро, либо по крайней мере два входящих красных ребра. Ориентация может меняться шагами, в которых одно ребро переворачивается, соблюдая эти ограничения. [2]
Более общие формы недетерминированной логики ограничений допускают большее разнообразие весов ребер, больше ребер на вершину и различные пороги для того, какой входящий вес должна иметь каждая вершина. Граф с системой весов ребер и порогов вершин называется графом ограничений . Ограниченный случай, когда веса ребер равны одному или двум, вершины требуют две единицы входящего веса, и все вершины имеют три инцидентных ребра с четным числом красных ребер, называется и/или графами ограничений . [2]
Причина названия и/или графов ограничений заключается в том, что два возможных типа вершин в графе ограничений и/или ведут себя в некотором роде как вентиль И и вентиль ИЛИ в булевой логике . Вершина с двумя красными ребрами и одним синим ребром ведет себя как вентиль И в том смысле, что она требует, чтобы оба красных ребра указывали внутрь, прежде чем синее ребро можно будет заставить указывать наружу. Вершина с тремя синими ребрами ведет себя как вентиль ИЛИ, причем два ее ребра обозначены как входы, а третье как выход, в том смысле, что она требует, чтобы по крайней мере одно входное ребро указывало внутрь, прежде чем выходное ребро можно будет заставить указывать наружу. [2]
Обычно проблемы логики ограничений определяются вокруг поиска допустимых конфигураций графов ограничений. Графы ограничений — это неориентированные графы с двумя типами ребер:
Мы используем графы ограничений в качестве моделей вычислений, где мы думаем о всем графе как о машине. Конфигурация машины состоит из графа вместе с определенной ориентацией его ребер. Мы называем конфигурацию действительной, если она удовлетворяет ограничению входящего потока: каждая вершина должна иметь входящий вес не менее . Другими словами, сумма весов ребер, которые входят в данную вершину, должна быть по крайней мере больше суммы весов ребер, которые выходят из вершины.
Мы также определяем перемещение в графе ограничений как действие по изменению ориентации ребра таким образом, чтобы полученная конфигурация оставалась действительной.
Предположим, что нам дан граф ограничений, начальная конфигурация и конечная конфигурация. Эта задача спрашивает, существует ли последовательность допустимых ходов, которые перемещают его из начальной конфигурации в конечную. Эта задача является PSPACE-полной для 3-регулярных или графов максимальной степени 3. [3] Сокращение следует из QSAT и описано ниже.
Вышеуказанная задача является PSPACE-полной, даже если граф ограничений является планарным , т.е. граф нельзя нарисовать таким образом, чтобы никакие два ребра не пересекали друг друга. Это сокращение следует из Planar QSAT .
Эта задача является частным случаем предыдущей. Она спрашивает, возможно ли, учитывая граф ограничений, обратить указанное ребро с помощью последовательности допустимых ходов. Обратите внимание, что это можно сделать с помощью последовательности допустимых ходов, пока последний допустимый ход обращает желаемое ребро. Также было доказано, что эта задача является PSPACE-полной для 3-регулярных или графов максимальной степени 3. [3]
Эта задача спрашивает, существует ли ориентация ребер, которая удовлетворяет ограничениям входящего потока, заданным неориентированным графом . Было доказано, что эта задача является NP-полной. [3]
Следующие задачи на графах ограничений и их ориентациях являются PSPACE-полными: [2]
Доказательство того, что эти проблемы сложны, включает сокращение от квантифицированных булевых формул , основанное на логической интерпретации и/или графов ограничений. Это требует дополнительных гаджетов для моделирования квантификаторов и для преобразования сигналов, передаваемых по красным ребрам, в сигналы, передаваемые по синим ребрам (или наоборот), что может быть достигнуто путем комбинаций вершин и и вершин или. [2]
Эти проблемы остаются PSPACE-полными даже для и/или графов ограничений, которые образуют планарные графы . Доказательство этого включает в себя построение кроссоверных гаджетов, которые позволяют двум независимым сигналам пересекать друг друга. Также можно наложить дополнительное ограничение, сохраняя при этом сложность этих проблем: каждая вершина с тремя синими ребрами может быть потребована, чтобы быть частью треугольника с красным ребром. Такая вершина называется защищенной или , и она обладает тем свойством, что (в любой допустимой ориентации всего графа) невозможно, чтобы оба синих ребра в треугольнике были направлены внутрь. Это ограничение упрощает моделирование этих вершин в снижениях сложности для других проблем. [2] Кроме того, графы ограничений могут быть потребованы, чтобы иметь ограниченную полосу пропускания , и проблемы на них по-прежнему останутся PSPACE-полными. [4]
Сокращение следует из QSAT. Чтобы встроить формулу QSAT, нам нужно создать гаджеты AND, OR, NOT, UNIVERSAL, EXISTENTIAL и Converter (для изменения цвета) в графе ограничений. Идея заключается в следующем:
Другие гаджеты также могут быть созданы таким образом. Полная конструкция доступна на веб-сайте Эрика Демейна . [5] Полная конструкция также объясняется в интерактивном режиме. [6]
Первоначальные приложения недетерминированной логики ограничений использовали ее для доказательства полноты PSPACE головоломок со скользящими блоками , таких как Rush Hour и Sokoban . Чтобы сделать это, нужно только показать, как моделировать ребра и ориентации ребер, вершины и защищенные вершины в этих головоломках. [2]
Недетерминированная логика ограничений также использовалась для доказательства сложности версий реконфигурации классических задач оптимизации графов, включая независимый набор , покрытие вершин и доминирующий набор , на планарных графах с ограниченной пропускной способностью. В этих задачах необходимо изменить одно решение данной проблемы на другое, перемещая одну вершину за раз в набор решений или из него, сохраняя при этом свойство, что в любой момент времени оставшиеся вершины образуют решение. [4]
При наличии формулы 3-CNF и двух удовлетворяющих назначений эта задача спрашивает, возможно ли найти последовательность шагов, которая приведет нас от одного назначения к другим, где на каждом шаге нам разрешено менять значение переменной. Эту задачу можно показать как PSPACE-полную с помощью редукции из задачи Non-deterministic Constraint Logic. [3]
Эта задача спрашивает, можем ли мы достичь желаемой конфигурации в головоломке с скользящими блоками, учитывая начальную конфигурацию блоков. Эта задача является PSPACE-полной, даже если прямоугольники являются домино. [2]
Эта задача спрашивает, можем ли мы достичь условия победы в головоломке «час пик» при заданной начальной конфигурации. Эта задача является PSPACE-полной, даже если блоки имеют размер . [3]
При наличии статической карты эта проблема спрашивает, существует ли гладкая динамическая маркировка. Эта проблема также является PSPACE-полной. [7]
