Задача ВЫПОЛНИМОСТЬ (SAT) и её принадлежность классу NP

Задача ВЫПОЛНИМОСТЬ (SAT) спрашивает, существует ли набор значений переменных, на котором заданная булева КНФ равна 1. В терминах языков SAT состоит из кодов выполнимых КНФ.1

SAT принадлежит классу \(NP\): недетерминированная машина может выбрать значения переменных, а затем за полиномиальное время проверить значение всех скобок. В модели пособия построена НМТ с полиномиальной оценкой времени \(O(L^3)\), где \(L\) — длина кода КНФ.1

Что важно запомнить
  • Вход SAT — код булевой формулы. В курсе рассматривается КНФ.
  • Ответ «да» означает существование хотя бы одного удовлетворяющего набора.
  • Такой набор служит свидетельством: его проверка выполняется за полиномиальное время.
  • Следовательно, \(SAT\in NP\). Теорема Кука добавляет NP-трудность и даёт NP-полноту SAT.1

Постановка задачи

Пусть дана КНФ \(K(x_1,\ldots,x_n)\). Требуется определить, существует ли \(\alpha\in\{0,1\}^n\), для которого \(K(\alpha)=1\). Если такой набор существует, формула называется выполнимой.

Недетерминированный алгоритм

НМТ последовательно выбирает для каждой переменной значение 0 или 1. После \(n\) выборов каждая ветвь дерева вычислений соответствует одному набору \(\alpha\). На этой ветви остаётся проверить, что после подстановки значений каждая скобка КНФ истинна. Если существует удовлетворяющий набор, существует и принимающая ветвь.1

В пособии процедура формализуется через код КНФ. Недетерминированный выбор констант совмещается с детерминированной подстановкой и проверкой. Полученная оценка времени каждой ветви — \(O(L^3)\), то есть полином от длины входа. Поэтому ВЫП \(\in NP\).1

Связь с NP-полнотой

Принадлежность \(NP\) — только одна половина результата. Теорема Кука показывает, что к SAT полиномиально сводится любой язык из \(NP\). Следовательно, SAT является NP-полной задачей.

Пример простыми словами

Для КНФ \((x_1\vee x_2)\wedge(\neg x_1\vee x_3)\) набор \((x_1,x_2,x_3)=(0,1,0)\) удовлетворяет обеим скобкам. Чтобы проверить это свидетельство, достаточно подставить три значения и вычислить формулу. Искать другие наборы уже не нужно.

Частые ошибки
  • Путать выполнимость с тождественной истинностью. SAT требует хотя бы одного удовлетворяющего набора.
  • Считать доказательством SAT \(\in NP\) полный детерминированный перебор \(2^n\) наборов. Нужна полиномиальная проверка одной недетерминированно выбранной ветви.
  • Из SAT \(\in NP\) сразу заключать NP-полноту. Для неё дополнительно нужна NP-трудность из теоремы Кука—Левина.

Другие вопросы

Источники

  1. 1 Сапоженко А. А. Некоторые вопросы сложности алгоритмов М.: МГУ, факультет ВМК, 2001 г. §5, теорема 5.1 и следствие 5.1