モノトーンそしてmP≠mNP その8

おはようございます。日本語には同音異義語が多く、これがいろはうたや駄洒落などの多く言葉遊びを生む要因にもなっています。でも、ここ最近随分寒くなってきてるので、そんなことをすると滑ってさらに寒くなるといけませんから、近似られたサーキットの方をを以下説明しましょうね。うう寒い。


今回は補題bを説明していきます。

【補題b】Cはモノトーンサーキットとする。このとき、肯定的テストグラフでそのグラフではC≦C'が成立（「その3」を参照）しないようなグラフの数は

　　　　　≦size(C)・m^2・(n-l-1)C(k-l-1)

　　　　　※ただし、kはクリークとなるノードの数（「その3」参照）、
　　　　　　　　　　　lは濃度、m=(p-1)l(「その5」参照)、nはノードの数
　　
を満たす

【証明】
いま、

　　A=┌X1┐∨┌X2┐∨…∨┌Xr┐,　B=┌Y1┐∨┌Y2┐∨…∨┌Ys┐

として、

　　A∨B≦AЦB　　または　　A∧B≦AПB

が成立（「その6」参照）しないような肯定的テストグラフの数が、高々

　　m^2・(n-l-1)C(k-l-1)

であるということを言えば、このような近似サーキットへの変換にかかる計算量はsize(C)で押さえられる、つまりたかだかクリーク表示の数であることは明らかですから、補題は証明されるということになります。

まず、AЦBの方ですが、花つみの結果においても近似サーキットは元のサーキットに比べ重複がある可能性がありますので、常に、A∨B≦AЦBとなり、問題ありません。

つぎに、AПBの方を考えるます。「その6」で行った作る過程を検討してみると、

(1)┌Xi┐∧┌Yj┐を┌Xi∪Yｊ┐に書き換るのは、どんな肯定的テストグラフにおいても同値であるので問題ありません。

(2)もし|Xi∪Yｊ|>lならば┌Xi∪Yｊ┐を消す場合。この場合はXi∪Yｊ|を含むような肯定的テストグラフがどれだけあるかを考えます。いま|Xi∪Yｊ|>lすなわち、|Xi∪Yｊ|≧l+1ですのでXi∪Yｊを固定すれば、肯定的テストグラフのk個のクリークをなしているノードの中にすくなくてもl-1個のノードを持つXi∪Yｊは存在し、それ以外の同じ数の消す訳ですから、組み合わせは多くても、

　　(n-l-1)C(k-l-1)

であることが分ります。ところでこの消すノードの数は高々m^2ですから全体としては

　　m^2・(n-l-1)C(k-l-1)

となります。

（3）花つみでは、AЦBの場合と同様につねに、A∧B≦AПBとなりますので問題ありません。

以上のことより、全体としての数は

　　　≦size(C)・m^2・(n-l-1)C(k-l-1)

であることが証明されました