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

Алгори́тм Шёнинга (англ. Schöning's Algorithm) — вероятностный алгоритм для решения задачи выполнимости булевых формул в k-конъюнктивной нормальной форме, предложенный Уве Шёнингом в 1999 году.

Описание для решения 3-SAT

1. Дана булева формула в 3-конъюнктивной нормальной форме $F(x_{1},x_{2},\dots ,x_{n})$.
2. Повтори $\lceil 20\cdot {\sqrt {3\cdot \pi \cdot n}}\cdot ({\frac {4}{3}})^{n}\rceil$ раз:
   1. Случайно установи набор переменных $\alpha =(\alpha _{1},\alpha _{2},\dots ,\alpha _{n})\in \{0,1\}^{n}$.
   2. Если булева формула $F(\alpha )$ истинна, выведи $\alpha$ и заверши работу.
   3. Повтори $3\cdot n$ раз:
      1. Выбери дизъюнкцию $c_{i}$, которой не удовлетворяет $\alpha$.
      2. Выбери переменную $x_{j}$ из $c_{i}$.
      3. Установи $\alpha =(\alpha _{1},\alpha _{2},\dots ,{\overline {\alpha _{j}}},\dots ,\alpha _{n})$.
      4. Если булева формула $F(\alpha )$ истинна, выведи $\alpha$ и заверши работу.
3. Выведи "$F$ невыполнима".

Временная сложность

Алгоритм Шёнинга имеет временную сложность $O(m\cdot n^{3/2}\cdot (4/3)^{n})=O(m\cdot 1.334^{n})$, где $n$ - количество переменных, а $m$ - количество дизъюнкций, при условии, что проверка выполнимости булевой формулы производится за $O(3m)$. Если булева формула $F$ невыполнима, то алгоритм Шёнинга всегда возвращает верный результат.

Оценка ошибки

Если булева формула $F$ выполнима, то вероятность ошибки всегда будет меньше $5\cdot 10^{-5}$. Для доказательства обозначим за $\alpha ^{*}$ набор переменных, при котором $F(\alpha ^{*})$ истинна, а также $p_{l}$ - вероятность, что алгоритм найдет $\alpha ^{*}$ во вложенном цикле (эта стадия называется также локальным поиском). Таким образом $p_{l}$ является нижним пределом вероятности нахождения удовлетворяющего набора переменных с помощью локального поиска. Далее мы покажем, что $p_{l}\leqslant {\frac {1}{20\cdot {\sqrt {3\cdot \pi \cdot n}}}}\cdot \left({\frac {3}{4}}\right)^{n}$. Расстоянием между двумя наборами $\alpha$ и $\beta$ будем называть количество отличных в них бит. Определим класс $C(j)$ как множество наборов, отличающихся от $\alpha ^{*}$ на $j$ бит, т.е. $C(j)=\{\beta \in \{0,1\}^{n}\mid \operatorname {dist} (\alpha ^{*},\beta )=j\}$. Таким образом все наборы могут быть распределены на $n+1$ классов. Для $j\in \{0,1,\dots ,n\}$ справедливо $|C(j)|={\tbinom {n}{j}}$. Вероятность случайно выбрать элемент из $C(j)$ равна $p_{j}={\tbinom {n}{j}}\cdot 2^{-n}$. В локальном поиске рассматривается дизъюнкция $c_{i}$, которой не удовлетворяет сгенерированный набор переменных, и при случайном перевыборе набора вероятность найти удовлетворяющий равна $1/3$. Таким образом вероятность перейти из класса $C(j)$ к классу $C(j-1)$ равна минимум $1/3$. Вероятность же попасть из класса $C(j)$ в $C(j+1)$ равна максимум $2/3$. Пусть $q_{j,i}$ - вероятностью попасть из класса $C(j)$ за $j+2i$ шагов в класс $C(0)$, т.е. найти решение $\alpha ^{*}$. В таком случае $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}$, где ${\binom {j+2i}{i}}\cdot {\frac {j}{j+2i}}$ - количество возможных переходов в направлении $\alpha ^{*}$, а вероятность достичь $\alpha ^{*}$ из класса $C(j)$ равна $q_{j}=\sum _{i=0}^{j}q_{j,i}$. После подстановки формул друг в друга и приблизительного вычисления результата, получим вероятность не найти удовлетворяющий набор переменных во время локального поиска равную ${\tilde {p}}=1-{\frac {1}{2\cdot {\sqrt {3\pi n}}}}\cdot \left({\frac {3}{4}}\right)^{n}$, а после $t$ таких поисков вероятность станет уже равна $(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}$.