ノンモノトーンで計算が減る場合 その2

おはようございます。今回からは少しまじめにお話しします。自分の考えをお話しするので緊張するのです。


今回ここで発表することは、すでに、「http://etsurohonda-blog.blogspot.jp/2011/11/pnp.html」やhttp://etsurohonda-blog.blogspot.jp/2011/11/pnp.html」などで発表しているのですが、改めてきちんと考察をしてまとめておこうということもありまして、身の程知らずにもここに書かせて頂きます。

基本的なアイディアをまず述べます。

(a∨b)∧(￢b∨c)

の括弧を外すことを考えると普通ならば

(a∨b)∧(￢b∨c)=a∧￢b∨a∧c∨b∧￢b∨b∧c

となり、計算量は増大するように思われますが、一般に公式を用いると

(a∨b)∧(￢b∨c)=a∨c　　　　　　　　　　（１）

となり計算量は減ります。

さらに

(a∨b∨c)∧(￢b∨￢c∨d)

のような論理式は（１）を応用すると

(a∨b∨c）∧(￢b∨￢c∨d)=(b∨(a∨c))∧(￢b∨(￢c∨d))
　　　　　　　　　　　　=(a∨c)∨(￢c∨d)
                        =a∨c∨￢c∨d
=a∨T∨d
                        =T
となります。


これをSATの節に応用して考察していきます。そのとき、以下の二つの考え方を用います

一つ目は、SAT表現における節において、各変数はブール変数であるため取りうる値は二値ですが、実際には項があるかないか、あれば真か偽かという事で、場合としては三通りの場合分けで考察します

二つ目は、たくさんの節集合がある場合に、適当な二つの節を持ってきる場合を考えます。はじめに論理式で説明したように、その節に同じ項があり、逆の値を持つときには計算せずその値を消去できます。例えば{{a,b},{not(b),c}}という節は,{{a,c}}と同値になります。そのため節が一つとなる、あるいはあとで説明しますが、節自身が消滅する場合もあり、著しく計算量が減るという考え方です。以下はもう少し詳しく場合分けして考察していきます。

※以下はSAT表現で、節集合Ｃの元の数はr、節の各リテラルは元々はm個のブール変数であるとして以下考えていきます

（a）適当に取った二つの節に同じ項があり逆の値を持つ場合
上でも説明していますが、部分的に{{a,b},{not(b),c}}=｛{a,c}｝とできる場合のことです。この場合、ある節にbが含まれ別の節にnot(b)が含まれる確率を考えます。そうすると、確率は1/9となる事が分かります。また、その逆もあり得ますので、確率は二倍となり、その場合に減る計算量は上の式の左辺の計算量は単純に3これが右辺では１ですのでとなります。
（注：以前のブログでは逆もありうるということを考慮に入れていませんでしたので修正しています）

ここからが以前と違う結論になるのですが、探すコストが9/2であるのに対し減らせるコストが2、前後に他の項があれば4の場合もあります。すなわち減らせる計算量は最大でも4。場合減らすコストより一致する項を探すコストの方が大きくなるため、この場合はやるだけ無駄ということになります。

（a'）適当に取った二つの節に二つ同じ項があり一つは同じ値、もう一つは逆の値を持つ場合

この場合の例としては{{a,b},{a,not(b)}}=｛{a}｝となり、かなり小さくなっていますが、変数が増えると{a}にあたる部分が複数の変数からなりすべて一致するとのは比較的まれな場合と考えられます。また、見かけ上は小さくなっていますが、{a}に相当する部分が複数の変数よりなる場合の計算のコストは(a)の場合とほぼ同様と考えられますので考察から除外しても問題ないと考えます。

（b）適当に取った二つの節に同じ項二つありそれぞれがあり逆の値を持つ場合
部分的に{{a,b,c},{notb,notc,d}}のような節がある場合です。この場合、探すためのコストは81/4の定数倍となりますがこの場合二つの節が一つになったときに真となります

　　例）{{{a,b,c},{not b,not c,d},{e}}=｛{a,c,not c,d},{e}}={{T},{e}}={{e}}

そのため、この場合、節二つ分を計算する必要が無くなり、減らす事のできるコストは論理和と論理積の個数即ち、（(節Aの長さ-1)+（節Bの長さ-1)+1）となります。従って、節の長さ（節の中の変数の個数）が11に等数発生などのコストを上乗せし、上回る場合はこの手法は有効となります。


今回は以上ですが、次回、この方法であるならば、乱数を発生させて適当な節と変数に注目すれば確率4/81ではありますが、大きく計算量を減らすことができる、と言う点に着目してもう少し考察を深めてみたいと思います。