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

Алгори́тм Шёнинга (англ. 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⩽\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 \mathrm{dist}({\alpha }^{*},\beta )=j\}$. Таким образом все наборы могут быть распределены на $n+1$ классов. Для $j\in \{0,1,\dots ,n\}$ справедливо $|C(j)|=(\genfrac{}{}{0ex}{}{n}{j})$. Вероятность случайно выбрать элемент из $C(j)$ равна $p_j=(\genfrac{}{}{0ex}{}{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}=(\genfrac{}{}{0ex}{}{j+2i}{i})\cdot \frac{j}{j+2i}\cdot {\left(\frac{1}{3}\right)}^{j+1}\cdot {\left(\frac{2}{3}\right)}^i$, где $(\genfrac{}{}{0ex}{}{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 }⩽e^{-10}⩽5\cdot 10^{-5}$.