Сложность удовлетворения ограничений

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

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

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

Обзор [ править ]

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

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

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

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

Ограничения [ править ]

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

Структурные и реляционные ограничения [ править ]

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

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

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

Язык ограничений является управляемым, если существует полиномиальный алгоритм, решающий все проблемы на основе языка, то есть с использованием домена и отношений, указанных в домене. Примером понятного языка ограничений является язык двоичных доменов и двоичных ограничений. Формально это ограничение соответствует разрешению только доменов размера 2 и только ограничений, отношение которых является бинарным. Хотя второй факт подразумевает, что области действия ограничений являются двоичными, это не структурное ограничение, поскольку оно не запрещает наложение каких-либо ограничений на произвольную пару переменных. Между прочим, проблема становится NP полной, если снимается любое ограничение: двоичные ограничения и тернарные области могут выражать раскраску графа.проблема, в то время как троичные ограничения и бинарные домены могут выражать 3-SAT ; обе эти две проблемы являются 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})\in R_{i}^{A}}$${\displaystyle (h(x_{1}),\ldots ,h(x_{k}))\in R_{i}^{B}}$

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

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

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

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

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

Присоединяйтесь к оценке [ править ]

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

Теоремы дихотомии [ править ]

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

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

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

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

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

Журнал данных [ править ]

Достаточное условие управляемости связано с выразительностью в Datalog . Логический запрос к журналу данных дает значение истинности набору литералов по заданному алфавиту, каждый из которых является выражением формы ; в результате логический запрос к журналу данных выражает набор наборов литералов, так как его можно считать семантически эквивалентным набору всех наборов литералов, которые он оценивает как истинные.${\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}$

abcdefghbd--------------- ---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}$, являются в точности строками этой таблицы.

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

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

abcdefgh---------------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}$

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

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

Функции сжатия и сокращенные домены [ править ]

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

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

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

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

Необходимое условие послушности [ править ]

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

Ссылки [ править ]

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