Алгоритм Шёнинга

Прочитал недавно статью 1999го года об алгоритме для проблемы поиска набора переменных, при котором данная 3-КНФ (а также вообще k-КНФ) истинна: homepages.cwi.nl/~rdewolf/schoning99.pdf
Возникли такие мысли: 1) действительно ли наиболее целесообразно делать именно 3n шагов? 2) Не сделает ли алгоритм более эффективным генерация не рандомных значений переменных, независимых от предыдущих попыток, а какой-либо более сложный подход? Например, выбор нескольких наборов значений переменных так, чтобы искомый набор (решение) был гарантированно близок по крайней мере к одному из них на расстояние Хэмминга, не превосходящее n/t, где t - некая специально подобранная константа.
Сейчас получены несколько лучшие асимптотики, чем в описанном алгоритме, но его относительная простота (и простота доказательства его асимптотики) делает поиск усовершенствований не таким сложным.

Прочитал. Осмысливаю.

Не вникая пока в выкладки (с. 411 — мне не очень понятно, какие там используются эквивалентности и пр.), могу сказать, что не понимаю, как это вообще работает. Матожидание приращения расстояния Хэмминга при одном «флипе» оценивается через при . Если мы всё равно уходим от искомого решения, зачем вообще эти 3n итераций, и почему сразу не выбирать новую точку? Какой-то фокус.

(08-11-2012 21:01)Quasus писал(а):  Не вникая пока в выкладки (с. 411 — мне не очень понятно, какие там используются эквивалентности и пр.), могу сказать, что не понимаю, как это вообще работает. Матожидание приращения расстояния Хэмминга при одном «флипе» оценивается через при . Если мы всё равно уходим от искомого решения, зачем вообще эти 3n итераций, и почему сразу не выбирать новую точку? Какой-то фокус.

Там получается, что вероятность прийти к решению (если конечно оно существует) за те 3n итераций не менее чем , где j - расстояние Хэмминга от сгенерённого набора переменных до ответа, и этого оказывается достаточно, чтобы побить "наивный" алгоритм по производительности.

Идея подобного рода алгоритмов основывается на том, что если есть способ получить ответ за одно испытание с вероятностью не менее 1/k, то если провести k таких независимых испытаний, то вероятность, что ответ не будет получен, будет всего лишь примерно 1/e. Если повторить их C*k раз, где C - соотв. константа, можно понизить вероятность неудачи ниже нужного уровня.

Видимо, в первую очередь я не понимаю, какой «функционал стоимости» оптимизируется.

Оптимизуется зависимость времени поиска решения (в данном случае - времени, за которое алгоритм найдёт решение с вероятностью, близкой к единице) от числа переменных в КНФ при максимальном размере дизъюнкций, обозначенном через k. Понятно, что на поиск невыполненной дизъюнкции тоже будет каждый раз уходить время, но в данном случае им можно пренебречь, поскольку сложность всё равно будет экспоненциальная. Цель построения алгоритмов для задачи о выполнимости k-КНФ (k >= 3) - максимально приблизить к 1 основание степени в асимпотической оценке (возможно, существуют и субэкспоненциальные алгоритмы, или даже полиномиальные, но пока таких не удалось найти). Для задачи о выполнимости 2-КНФ существует простой полиномиальный алгоритм - O(N²).

Задача о выполнимости 3-КНФ - NP-полная задача, поэтому весьма вероятно, что полиномиального алгоритма для неё не существует.

То есть начальное приближение — «дорого», нахождение невыполненной дизъюнкции — «дёшево» (a fortiori проверка тоже дешёвая). А «флипанье» значит дорого?

(10-11-2012 01:38)Quasus писал(а):  То есть начальное приближение — «дорого», нахождение невыполненной дизъюнкции — «дёшево» (a fortiori проверка тоже дешёвая)

Сам блок из 3n итераций дёшев, так как работает за полиномиальное от n время. Но его нужно повторять экспоненциальное число раз, чтобы достичь близкой к 1 вероятности нахождения ответа. От полиномиального множителя можно избавиться, промажорировав его через , где эпсилон - положительное число, сколь угодно близкое к нулю. Сложность для 3-КНФ будет тогда выглядеть как .