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

おはようございます。

今回は、前回に引き続き、

(a∨b∨c）∧(￢b∨￢c∨d)=T

という事を利用して、SAT表現で部分的に{{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}}


まず、モノトーンの場合普通のサーキットであれば、前回の節までで考察したように、オーダーは

size(C)=2^(p-1)/m^2≧n^(8・k^(1/2))

より決まります（参照：モノトーンそしてmP≠mNP その11（http://peunp.blogspot.jp/2014/11/blog-post.html））

ところが、乱数を発生させずに、

(a∨b∨c）∧(￢b∨￢c∨d)=T

となるものを探すということを考えますと、節集合Cの元の数|C|をn、節の中のブール変数の平均の数をmとおいて、総当たりで探すことになりますから、オーダーは単純に考えるとO(m^2*n^2)となり、オーダーは多項式で表わすことができるようになります。発生確率も4/81と比較的高いことから、乱数で元を発生させたようなホワイトノイズがSATの節にある場合は著しく計算量を減らすことができるということになります。つまりNTMで適当にデータを作成して処理するというような場合ほとんどの場合ホワイトノイズであると考えられますので、多項式時間で解を求められるのではないのかと考えます

さらに、乱数を発生させて探す場合にはオーダーは確率4/81の逆数の84/4に乱数発生のコストを加えたものを定数Aとすると、コストは最悪でもA（m^2）より大きくならず、即ちオーダーは（m^2）まで押さえられると思われます。

プログラムを用いた乱数を場合どれくらいの試行を行えば良いかを確認したのですが、例えば、n=1000,r=100の場合、81×100の試行で約56％、81×500で約98％まで節の数は減少し、81×800で99.7％、81×100で残りの節はほぼ0か1にまで減少しました。

検証用のプログラムはGitHubにアップロードしています。（実際はいくつかのバージョンがあるのですが、今回の検証用のプログラムだけアップロードします）。プログラムの解説は、今回のブログの目的から外れますので行いませんが、よろしければ、どうぞご確認下さい。

アドレスはこちら

https://github.com/Futarisizuka/SAT_term_compress_simulation