Введение

Сложность задач об удовлетворимости ограничений — это применение теории вычислительной сложности к задачам об удовлетворимости ограничений. В основном она изучалась для разграничения между вычислительно разрешимыми и неразрешимыми классами задач об удовлетворимости ограничений на конечных областях. Решение задачи об удовлетворимости ограничений на конечном домене в общем случае является NP-полной задачей. Исследования выявили ряд частных случаев, решаемых за полиномиальное время, в основном благодаря ограничению допустимых областей, типов ограничений или способов наложения ограничений на переменные. Также установлена связь между задачей об удовлетворимости ограничений и задачами в других областях, таких как теория конечных моделей и базы данных.

Обзор

Установление того, имеет ли решение задача об удовлетворении ограничений на конечном домене, является NP-полной задачей в общем случае. Это является прямым следствием того, что ряд других NP-полных задач можно представить в виде задач об удовлетворении ограничений. К таким задачам относятся выполнимость булевых формул и задача о раскраске графа в три цвета. Достижение вычислительной эффективности возможно при рассмотрении специфических классов задач об удовлетворении ограничений. Например, если домен двоичный и все ограничения двоичные, то проверка выполнимости является задачей, разрешимой за полиномиальное время, поскольку эта задача эквивалентна задаче 2-SAT, которая также разрешима за полиномиальное время. Одно из направлений исследований использует соответствие между задачей об удовлетворении ограничений и задачей установления существования гомоморфизма между двумя реляционными структурами. Это соответствие позволило связать задачи об удовлетворении ограничений с областями, традиционно относящимися к теории баз данных. Рассматриваемая исследовательская проблема связана с существованием дихотомий среди множеств ограничений. Суть вопроса заключается в том, содержит ли данное множество ограничений только ограничения, разрешимые за полиномиальное время, и NP-полные ограничения. Для реляционных ограничений (см. ниже) этот вопрос был положительно решен для булевых доменов теоремой о дихотомии Шефера, а для любого конечного домена – Андреем Булатовым и Дмитрием Жуком, независимо друг от друга, в 2017 году.

Ограничения

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

Однородные и неоднородные ограничения

Подзадача, полученная путем ограничения конечным языком ограничений, называется неравномерной задачей. Эти задачи в основном рассматриваются при выражении задачи об удовлетворении ограничениях в терминах задачи о гомоморфизмах, как описано ниже. Однородные задачи также были определены в контексте задач о гомоморфизмах; однородную задачу можно определить как объединение (возможно, бесконечного) множества неравномерных задач. Однородная задача, состоящая из бесконечного множества неравномерных задач, может быть вычислительно сложной, даже если все эти неравномерные задачи разрешимы.

Ограничения на основе деревьев

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

Условия эквивалентности

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

Удовлетворение ограничений и проблема гомоморфизма

Связь между задачей об удовлетворении ограничений и теорией баз данных установлена посредством соответствия между проблемой выполнимости ограничений и проблемой проверки существования гомоморфизма между двумя реляционными структурами. Реляционная структура представляет собой математическую модель реляционной базы данных: это набор значений и набор отношений над этими значениями. Формально, , где каждый является отношением над , то есть множеством кортежей значений . Реляционная структура отличается от задачи об удовлетворении ограничений тем, что ограничение – это отношение и кортеж переменных. Также различен способ их использования: для задачи об удовлетворении ограничений основная задача – найти допустимое назначение; для реляционной структуры – найти ответ на запрос. Однако задача об удовлетворении ограничений связана с задачей установления существования гомоморфизма между двумя реляционными структурами. Гомоморфизм – это функция, отображающая значения первой реляционной структуры в значения второй, которая при применении ко всем значениям отношения первой структуры преобразует его в подмножество соответствующего отношения второй структуры. Формально, является гомоморфизмом из в , если это функция из в , такая что, если то . Можно установить прямое соответствие между задачей об удовлетворении ограничений и задачей о гомоморфизме. Для заданной задачи об удовлетворении ограничений можно построить пару реляционных структур: первая кодирует переменные и сигнатуры ограничений, а вторая – области и отношения ограничений. Выполнимость задачи об удовлетворении ограничений соответствует нахождению значения для каждой переменной, такого что замена значения в сигнатуре приводит к кортежу в отношении ограничения. Это возможно тогда и только тогда, когда эта оценка является гомоморфизмом между двумя реляционными структурами. Обратное соответствие – противоположное: для двух заданных реляционных структур, значения первой кодируются переменными задачи об удовлетворении ограничений, а значения второй – областью той же задачи. Для каждого кортежа каждого отношения первой структуры существует ограничение, имеющее в качестве значений соответствующее отношение второй структуры. Таким образом, гомоморфизм соответствует отображению области каждого ограничения (каждого кортежа каждого отношения первой структуры) в кортеж в отношении ограничения (кортеж в соответствующем отношении второй структуры). Неоднородная задача об удовлетворении ограничений – это ограничение, при котором вторая структура в задаче о гомоморфизме фиксирована. Иными словами, каждая реляционная структура определяет неоднородную задачу, заключающуюся в определении, является ли реляционная структура гомоморфной ей. Аналогичное ограничение можно наложить и на первую структуру; для любой фиксированной первой структуры задача о гомоморфизме является разрешимой, поскольку тогда существует лишь полиномиальное число функций из первой структуры во вторую. Однородная задача об удовлетворении ограничений – это произвольное ограничение на множества структур для первой и второй реляционных структур в задаче о гомоморфизме.

Оценка и ограничение объединенных запросов

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

Присоединяйтесь к оценке

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

Теоремы дихотомии

Известно, что некоторые языки ограничений (или неравномерные задачи) соответствуют задачам, разрешимым за полиномиальное время, а другие, как известно, выражают NP-полные задачи. Однако возможно, что некоторые языки ограничений не попадают ни в одну из этих категорий. Теорема Ладнера утверждает, что если P не равно NP, то существуют задачи в NP, которые не являются ни полиномиальными, ни NP-трудными. Для задач с ограничениями с фиксированным языком ограничений и без структурных ограничений, таких промежуточных задач не существует, что было доказано Андреем Булатовым.

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

Достаточные условия для обрабатываемости

Некоторые результаты по вычислительной сложности доказывают, что некоторые ограничения разрешимы за полиномиальное время, но не доказывают, что все остальные возможные ограничения того же типа являются NP-трудными.

Даталог

Достаточное условие вычислительной реализуемости связано с выразимостью в Datalog. Булевый запрос Datalog присваивает значение истинности множеству литералов над заданным алфавитом, причем каждый литерал является выражением вида ; как результат, булевый запрос Datalog выражает множество множеств литералов, поскольку его можно считать семантически эквивалентным множеству всех множеств литералов, для которых он возвращает значение истинности. С другой стороны, неравномерную задачу можно рассматривать как способ выражения подобного множества. Для данной неравномерной задачи набор отношений, используемых в ограничениях, фиксирован; как следствие, им можно присвоить уникальные имена. Экземпляр этой неравномерной задачи может быть представлен как множество литералов вида: Среди этих экземпляров/множеств литералов некоторые выполнимы, а некоторые нет; выполнимость множества литералов зависит от отношений, которые определяются неравномерной задачей. И наоборот, неравномерная задача указывает, какие множества литералов представляют выполнимые экземпляры, а какие – невыполнимые. После присвоения имен отношениям, неравномерная задача выражает набор множеств литералов: соответствующих выполнимым (или невыполнимым) экземплярам. Достаточным условием вычислительной реализуемости является то, что неравномерная задача вычислительно реализуема, если множество ее невыполнимых экземпляров может быть выражено булевым запросом Datalog. Иными словами, если множество множеств литералов, представляющих невыполнимые экземпляры неравномерной задачи, также является множеством множеств литералов, удовлетворяющих булевому запросу Datalog, то неравномерная задача вычислительно реализуема.

Условия на деревьях

Проблемы удовлетворения ограничений, состоящие только из бинарных ограничений, можно представить в виде графов, где вершины соответствуют переменным, а ребра – наличию ограничения между двумя переменными. Этот граф называется графом Гайфмана или графом первичных ограничений (или просто первичным графом) для данной задачи. Если первичный граф задачи ацикличен, то проверка её разрешимости является вычислимой задачей. Это структурное ограничение, поскольку его можно проверить, рассматривая только области действия ограничений, не учитывая их взаимосвязи и область определения. Ациклический граф является лесом, но обычно предполагается связность; следовательно, чаще всего рассматривается условие, что первичные графы являются деревьями. Это свойство древовидных задач удовлетворения ограничений используется методами декомпозиции, которые преобразуют задачи в эквивалентные, содержащие только бинарные ограничения, расположенные в виде дерева. Переменные этих задач соответствуют множествам переменных исходной задачи; область определения такой переменной определяется путем рассмотрения части ограничений исходной задачи, область действия которых содержится в соответствующем исходном множестве переменных; ограничения в этих новых задачах представляют собой равенство переменных, входящих в два множества. Если граф одной из таких эквивалентных задач является деревом, то задача может быть решена эффективно. Однако построение одной из таких эквивалентных задач может быть неэффективным по двум причинам: необходимости определения совокупного эффекта группы ограничений на множество переменных и необходимости хранения всех кортежей значений, удовлетворяющих данной группе ограничений.

Необходимое условие для обрабатываемости

Доказано необходимое условие разрешимости языка ограничений, основанного на универсальном гаджете. Универсальный гаджет — это частный случай задачи об удовлетворимости ограничений, который изначально был определён для выражения новых отношений посредством проецирования.

Сквоширование функций и сокращение доменов

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

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

Необходимое условие для обрабатываемости

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