P=NP?問題で計算量が減るもう一つのパターン

以前、このブログのP=NP?問題の証明のもっとも肝心な部分についての考察という記事で、計算量が著しく減るパターンとして、{{a,b},{a,not(b)}}={{a}} （ＳＡＴ形式で記述）というものを挙げていましたが、ほかに、{{a,b},{not(b),c}}={{a,c}}というパターンがある事に最近になって気付きました。つまり、b=Tの時には{{a,T},{F,c}}=cとなり、b=Fの時には｛{a,F},{T,b}}=aとなるため、全体としては{{a,b}}となるようなパターンです。こちらの方は計算量の減り方はやや落ちるものの、ブール変数aに対しnot(a)のブール変数があれば、必ず計算量は少なくなります。この場合は、削除されるブール変数の対（例えば、aとnot(a))以外は何でも良いので、P=NP?問題の証明のもっとも肝心な部分についての考察の時に対して、計算量が減る確率は多くなります。

つまり、ブール変数の個数mと節集合Ｃの節の元の数rが増えるにつれて、P=NP?問題の証明のもっとも肝心な部分についての考察のパターンは無視できるほどの出現確率になりますが、それに対しこのパターンは、最大で節の数rの半分の節の数だけ計算すれば良いという、計算量の減るパターンであるという事です。

これをもう少し詳しく場合分けしてみてみたいと思います。

まず、

a).部分的に{{a,b},{not(b),c}}=｛{a,c}｝とできる場合

 この場合、ある節にbが含まれ別の節にnot(b)が含まれる確率を考えます。そうすると、確率は2/9となる事が分かります。その場合に減る計算量は上の式の左辺の計算量は単純に3これが右辺では１ですので減少する計算量は２。確率的な平均を出すと2/9の減少量となります

さらに、
b). {{a,b,not(c)},{a,not(b),c,d},{e}}={{a,c,not(c),d},{e}}={{T},{e}}={{e}}となるパターン
があります。
つまり、部分的に{{a,b,not(c)},{a,not(b),c,d}}={{a,c,not(c),d}}=Tとなるペアの発生確率は、問題となる二つのブール変数のとりうる３ｘ３ｘ３ｘ３通りのうちの１パターンであるので１/81と意外に大きい事が分かります。つまり、2/81の確率で、最大mx2の計算量が減少します。つまり、その場合があったとして、減少量は節の平均の長さを確率的にm/2と考えた時に、減少量は平均でmです。

まとめると、つまり、ある節集合Ｃにおいて、任意の二つのブール変数を取り出し、その二つの ブール変数が、部分的に節集合｛{{a,b,not(c)},{a,not(b),c,d}}のb,cような形で取り出される場合は１2/81の確率で発生するので、減少量は平均でm/81となります。


他に、例外的に、

.{{a,b,c},{a,not(b),c},{a,b,not(c)},{a,not(b),not(c)}}
   ={{a,c},{a,not(c)}
   ={{a}}

となるパターンもあるでしょうが、これは、P=NP?問題の証明のもっとも肝心な部分についての考察で考えた場合と同様に確率的に０に近づくと考えられ無視できます。

さて、上記a),b)は節集合Ｃの元の数rが増えると発生する場合の数はそのrに比例して多くなり、それはブール変数mのうちからa)の場合一つ、b)の場合二つに注目すればいいという事が分かると思います。

まず、a)の場合から考えましょう。

r個の節から2つを取り出し、その平均ｍ/2の節内の変数がa,not(a)となっているようなパターンは、
節は同じものが二つあってもかまいませんから（計算量は2倍になるがオーダーとしてみた時は大丈夫）

{rx(r-1)/2x1}x{1/9xm}

この場合の計算の減少量は2であるから、オーダーとしてみた場合、Ｏ（ｍｒ）で計算量が減る事になります。


 ｂ）の場合も同様ですが、計算量の減り方がmに比例しますのでオーダーとしてみた場合O（m^2ｒ）（ ＾はべき乗の記号 ) となってきます。


 とりあえず、ここまでにしておきましょう。ここまでが間違ってないかどうかが問題ですから。この先の検討は、また次の機会に。