Логика недетерминированных ограничений - Википедия - Nondeterministic constraint logic

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

Это форма обратимая логика в том, что каждая последовательность изменений ориентации кромки может быть отменена. Сложность этой проблемы была использована для доказательства того, что многие игры и головоломки имеют высокую сложность игры.

Графики ограничений

Логический элемент И в логике ограничений. Поскольку минимальная внутренняя степень узла равна 2, верхний край может быть вне, если и только если два нижних края входят.

Пример графа ограничений.^[1]

В простейшей версии недетерминированной логики ограничений каждое ребро неориентированного графа имеет вес один или два. (Веса также можно представить графически, нарисовав ребра веса один красным, а ребра веса два - синим.) График должен быть кубический граф: каждая вершина инцидентна трем ребрам, и дополнительно каждая вершина должна быть инцидентна четному количеству красных ребер.^[2]

Ребра должны быть ориентированы таким образом, чтобы по крайней мере две единицы веса были ориентированы на каждую вершину: должно быть либо хотя бы одно входящее синее ребро, либо как минимум два входящих красных ребра. Ориентация может меняться ступенчато, когда одна кромка переворачивается, соблюдая эти ограничения.^[2]

Более общие формы недетерминированной логики ограничений допускают большее разнообразие весов ребер, большее количество ребер на вершину и разные пороговые значения того, сколько входящего веса должна иметь каждая вершина. Граф с системой весов ребер и порогов вершин называется граф ограничений. Ограниченный случай, когда веса всех ребер равны одному или двум, вершинам требуется две единицы входящего веса, а все вершины имеют три инцидентных ребра с четным числом красных ребер, называются и / или графы ограничений.^[2]

Причина названия и / или графы ограничений состоит в том, что два возможных типа вершин в графе и / или графе ограничений ведут себя некоторым образом как И ворота и ИЛИ ворота в Логическая логика. Вершина с двумя красными ребрами и одним синим ребром ведет себя как логический элемент И в том смысле, что требуется, чтобы оба красных ребра указывали внутрь, прежде чем можно будет заставить синий край указывать наружу. Вершина с тремя синими ребрами ведет себя как логический элемент ИЛИ, причем два его ребра обозначены как входы, а третье - как выход, поскольку для этого требуется, чтобы по крайней мере одно входное ребро указывало внутрь, прежде чем выходное ребро может указывать наружу.^[2]

Обычно проблемы логики ограничений определяются вокруг поиска допустимых конфигураций графов ограничений. Графы ограничений - это неориентированные графы с двумя типами ребер:

красные края с грузом ${ displaystyle 1}$
синие края с грузом ${ displaystyle 2}$

Мы используем графы ограничений в качестве моделей вычислений, где мы думаем обо всем графе как о машине. А конфигурация машины состоит из графа с определенной ориентацией его ребер. Мы называем конфигурацию допустимой, если она удовлетворяет ограничению притока: каждая вершина должна иметь входящий вес не менее ${ displaystyle 2}$ . Другими словами, сумма весов ребер, входящих в данную вершину, должна быть не менее ${ displaystyle 2}$ больше суммы весов ребер, выходящих из вершины.

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

Формальное определение проблемы логики ограничений

Предположим, нам дан граф ограничений, начальная конфигурация и конечная конфигурация. Эта проблема спрашивает, существует ли последовательность допустимых перемещений, которые перемещают ее из начальной конфигурации в конечную конфигурацию. Эта проблема является PSPACE-Complete для 3-регулярных графов или графов максимальной степени 3.^[3] Приведение следует из QSAT и описан ниже.

Варианты

Планарная недетерминированная логика ограничений

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

Смена края

Эта проблема - частный случай предыдущей. При заданном графе ограничений он спрашивает, можно ли перевернуть заданное ребро с помощью последовательности допустимых ходов. Обратите внимание, что это может быть сделано с помощью последовательности допустимых ходов, если последний допустимый ход переворачивает желаемое ребро. Также было доказано, что эта проблема является PSPACE-Complete для 3-регулярных графов или графов максимальной степени 3.^[3]

Удовлетворение графа ограничений

Эта проблема спрашивает, существует ли ориентация ребер, которая удовлетворяет ограничениям притока для неориентированного графа. ${ displaystyle G}$ . Доказано, что эта проблема является NP-полной.^[3]

Сложные проблемы

Следующие задачи, касающиеся графов и / или ограничений и их ориентации, являются PSPACE-полными:^[2]

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

Доказательство сложности этих проблем включает в себя снижение из количественные булевы формулы на основе логической интерпретации графов и / или ограничений. Это требует дополнительных гаджеты для моделирования кванторы и для преобразования сигналов, переносимых по красным краям, в сигналы, переносимые по синим краям (или наоборот), что может быть выполнено комбинациями и-вершин и или-вершин.^[2]

Эти проблемы остаются PSPACE-завершенными даже для графов ограничений и / или графов ограничений, которые образуют планарные графы. Доказательство этого заключается в создании кроссоверных устройств, которые позволяют двум независимым сигналам пересекаться друг с другом. Также возможно наложить дополнительное ограничение, сохранив при этом сложность этих задач: каждая вершина с тремя синими ребрами может быть обязана быть частью треугольника с красным ребром. Такая вершина называется защищенный или, и он обладает тем свойством, что (при любой допустимой ориентации всего графа) оба синих ребра в треугольнике не могут быть направлены внутрь. Это ограничение упрощает моделирование этих вершин в снижении жесткости для других задач.^[2] Кроме того, может потребоваться, чтобы графы ограничений имели ограниченные пропускная способность, и проблемы на них все равно останутся PSPACE-завершенными.^[4]

Подтверждение твердости PSPACE

Уменьшение следует из QSAT. Чтобы встроить формулу QSAT, нам нужно создать гаджеты AND, OR, NOT, UNIVERSAL, EXISTENTIAL и Converter (для изменения цвета) в графе ограничений. Идея следующая:

Вершина AND - это вершина, у которой есть два инцидентных красных ребра (входные) и одно синее инцидентное ребро (выход).
Вершина ИЛИ - это вершина, у которой есть три инцидентных синих ребра (два входа, один выход).

Остальные гаджеты также могут быть созданы таким же образом. Полная конструкция доступна в Эрик Демейн веб-сайт^[5]. Полная конструкция также объясняется в интерактивном режиме.^[6].

Приложения

Первоначальные приложения недетерминированной логики ограничений использовали ее для доказательства PSPACE-полноты головоломки с раздвижными блоками Такие как Час пик и Сокобан. Для этого нужно только показать, как моделировать ребра и ориентацию ребер, и вершины, и защищенные вершины или вершины в этих головоломках.^[2]

Недетерминированная логика ограничений также использовалась, чтобы доказать твердость реконфигурация версии классических задач оптимизации графов, включая независимый набор, крышка вершины, и доминирующий набор, на плоских графах с ограниченной пропускной способностью. В этих задачах нужно заменить одно решение данной проблемы другим, перемещая по одной вершине в набор решений или из него, сохраняя при этом свойство, что все время оставшиеся вершины образуют решение.^[4]

Реконфигурация 3SAT

Учитывая 3-CNF формула и два удовлетворительных присваивания, эта задача спрашивает, можно ли найти последовательность шагов, которые переводят нас от одного присваивания к другому, где на каждом шаге нам разрешено переворачивать значение переменной. Эту проблему можно показать PSPACE-завершенной через сокращение от проблемы недетерминированной логики ограничений.^[3]

Головоломки со скользящими блоками

Эта проблема спрашивает, можем ли мы достичь желаемой конфигурации в раздвижной блок головоломки учитывая начальную конфигурацию блоков. Эта задача является PSPACE-полной, даже если прямоугольники представляют собой домино.^[7]

Час пик

Эта проблема спрашивает, можем ли мы достичь условия победы час пик пазл учитывая начальную конфигурацию. Эта проблема является PSPACE-полной, даже если блоки имеют размер ${ Displaystyle 1 раз 2}$ .^[3]

Маркировка динамической карты

Учитывая статическую карту, эта проблема спрашивает, есть ли плавная динамическая маркировка. Эта проблема также является PSPACE-завершенной.^[8]