Blog
吉田です。もうしばらくLovasz Local Lemma (LLL)にお付き合い下さい。
LLLとは確率事象\(A_1,\ldots,A_m\)が存在したときに、ある条件下でそのどれもが起こらないことが有ることを示す定理でした。その応用例として、\(k\)-CNFのインスタンス\(X\)がどの節も他の高々\(2^k/e\)個の節としか変数を共有しない時、\(X\)の全ての節を充足する解が存在することを見ました。前回のLLLでは解が存在することを保証するのみでしたが、今回はその解を実際に求める話をしたいと思います。2009年の非常に最近の結果です。
CNFとはリテラルの論理和からなる節を論理積で繋げたものでした。例えば以下はCNFの例です。
\((x \vee y) \wedge (\bar{x} \vee z)\)
リテラルとは変数に否定が付いたり付かなかったりしたもののことを呼びます。また一つの節に高々\(k\)個のリテラルしか含まないものを\(k\)-CNFと呼びます。目的は変数(上の例では\(x,y,z\))にtrue/falseの値をいれて全ての節を充足することです。例えば上の例ですと、\(x = \mathrm{true}, y = \mathrm{false}, z = \mathrm{true}\)は充足解の一例になっています。
さてLLLから、\(k\)-CNFのインスタンス\(X\)がどの節も高々\(2^k/e\)個の節としか変数を共有せずしない時、\(X\)は充足可能であることが示されます。これに対してMoserとTardosは[1]で実際に(LLLと近い条件下で)解を求めることが出来ることを示しました。このように存在性を示すだけでなく解も求めることが出来るような手法を”構成的”と呼びます。今回の話題もConstructive(構成的) Lovasz Local Lemmaと呼ばれています。ちなみに構成的の反対語は非構成的で、その典型例は不動点定理になるでしょうか。
さてMoserとTardosによるアルゴリズムは以下の通りです。\(\mathrm{vbl}(C)\)で節\(C\)に現れる変数を示すことにします。
moser(\(X\)):
ランダムな解を選ぶ
while ある節\(C\)が存在して現在の解において充足されていない
fix(\(C\))
fix(\(C\)):
\(\mathrm{vbl}(C)\)に対する割り当てをランダムに選び直す
while \(C\)と隣接するある節\(D\)が存在して現在の解において充足されていない
fix(\(D\))
非常に簡単です。というよりもアルゴリズムには何の工夫もありません。アルゴリズムが停止すれば充足解を与えることは明らかですが、これが実際に止まることを示したのがMoserとTardosの素晴らしい所です(個人的にはアルゴリズムが簡単で解析が大変というのが、一般の人に貢献している気がして好みです)。\(d\)を節と変数を共有する節の数の上限としましょう。
[定理] アルゴリズムmoserは\(d < 2^{k-3}\)の時、多項式時間で終了する。
[略証] まずインスタンス\(X\)は\(n\)変数、\(m\)節からなるとする。アルゴリズム中で使用する乱数を二通りの方法でカウントすることで計算時間を求める。
もしアルゴリズムmoserが\(r\)回のfix呼び出しで終了したとする。この時使用した乱数は\(n + rk\)ビットである。
この乱数列はアルゴリズムの動作の過程を利用して記録することも出来る。最初のランダムな解においてどの節が充足されているかを記録するのに\(m\)ビット使う。また各fix呼び出しの動作は\(\log d + 3\)ビットで記録することが出来る。ここで\(\log d\)ビットで次のどの節\(D\)に対してfix(\(D\))を呼び出すかを記録し、残りの\(3\)ビットでそのfix呼び出しの後にwhileループを抜けたかどうか(など)を記録するのに使う(\(3\)で出来ることは別途証明が必要)。最後に得られた解を記憶するのに\(n\)ビット使う。これらの情報が有ればアルゴリズムが途中で使用した乱数を全て復元出来ることが示せる。
乱数は”圧縮出来ないので”
\(m + r(\log d +3) + n \geq n + rk\)
よって
\(m \geq r(k – \log d – 3)\).
もし\(k – \log d – 3 > 0\)、即ち\(d < 2^{k-3}\)であれば、\(r = O(m)\)と抑えることが出来る。\(r\)はアルゴリズムがfixを呼び出す回数だったので、アルゴリズムの計算時間は\(rn = O(mn)\)で有ることが示せた。
この乱数のビット数を二通りの方法でカウントする手法は他に類を見ない非常に面白い議論だと思います。今のところ同じ考え方が他の問題に適用出来たという話を聞きませんが、必ずまだ面白い応用が眠っていると思っています。
さて、このアルゴリズムは\(k\)-CNFだけの為のものでなく一般化することも出来ます。確率事象を\(A_1,\ldots,A_m\)とし, \(A_1,\ldots,A_m\)は変数\(x_1,\ldots,x_n\)によって定義されているものとしましょう。\(k\)-CNFの時と同じ様に\(\mathrm{vbl}(A_i)\)で事象\(A_i\)が依存している変数集合を表すことにします。
次のようなアルゴリズムを考えます。
\(x_1,\ldots,x_n\)に対するランダムな割り当てを選ぶ。
while ある\(A_i\)が存在して\(A_i\)が”起こっている”
\(\mathrm{vbl}(A_i)\)をサンプルしなおす
証明の詳細には入りませんが、LLLの仮定が成り立つ時、上のアルゴリズムも停止して、具体的に\(A_1,\ldots,A_m\)がどれも起こっていない解\(x_1,\ldots,x_n\)を求めることが可能です。
[1] Robin Moser and Gabor Tardos, A constructive proof of the general Lovasz local lemma, J. ACM, 57(2), 11:1–11:15, 2010.
Tag
