Сложность удовлетворения ограничений - Complexity of constraint satisfaction

Эта статья включает список литературы, связанное чтение или внешние ссылки, но его источники остаются неясными, потому что в нем отсутствует встроенные цитаты. Пожалуйста, помогите улучшить эта статья введение более точные цитаты. (Август 2011 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

Обзор

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

Управляемость может быть достигнута путем рассмотрения конкретных классов проблем удовлетворения ограничений. Например, если домен двоичный и все ограничения двоичный, установление выполнимости является задачей полиномиального времени, потому что эта проблема эквивалентна 2-СБ, что послушно. Исследования показали ряд поддающихся лечению случаев. Некоторые из этих классов основаны на ограничении разрешенных доменов или отношений, некоторые - на ограничении способа наложения ограничений на переменные, а некоторые - на обоих типах ограничений.

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

Рассматриваемая исследовательская проблема заключается в существовании дихотомий между наборами ограничений. Это вопрос о том, содержит ли набор ограничений только ограничения полиномиального времени и NP-полные ограничения. Этот вопрос решен для некоторых наборов ограничений, но все еще открыт для набора всех ограничений, основанных на фиксированном домене и наборе отношений, начиная с 2007 г.^{[Обновить]}. Некоторые авторы считают это наиболее важным открытым вопросом о сложности выполнения ограничений.

Ограничения

Подходящие подслучаи общих проблем удовлетворения ограничений могут быть получены путем наложения подходящих ограничений на проблемы. Были рассмотрены разного рода ограничения.

Структурные и реляционные ограничения

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

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

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

Язык ограничений является управляемым, если существует полиномиальный алгоритм, решающий все проблемы на основе языка, то есть с использованием домена и отношений, указанных в домене. Примером управляемого языка ограничений является язык двоичных доменов и двоичных ограничений. Формально это ограничение соответствует разрешению только доменов размера 2 и только ограничений, отношение которых является бинарным. Хотя второй факт подразумевает, что области действия ограничений являются двоичными, это не структурное ограничение, поскольку оно не запрещает накладывать какие-либо ограничения на произвольную пару переменных. Между прочим, проблема становится NP-полной, если снимается любое ограничение: двоичные ограничения и троичные домены могут выражать раскраска графика проблема, в то время как троичные ограничения и бинарные домены могут выражать 3-СБ; обе эти две проблемы NP-полны.

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

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

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

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

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

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

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

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

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

Выполнение ограничений и проблема гомоморфизма

Связь между удовлетворением ограничений и теорией баз данных была предоставлена ​​в форме соответствия между проблемой выполнимости ограничений и проблемой проверки, существует ли гомоморфизм между двумя реляционными структурами. Реляционная структура - это математическое представление базы данных: это набор значений и набор отношений между этими значениями. Формально, ${displaystyle A = (V, R_ {1} ^ {A}, ldots, R_ {n} ^ {A})}$, где каждый ${displaystyle R_ {i} ^ {A}}$ это отношение над ${displaystyle V}$, то есть набор кортежей значений ${displaystyle V}$.

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

Однако проблема удовлетворения ограничений связана с проблемой установления существования гомоморфизма между двумя реляционными структурами. Гомоморфизм - это функция от значений первого отношения к значениям второго, которая при применении ко всем значениям отношения первой структуры превращает ее в подмножество соответствующего отношения второй структуры. Формально, ${displaystyle h}$ является гомоморфизмом из ${displaystyle A = (V, R_ {1} ^ {A}, ldots, R_ {n} ^ {A})}$ к ${displaystyle B = (D, R_ {1} ^ {B}, ldots, R_ {n} ^ {B})}$ если это функция из ${displaystyle V}$ к ${displaystyle D}$ так что, если ${displaystyle (x_ {1}, ldots, x_ {k}) в R_ {i} ^ {A}}$ тогда ${displaystyle (h (x_ {1}), ldots, h (x_ {k})) в R_ {i} ^ {B}}$.

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

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

Неравномерная проблема удовлетворения ограничений - это ограничение, в котором зафиксирована вторая структура проблемы гомоморфизма. Другими словами, каждая реляционная структура определяет неоднородную проблему, а именно: определить, является ли структура отношения гомоморфной ей. Аналогичное ограничение может быть наложено на первую структуру; для любой фиксированной первой структуры проблема гомоморфизма разрешима. Задача выполнения равномерного ограничения - это произвольное ограничение на наборы структур для первой и второй структур проблемы гомоморфизма.

Оценка и содержание конъюнктивного запроса

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

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

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

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

Известно, что некоторые языки ограничений (или неоднородные задачи) соответствуют задачам, решаемым в полиномиальное время, а некоторые другие, как известно, выражают НП-полный проблемы. Однако возможно, что некоторые языки ограничений не являются ни тем, ни другим. Это известно Теорема Ладнера что если P не равно NP, то в NP существуют задачи, которые не являются ни полиномиальными, ни NP-трудными. По состоянию на 2007 год^{[Обновить]}, неизвестно, могут ли такие проблемы быть выражены как проблемы удовлетворения ограничений с помощью языка фиксированных ограничений. Если бы языки Ladner не могли быть выражены таким образом, набор всех языков ограничений можно было бы точно разделить на те, которые определяют полиномиальное время, и те, которые определяют NP-полные проблемы; то есть этот набор будет показывать дихотомия.

Частичные результаты известны для некоторых наборов языков ограничений. Самый известный такой результат - Теорема дихотомии Шефера, что доказывает существование дихотомии во множестве языков ограничений в бинарной области. Точнее, он доказывает, что ограничение отношения в бинарной области является управляемым, если все его отношения принадлежат одному из шести классов, и NP-полным в противном случае. Булатов доказал теорему о дихотомии для областей из трех элементов.

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

Достаточные условия для послушности

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

Лог данных

Достаточное условие управляемости связано с выражаемостью в Лог данных. Логический запрос к журналу данных дает значение истины к набору литералов по данному алфавиту, каждый из которых является выражением формы ${displaystyle L (a_ {1}, ldots, a_ {n})}$; в результате логический запрос к журналу данных выражает набор наборов литералов, поскольку его можно считать семантически эквивалентным набору всех наборов литералов, которые он оценивает как истинные.

С другой стороны, неоднородную задачу можно рассматривать как способ выражения подобного множества. Для данной неоднородной задачи фиксируется набор отношений, которые могут использоваться в ограничениях; в результате можно давать уникальные имена ${displaystyle R_ {1}, ldots, R_ {n}}$ им. Пример этой неоднородной задачи может быть записан в виде набора литералов вида ${displaystyle R_ {i} (x_ {1}, ldots, x_ {n})}$. Среди этих экземпляров / наборов литералов некоторые являются выполнимыми, а некоторые нет; выполнимость набора литералов зависит от отношений, которые задаются неравномерной задачей. С другой стороны, неоднородная проблема сообщает, какие наборы литералов представляют выполнимые экземпляры, а какие - неудовлетворительные. После того, как отношения названы, неоднородная проблема выражает набор наборов литералов: тех, которые связаны с выполнимыми (или неудовлетворительными) экземплярами.

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

Локальная согласованность

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

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

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

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

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

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

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

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

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

Необходимое условие послушности

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

Универсальный гаджет

Отношение, которое отсутствует в языке ограничений, может быть «смоделировано» ограничениями с использованием отношений на языке. В частности, новое отношение можно создать, поместив набор ограничений и используя только некоторые из их переменных. Если все другие ограничения используют только эти переменные, этот набор ограничений вынуждает эти переменные принимать только определенные значения, практически моделируя новое отношение.

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

Универсальный гаджет основан на наблюдении, что каждое отношение, содержащее ${displaystyle k}$-кортежи могут быть определены путем проектирования отношения, которое содержит все возможные столбцы ${displaystyle k}$ элементы из домена. В качестве примера в следующих таблицах показана такая проекция:

а б в г д е ж з б г --------------- --- 1 1 1 1 0 0 0 0 -> 1 11 1 0 0 1 1 0 0 1 01 0 1 0 1 0 1 0 0 0

Если таблица слева представляет собой набор решений задачи удовлетворения ограничений, ее переменные ${displaystyle b}$ и ${displaystyle d}$ ограничены значениями таблицы справа. В результате проблема удовлетворения ограничений может использоваться для установки ограничения, отношение которого является таблицей справа, что может не быть на языке ограничений.

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

Например, если язык содержит бинарное отношение, представляющее булеву дизъюнкцию (отношение, содержащее все кортежи из двух элементов, которые содержат как минимум 1), это отношение помещается как ограничение на ${displaystyle a}$ и ${displaystyle b}$, потому что их значения в таблице выше ${displaystyle (1,1)}$, ${displaystyle (1,1)}$ снова и ${displaystyle (1,0)}$. Поскольку все эти значения удовлетворяют ограничению, устанавливается ограничение. С другой стороны, ограничение на это отношение не накладывается на ${displaystyle b}$ и ${displaystyle d}$, так как ограничение таблицы выше на эти две переменные содержит ${displaystyle (0,0)}$ в качестве третьей строки, и эта оценка нарушает это ограничение.

Универсальный гаджет порядка ${displaystyle k}$ - это задача удовлетворения ограничений, содержащая все ограничения, которые могут быть наложены, чтобы получить приведенную выше таблицу. Решения универсального гаджета включают строки этой таблицы, но могут содержать и другие строки. Если решения - это в точности строки таблицы, каждое отношение может быть выражено путем проецирования на подмножество переменных. Однако, даже если решения включают другие строки, некоторые отношения все же могут быть выражены. Свойство универсального гаджета состоит в том, что он может выражать посредством проекции каждое отношение, которое может быть выражено проекцией из произвольной задачи удовлетворения ограничений, основанной на том же языке. Точнее универсальный гаджет на заказ ${displaystyle k}$ выражает все отношения ${displaystyle k}$ строки, которые могут быть выражены на языке ограничений.

Если задано конкретное отношение, его выразимость на языке можно проверить, рассмотрев произвольный список переменных, столбцы которых в приведенной выше таблице («идеальные» решения универсального гаджета) образуют это отношение. Отношение может быть выражено на языке тогда и только тогда, когда решения универсального устройства совпадают с отношением при проецировании по такому списку переменных. Другими словами, можно проверить выразимость, выбрав переменные, «как если бы» решения универсального гаджета были такими, как в таблице, а затем проверить, действительно ли ограничение «реальных» решений совпадает с отношением. В приведенном выше примере выразимость отношения в таблице справа можно проверить, посмотрев, могут ли решения универсального гаджета, ограниченные переменными ${displaystyle b}$ и ${displaystyle d}$, это именно строки этой таблицы.

Решения как функции в универсальном гаджете

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

abcdefg h --------------- 1 1 1 1 0 0 0 01 1 0 0 1 1 0 0 (решения, существующие по определению) 1 0 1 0 1 0 1 0 --- ------------.... 1 0 0 1 1 1 0 0 (возможны другие решения) ....

Этот стол состоит из двух частей. Первая часть содержит решения, существующие по определению этой проблемы; вторая часть (которая может быть пустой) содержит все остальные решения. Поскольку столбцы таблицы по определению связаны с возможными ${displaystyle k}$-наборы значений области, каждое решение можно рассматривать как функцию от ${displaystyle k}$-набор элементов в один элемент.

Функция, соответствующая решению, может быть вычислена из первой части приведенной выше таблицы и решения. Например, для последнего решения, отмеченного в таблице, эту функцию можно определить для аргументов ${displaystyle 1,0,1}$ следующим образом: во-первых, эти три значения являются первой частью строки «c» в таблице; значение функции - это значение решения в том же столбце, то есть 0.

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

Функции сжатия и сокращенные домены

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

Формально с учетом перегородки ${displaystyle D_ {1}, ldots, D_ {n}}$ домена ${displaystyle D}$ содержащий хотя бы набор размера больше единицы, функция сжатия - это функция ${displaystyle s: Dightarrow D}$ такой, что ${displaystyle s (x) = s (y)}$ для каждого ${displaystyle x, y}$ в том же разделе и для каждого кортежа ${displaystyle langle x_ {1}, ldots, x_ {n} угол в R}$, он держит ${displaystyle langle s (x_ {1}), ldots, s (x_ {n}) угол в R}$.

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

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

Необходимое условие послушности

Эта секция нуждается в расширении. Вы можете помочь добавляя к этому. (Февраль 2010 г.)

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

использованная литература

• Дехтер, Рина (2003). Обработка ограничений. Морган Кауфманн. ISBN  1-55860-890-7
• Варди, Моше Й. (2000). "Удовлетворение ограничений и теория базы данных: учебное пособие". PODS 2000. С. 76–85.
• Булатов, Андрей А. (2006). «Теорема дихотомии для задач удовлетворения ограничений на трехэлементном множестве». Журнал ACM. 53 (1): 66–120. Дои:10.1145/1120582.1120584. S2CID  18220438.