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

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

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

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

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

Пример графа ограничений.

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

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

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

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

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

• красные края с весом $1$
• синие края с весом $2$

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

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

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

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

Варианты

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

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

Реверс края

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

Удовлетворенность графиком ограничений

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

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

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

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

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

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

Доказательство твердости PSPACE

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

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

Таким же образом можно создать и другие гаджеты. Полная конструкция доступна на Эрика Демейна . сайте Полная конструкция также объясняется в интерактивном режиме.

Приложения

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

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

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

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

Головоломки с раздвижными блоками

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

Час Пик

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

Динамическая маркировка карт

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