Задачи SAT и 3-SAT

Допустим, имеется множество X из n булевых переменных x1, ..., xn; каждая пере- менная может принимать значение 0 или 1 (эквиваленты fаl sе и true). Литералом по X называется одна из переменных х.
или ее отрицание Наконец, условием на-

зывается обычная дизъюнкция литералов

/, v/г V”‘V/, .

(Еще раз: все I, £ |х, ,.r:}). Мы говорим, что условие имеет длину i, если оно содержит I литералов.

А теперь дадим формальное определение присваиванию значений, удовлет- воряющих набору условий. Логическим присваиванием для X называется присва- ивание значения 0 или 1 каждому х.; другими словами, это функция v :Х—> {0,1}. Присваивание v неявно задает jг, значение истинности, противоположное х. При- сваивание выполняет условие C, если после него C дает результат 1 по условиям булевой логики; это эквивалентно требованию о том, чтобы по крайней мере один из литералов в C имел значение 1. Присваивание выполняет совокупность условий C1, ..., Ck, если в результате его все C дают результат 1; иначе говоря, если в резуль- тате его конъюнкция

Cj Λ C2 Λ ... Λ Ck

дает результат 1. В этом случае v называется выполняющим присваиванием в отно- шении С',,а набор условий С,,...,С) называется выполнимым.

Рассмотрим простой пример. Допустим, имеются три условия:

⅛ V⅜V4( ⅛ V*~>.

Логическое присваивание v, которое задает всем трем переменным значение 1, не является выполняющим, потому что с ним не выполняется второе из перечис- ленных условий; с другой стороны, присваивание ν', которое задает всем перемен- ным значение 0, является выполняющим.

Теперь можно привести формулировку задачи выполнимости, также обознача- емой SAT:

Для заданного множества условий C1, ..., Ck по множеству переменных X = {x1, ..., хп} существует ли выполняющее логическое присваивание?

Существует частный случай SAT, обладающий эквивалентной сложностью, но при этом более понятный; в нем все условия содержат ровно три литерала (соот- ветствующих разным переменным). Назовем эту задачу задачей 3-выполнимости, или 3-SAT:

Для заданного множества условий C1, ..., Ck , каждое из которых имеет длину 3, по множеству переменных X = {x1, ..., хп}, существует ли выполняющее логиче- ское присваивание?

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

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Задачи SAT и 3-SAT:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  11. Основные задачи
  12. Правило решаемой психологической задачи.
  13. Задачи и упражнения
  14. Терапевтическая задача
  15. 3. Задачи и функции социологии
  16. Основные задачи МПП.
  17. Задачи и упражнения
  18. Задачи