Blog
吉田です。今日は3SATの話をしましょう。
3SATは恐らくNP完全問題の中で一番有名な問題です。入力インスタンス\(I\)はBoolean変数の集合\(V\)と節の集合\(\mathcal{C}\)からなるCNF論理式で、各節はリテラルの個数が丁度三つからなっています。目的は全ての節を充足するような変数への割り当て\(\alpha : V \to \{\mathrm{true}, \mathrm{false}\}\)を見つけることです。ともかく例を見てみましょう。
\(V = \{x,y,z,w\}\)
\(\mathcal{C} = (x \vee y \vee z) \wedge (\neg x \vee y \vee z) \wedge (y \vee \neg z \vee w)\).
上の例だと、例えば\(\alpha(x) = \mathrm{true}, \alpha(y) = \mathrm{true}, \alpha(z) = \mathrm{false}, \alpha(w) = \mathrm{false}\)とすれば全ての節を充足することが出来ます。
3SATはNP完全なので全てのNPに属す問題は3SATとして解けるのですが、そうでなくても多くの問題から”自然”に3SATが導出されます。なので3SATを解くアルゴリズムを考えましょう。一番自明なアルゴリズムは次のようになると思います。変数の数を\(n\)、節の数を\(m\)としましょう。
(1) \(2^n\)通りの全ての割り当て\(\alpha\)に対して以下を行う。
(1.1) \(\alpha\)が全ての節を満たしていれば、\(\alpha\)を出力。
(2) 充足不能と出力。
明らかに計算時間は\(O(m2^n)\)、つまり(入力サイズに対して)指数時間になります。
それではこれを高速化することは出来るのでしょうか？残念なことにNP完全な問題は多項式時間では解けないと信じられています。なので大幅に計算時間を縮めることは出来そうにありません。なので実用的には枝刈りを用いて解かれています。ただ枝刈りという解析出来ないものは理論屋さんは好きではないので、理論屋さんは主に次の三つの方法で3SATにアプローチしているようです。
・厳密アルゴリズム: \(c^n\)時間で解くアルゴリズムで、出来るだけ\(c\)が小さいものを作る。
・近似アルゴリズム: 出来るだけ多くの節を充足する多項式時間アルゴリズムを作る。
・ランダム3SAT: 入力がランダムに分布しているとして、高い確率で充足解を出力する多項式時間アルゴリズムを作る。
今回は厳密アルゴリズムに注目しましょう。3SATに対する厳密アルゴリズムとしては、既に乱択アルゴリズムの代表例となっている、Schoeningのアルゴリズム[1]が知られています。Schoeningのアルゴリズムを3SATを\(O((\frac{4}{3})^n)=O(1.334^n)\)解くモンテカルロアルゴリズムです。正確には充足可能であれば高い確率(例えば\(\frac{99}{100}\))で充足解を出力し、充足不能であれば必ず充足不能と出力します。
\(O(2^n)\)が\(O(1.334^n)\)になったって大した違いは無いと思うかもしれませんが、例えば\(n=100\)とすると、
\(2^n \approx 10^{30} = 1000000000000000000000000000000\)、
\(1.334^n \approx 3\cdot 10^{12} = 3000000000000\)
となり、その性能向上は圧倒的です(どちらも現在のコンピュータの性能では解けないのですが)。
Schoeningのアルゴリズムは非常に簡単です。\(K\)を後で決めるパラメータとしましょう。
入力: 3SATのインスタンス\(I=(V; C), |V|=n\).
出力: 充足解\(\alpha\)、又は充足不能。
(1) 以下を\(K\)回繰り返す
(1.1) 割り当て\(\alpha\)をランダムに選ぶ
(1.2) 以下を\(3n\)回繰り返す
(1.2.1) \(\alpha\)が全ての節を充足しているなら\(\alpha\)を出力
(1.2.2) \(\alpha\)が充足しない節\(C\)を選ぶ
(1.2.3) 節\(C\)中の変数\(x\)をランダムに選び、\(\alpha(x)\)をフリップ(trueならfalseに、falseならtrueにする)。
(2) \(I\)は充足不能と出力
簡単に以下が分かります。
[命題] インスタンス\(I\)が充足不能ならば、Schoeningのアルゴリズムは充足不能と出力する。
次にインスタンス\(I\)が充足可能だった時の挙動を考えましょう。何か一つ充足解\(\alpha^*\)を固定し、\(d(\alpha)\)を\(\alpha\)と\(\alpha^*\)のハミング距離とします。ここでハミング距離とは二つの割り当ての不一致の個数です。正確には\(d(\alpha) = |\{x \in V \mid \alpha(x) \neq \alpha^*(x)\}|\)となります。以下の補題が成り立ちます。
[補題] (1.1)で選んだ\(\alpha\)が\(d(\alpha)=j\)を満たすとする。この時(1.2)で充足解を見つける確率は\(\frac{1}{2^jO(\sqrt{n})}\)以上.
この補題を元にSchoeningのアルゴリズムが充足解を出力する確率を求めましょう。(1.1)で選んだ\(\alpha\)が\(d(\alpha)=j\)になる確率は\(2^{-n}{n \choose j} \)です。なので充足解を見つける確率は
\(2^{-n}\sum {n \choose j} \frac{1}{2^jO(\sqrt{n})} = \frac{1}{O(\sqrt{n})}(\frac{3}{4})^n\)
となります。\(K\)をその逆数より少し大きい値、例えば\(K = O(\sqrt{n}(\frac{4}{3})^n)\)と選ぶと、定数確率で充足解を見つけることが示せます。最終的な計算時間も\(O((\frac{4}{3})^n)\)となります。
それでは[補題]の証明をしましょう。最初割り当て\(\alpha\)から始めて、変数を一つずつ変えていくのですが、これは数直線状のランダムウォークとみなすことが出来ます。原点に充足解\(\alpha^*\)が存在し、\(\alpha\)は原点から\(d(\alpha)=j\)の所に存在します。
(1.2.3)では現在の\(\alpha\)が充足していない節\(C\)に現れる変数をフリップしています。ところが\(\alpha^*\)はこの節\(C\)を充足しているので、\(C\)中のある変数\(x\)が存在して、\(\alpha(x) \neq \alpha^*(x)\)のはずです。どれが\(x\)かは分かりませんが、少なくとも確率\(\frac{1}{3}\)で\(x\)を当てることができ、より\(\alpha^*\)に近い割り当てを得ることが出来ます。
つまり各ステップごとに少なくとも確率\(\frac{1}{3}\)で原点に近づき、多くとも確率\(\frac{2}{3}\)で原点から離れます。原点に到達すれば解\(\alpha^*\)を出力出来ます。ここではこれらの確率を正確に\(\frac{1}{3}\), \(\frac{2}{3}\)であるとします。計算量の下限を求めるにはこう仮定しても構いません。さて上の議論から結局次のような問題を解けば良いことが分かります。
[問題] 今原点から\(j\)の距離にいる。各ステップで確率\(\frac{1}{3}\)で原点に近づき、確率\(\frac{2}{3}\)で原点から遠ざかる。この時、\(3n\)ステップ以内に原点に到達する確率は何か。
後は簡単な計算問題です。\(m\)ステップ後に始めて原点に到達したとします。原点から遠ざかった回数を\(i\)と置くと、\(m=j+2i\)と表せます。\(m\)ステップ中に\(i\)回原点から遠ざかり、\(i+j\)回原点に近づくような組み合わせは\({m \choose i}\)通りあります。少し計算をすると、\(m\)ステップ後に”初めて”原点に到達する組み合わせは\(\frac{j}{m}{m \choose i}\)通り有ることが分かります。なので、\(p(j,i)\)を座標\(j\)からスタートして\(m\)ステップ後に初めて原点に到達する確率とすると、
\(p(j,i) = \frac{j}{j+2i}{j+2i \choose i}(\frac{1}{3})^{j+i}(\frac{2}{3})^{i}\)
と書けます。
\(p(j)\)を座標\(j\)からスタートして\(3j\)ステップ以内に原点に到達する確率としましょう。\(p(j) = \sum_{i=0}^jp(j,i)\)ですが、ここでは\(p(j) \geq p(j,j)\)という(かなり粗い)関係から\(p(j)\)を下から抑えることにしましょう。以下は計算だけなので、流れだけ見てもらえれば十分です。まず\(p(j,j) = \frac{1}{3}{3i \choose i}(\frac{1}{3})^{2i}(\frac{2}{3})^i\)です。スターリングの公式\(n! = \sqrt{2\pi }(\frac{n}{e})^n(1+o(1))\)を用いると、\({3i \choose i} \geq (3i)^{3i} / (i^i (2i)^{2i} O(\sqrt{2i}))\)と書けるので、更に計算を進めると\(p(j,j) = \frac{1}{2^jO(\sqrt{j})}\)となります。
解析は(研究者からすると)驚くほど簡単で、実装も(プログラマからすると)驚くほど簡単です。このようなインパクトのある結果が少し乱数を導入しただけで得られるのは面白いです。
[1] Schoening, T., A probabilistic algorithm for k-SAT and constraint satisfaction problems, Proc. of FOCS 1999, pp. 410-414, 1999.
Tag
