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

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

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

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