Русская Википедия:Алгоритм Шёнинга
Алгори́тм Шёнинга (англ. Schöning's Algorithm) — вероятностный алгоритм для решения задачи выполнимости булевых формул в k-конъюнктивной нормальной форме, предложенный Уве Шёнингом в 1999 году[1].
Описание для решения 3-SAT
- Дана булева формула в 3-конъюнктивной нормальной форме <math>F(x_1, x_2, \dots, x_n)</math>.
- Повтори <math>\lceil 20 \cdot \sqrt{3 \cdot \pi \cdot n} \cdot (\frac{4}{3})^n \rceil</math> раз:
- Случайно установи набор переменных <math>\alpha = (\alpha_1, \alpha_2, \dots, \alpha_n) \in \{0, 1\}^n</math>.
- Если булева формула <math>F(\alpha)</math> истинна, выведи <math>\alpha</math> и заверши работу.
- Повтори <math>3 \cdot n</math> раз:
- Выбери дизъюнкцию <math>c_i</math>, которой не удовлетворяет <math>\alpha</math>.
- Выбери переменную <math>x_j</math> из <math>c_i</math>.
- Установи <math>\alpha = (\alpha_1, \alpha_2, \dots, \overline{\alpha_j}, \dots, \alpha_n)</math>.
- Если булева формула <math>F(\alpha)</math> истинна, выведи <math>\alpha</math> и заверши работу.
- Выведи "<math>F</math> невыполнима".
Временная сложность
Алгоритм Шёнинга имеет временную сложность <math>O(m \cdot n^{3/2} \cdot (4/3)^n) = O(m \cdot 1.334^n) </math>, где <math>n</math> - количество переменных, а <math>m</math> - количество дизъюнкций, при условии, что проверка выполнимости булевой формулы производится за <math>O(3m)</math>. Если булева формула <math>F</math> невыполнима, то алгоритм Шёнинга всегда возвращает верный результат.
Оценка ошибки
Если булева формула <math>F</math> выполнима, то вероятность ошибки всегда будет меньше <math>5 \cdot 10^{-5}</math>. Для доказательства обозначим за <math>\alpha^*</math> набор переменных, при котором <math>F(\alpha^*)</math> истинна, а также <math>p_l</math> - вероятность, что алгоритм найдет <math>\alpha^*</math> во вложенном цикле (эта стадия называется также локальным поиском). Таким образом <math>p_l</math> является нижним пределом вероятности нахождения удовлетворяющего набора переменных с помощью локального поиска. Далее мы покажем, что <math>p_l \leqslant \frac{1}{20 \cdot \sqrt{3 \cdot \pi \cdot n}} \cdot \left ( \frac{3}{4} \right )^n</math>. Расстоянием между двумя наборами <math>\alpha</math> и <math>\beta</math> будем называть количество отличных в них бит. Определим класс <math>C(j)</math> как множество наборов, отличающихся от <math>\alpha^*</math> на <math>j</math> бит, т.е. <math>C(j) = \{ \beta \in \{0, 1\}^n \mid \operatorname{dist}(\alpha^*, \beta) = j \}</math>. Таким образом все наборы могут быть распределены на <math>n+1</math> классов. Для <math>j \in \{0, 1, \dots, n\}</math> справедливо <math>|C(j)| = \tbinom{n}{j}</math>. Вероятность случайно выбрать элемент из <math>C(j)</math> равна <math>p_j = \tbinom{n}{j} \cdot 2^{-n}</math>. В локальном поиске рассматривается дизъюнкция <math>c_i</math>, которой не удовлетворяет сгенерированный набор переменных, и при случайном перевыборе набора вероятность найти удовлетворяющий равна <math>1/3</math>. Таким образом вероятность перейти из класса <math>C(j)</math> к классу <math>C(j-1)</math> равна минимум <math>1/3</math>. Вероятность же попасть из класса <math>C(j)</math> в <math>C(j+1)</math> равна максимум <math>2/3</math>. Пусть <math>q_{j, i}</math> - вероятностью попасть из класса <math>C(j)</math> за <math>j + 2i</math> шагов в класс <math>C(0)</math>, т.е. найти решение <math>\alpha^*</math>. В таком случае <math>q_{i, j} = \binom{j+2i}{i} \cdot \frac{j}{j + 2i} \cdot \left ( \frac{1}{3} \right )^{j+1} \cdot \left ( \frac{2}{3} \right )^{i}</math>, где <math>\binom{j+2i}{i} \cdot \frac{j}{j + 2i}</math> - количество возможных переходов в направлении <math>\alpha^*</math>, а вероятность достичь <math>\alpha^*</math> из класса <math>C(j)</math> равна <math>q_j = \sum_{i=0}^j q_{j, i}</math>. После подстановки формул друг в друга и приблизительного вычисления результата, получим вероятность не найти удовлетворяющий набор переменных во время локального поиска равную <math>\tilde{p} = 1 - \frac{1}{2 \cdot \sqrt{3 \pi n}} \cdot \left ( \frac{3}{4} \right )^n</math>, а после <math>t</math> таких поисков вероятность станет уже равна <math>(1 - \tilde{p})^{\lceil 20 \cdot \sqrt{3 \cdot \pi \cdot n} \cdot (\frac{4}{3})^n \rceil} \leqslant e^{-10} \leqslant 5 \cdot 10^{-5}</math>.
Примечания
