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

Шонинг выполнил очень изящный анализ этого алгоритма. Обозначим за 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).