Алгоритмы локального поиска для k-КНФ: различия между версиями

[[Задача о выполнимости]] КНФ заключается в следующем. Для данной формулы F с n переменными в конъюнктивной нормальной форме необходимо определить, существует ли присваивание, обеспечивающее выполнимость формулы F. Если все дизъюнкты F содержат не более литералов, то F называется формулой в k-КНФ, а задача носит название задачи выполнимости k-КНФ (k-SAT) и является одной из самых фундаментальных NP-полных задач. Тривиальный алгоритм выполняет поиск среди <math>2^n \;</math> присваиваний значений 0 и 1 для n переменных. Однако с момента выхода работы [6] были разработаны алгоритмы, скорость выполнения которых значительно превышает <math>O(2^n) \;</math> тривиального подхода. В качестве простого примера рассмотрим следующий прямолинейный алгоритм для задачи 3-КНФ, обеспечивающий верхнюю границу <math>1,913^n \;</math>. Выберем произвольный дизъюнкт из F, скажем, <math>(x_1 \lor \bar{x_2} \lor x_3)</math>. Затем сгенерируем семь новых формул путем подстановки в <math>x_1, x_2, x_3 \;</math> всех возможных значений, кроме <math>(x_1, x_2, x_3) = (0, 1, 0) \;</math>, при котором, очевидно, формула F не выполняется. Теперь можно проверить выполнимость этих семи формул и сделать вывод, что F является выполнимой, в том случае, если хотя бы одна из этих формул выполнима. (Обозначим за T(n) временную сложность этого алгоритма. После этого, учитывая рекуррентность <math>T(n) \le 7 \times T(n - 3) \;</math>, можно получить вышеупомянутую границу).

В длинном списке алгоритмов для k-SAT алгоритм Шонинга [11] стал революционным прорывом. Это стандартный подход с использованием локального поиска, и сам по себе алгоритм не был новинкой (см., например, [7]). Предположим, что y – текущее присваивание (его начальное значение равномерно выбирается случайным образом). Если присваивание y обеспечивает выполнимость формулы, алгоритм выдает ответ «Да» и завершает работу. В противном случае имеется по меньшей мере один дизъюнкт, литералы которого на присваивании y имеют значение «ложь». Выберем такой произвольный дизъюнкт и выберем случайным образом один из трех литералов. Затем изменим значение этой переменной на противоположное («истина» на «ложь» и наоборот), заменим y этим новым присваиванием и повторим ту же процедуру.

Шонинг выполнил очень изящный анализ этого алгоритма. Обозначим за d(a, b) [[Hamming distance|расстояние Хэмминга]] между двумя бинарными векторами (присваиваниями) a и b. Для простоты будем считать, что формула F оказывается выполнимой только на одном присваивании y* и что текущее присваивание y находится от y* на расстоянии Хэмминга d. Предположим также, что ложный в настоящий момент дизъюнкт C включает три переменные – xi, xj и xk. Тогда y и y* должны различаться по меньшей мере в одной из этих переменных. Это значит, что если поменять значение xi, xj или xk на противоположное, то новое присваивание будет ближе к y* согласно расстоянию Хэмминга с вероятностью не ниже 1/3 – и дальше от него с вероятностью не более 2/3. Это рассуждение можно распространить на случай, когда формула F оказывается выполнимой на нескольких присваиваниях. Отсюда следует важная лемма.

Лемма 1. Пусть F – выполнимая формула, а y* – присваивание, на котором она оказывается выполнимой. Для любого присваивания y вероятность того, что присваивание, на котором формула оказывается выполнимой (и которое может быть отличным от y*), найдено алгоритмом RandomWalk(F, y), составляет не менее (1/(k - 1))d(y, y*)/p(n), где p(n) – полином от n.

Теорема 2. Для любой выполнимой формулы F с n переменными вероятность успеха алгоритма RandomWalk(F, y) составляет не менее (k/2(k - 1))n /p(n) для некоторого полиномиального p. Таким образом, положив I = (2(k - 1)/k)n _ p(n), алгоритм SCH с высокой вероятностью находит присваивание, на котором формула выполняется. При k = 3 значение I составляет O(1,334n).

Результат Шонинга был улучшен в серии статей [1, 3, 9], основанных на идее из [3]. В частности, сочетание алгоритма RandomWalk с алгоритмом 2-КНФ с полиномиальным временем выполнения позволило выбирать более подходящие начальные присваивания. Дерандомизация алгоритма SCH описана в работе [2]. В работе [4] была предложена нетривиальная комбинация SCH с еще одним известным представителем семейства алгоритмов с возвратом [8], что позволило ускорить выполнение алгоритма до показателя O(1,324n). Самый быстрый известный на данный момент алгоритм представлен в [10], он основан на том же подходе, что и алгоритм из работы [4], и выполняется за время O(1,32216n).