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

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

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

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

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