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

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

Описание для решения 3-SATПравить

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

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

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

Оценка ошибкиПравить

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