P=NP?問題の証明のもっとも肝心な部分についての考察

私の知っている範囲で言うとP=NP?問題では全て肯定的なリラテル（論理式の最小単位）の場合P=NPであることが証明されています。

残る問題は否定のリラテルがあった場合、計算量を減少させられる事が知られていますが、それがどれくらいの影響があるかと言うことでしょう。

そこで考えたことを、以前mixiの日記にメモ書き程度に残したことをここに公表したいと思います。ちなみにRotaTRはわたしのIDです。


否定のリテラルによって減少する計算量は０　2010年09月28日14:29
SATに於いて計算量を減らせるのは、
あるブール変数以外がまったく同じ場合

節集合Ｃの各節はブール変数の論理和で表されるが
そこに表されていないブール変数の値はＦとしてよい。

従って各節はブール変数の二つのリテラルとＦの３つの値を取り得る。

ブール変数の集合Uがm個のブール変数を持ち、ｍが十分大きいとする。
また、節集合の元の個数ｒとする

このときある節が節集合Ｃに現れる確率はｒ/3^m
それと対になり消滅する節が同じ節集合に現れる確率もほぼ同じ

一方それによって少なくなるＴＭの計算量はO（r/2）

従って、mが十分大きいとき否定のリテラルによって減少する計算量は０
コメント
コメント

RotaTR2010年09月28日 14:41

> SATに於いて計算量を減らせるのは、
> あるブール変数以外がまったく同じ場合
> 説集合Ｃの各節はブール変数の論理和で表されるが
> そこに表されていないブール変数の値はＦとしてよい。
> 従って各節はブール変数の二つのリラテルとＦの３つの値を取り得る。
> ブール変数の集合Uがm個のブール変数を持ち、ｍが十分大きいとする。
> また、節集合の元の個数ｒとする
> このときある節が節集合Ｃに現れる確率はｒ/3^m
> それと対になり消滅する節が同じ節集合に現れる確率もほぼ同じ
> 一方それによって少なくなるＴＭの計算量はO（r/2）
> 従って、mが十分大きいとき否定のリラテルによって減少する計算量は０

少なくなる計算量は平均でｍ／２の定数倍が正しいです。
お詫びして訂正いたします

RotaTR2010年09月28日 19:45
リラテル＝＞リテラル
説集合＝＞節集合

と修正

RotaTR2010年09月29日 03:45
しまった。いろいろ間違ってる。

｛｛a,b｝,{a,NOT(b)}={a}

だｗ

まぁ、こんな感じで減らせるんでしょう。
節の出現確率のところだけは使えるな（笑い）

RotaTR2010年09月29日 03:50
情けないなぁ、まったく

補足しておくと、{{a,b,c},{a,b,NOT(c)}}={{a,b}}

まぁ、減らせる計算量は同じだけど、更に減らせる可能性があるよね

RotaTR2010年09月29日 03:52
{{a,b,c},{a,b,NOT(c)},{a,NOT(b})}
={{a,b},{a,NOT(b)}}
={{a,b},{a,NOT(b)}}
={{a}}

とかね。

RotaTR2010年09月29日 03:55
あ、しかし、そういう節の出現確率も上記の出現確率だから、良いのか。
あははｗ

ま、まぁ、出先でのメモということで許して下さい。
いろいろと検討が足りなくてすいません。

RotaTR2010年09月29日 04:10
しかし、ごくまれだと思うけど、


{{a,b,c},{a,b,NOT(c)},{a,NOT(b})}
={{a,b},{a,NOT(b)}}
={{a,b},{a,NOT(b)}}
={{a}}

の例のように計算するブール変数の量が減らせるときは、計算量は著しく減る場合もあるね。そこの変まできっちりと計算する必要があるのかな。ないと思ってたけど、検討すべきですか？うーん、ちゃんとすべきかもね。そこ変が残る課題か。

RotaTR2010年09月29日 04:19
あ、いいか。そういえば、昼に頭の中で検討したときには、パターンは出現確率がｒ／３^mに対し、そのようなパターンで削減される計算量はO(2^m)なので、削減量は確率を考えると、最大でO(２＾ｍ/３＾ｍ)なはずで、ｍが大きくなると、０に近づくと考えたのだけど、大丈夫だよね？

RotaTR2010年09月29日 04:20
なんか、本当にいろいろダメだなぁ（苦笑）