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

おはようございます。といいながら時は流れてもうこんばんは、あるいはお休みなさいの方がいい方もいらっしゃるかもしれません。では、おやすみ……トドのように、と言いたいところですが、もうちょっとがんばらないとですね。「秋の田の」といえば「我が衣手は露に濡れつつ」と来るのが百人一首。なんでも、上の句を分類して「あ」の音で始まる詩はいくつあり、と言うようにいろいろなテクニックがあるようですが、坊主めくりで良いと言えばそれでも良いですよね。人類の発展のためにはちょっとそれでは寂しいのかもしれませんが。


今回は補題cを説明していきます。苫を粗まないようにしないとですね。

【補題c】Cはモノトーンサーキットとします。このとき、C≧C'が成立しないような否定的テストグラフの

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

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

【証明】
補題bと同様にいま、

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

として、

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

が成立しないような否定的テストグラフの数が、高々

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

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

(1)　AЦB≦A∨B　が成立しない場合
AЦBはA∨Bから高々2m回の花摘みで得られることから、1回の花つみで新たに受容される否定的テストグラフの数を考察することにすると、まず否定的テストグラフで与える1～k-1の番号の与え方は(k-1)^n通り。その中の一つから定義される否定的テストグラフをGとします。

集合の集合の元Z1,Z2,…Zpがあってひまわりを作っており、その中心をZとします。このとき

　”┌Z┐がGを受容する（命題Aとおく）か、または、どの┌Z1┐,┌Z2┐,…,┌Zp┐もGを受容しない(命題Bとおく)”

は次のことと同等です。（A∪B=￢(￢A∩￢B)の形式になっています）

”Zの二つの頂点に負荷された値は相異なる（命題Aの否定）が、同時にどのZiをとっても、その中に二つの頂点で負荷された値が同じものが存在する（命題Bの否定と共に上の命題全体の否定にもなっている）”

これらから次の確立についての不等式が出てきます。以下のZが正付加とは、Zの相異なる二つの頂点に付加されたの値が異なることと定義しています。（Pr[x]は事象xに関する確率）

　　Pr[Zは正付加であるが、Z1,Z2,…,Zpは正付加でない]

　　≦　Pr[Z1,Z2,…,Zpは正付加でない|Zは正付加である]

　　　　※Pr[A|B]はB上のAの相対確率（Pr[A∩B]/Pr[B]）を表わしている
　　　　
　　=　Pr[Z1は正付加でない|Zは正付加である]×Pr[Z2は正付加でない|Zは正付加である]×…
　　　　×Pr[Zpは正付加でない|Zは正付加である]

　　≦　Pr[Z1は正付加でない]×Pr[Z2は正付加でない]×…Pr[Zpは正付加でない]

上の式の二番目から三番目の等号で結ばれた式の関係は”Ziが正付加でない”という確率変数が”Zは正付加である”上の相対確率として独立であることを用いています。

同じ式の三番目から四番目ですが、以下の図を用いて説明すると、

三番目の式はB/(B+C)で表わされ、四番目の式は（A+B)/(A+B+C)と表わされます。証明したいことは、

　　B/(B+C)≦(A+B)/(A+B+C)

ですが、分母を払うと

AB+B^2+BC≦AB+AC+B^2+BC
　　　　0≦AC

と変形され確かに成立します。

ところで、補題a（「その7」参照）で見てきたように、


　　　Pr[Ziは正付加でない（ノード集合Ziの二つのノードが同じ番号を取る）]≦lC2/(k-1)　

ですから、

　　　Pr[Zは正付加であるが、Z1,Z2,…,Zpは正付加でない]≦（lC2/(k-1)）^p

となり、花つみ一回ごとに、高々（lC2/(k-1)）^p・(k-1)^nの新しい否定テストグラフがAЦB≦A∨Bを満たさないことが分ります。

したがって、全体では高々2m回の花つみがありますから、次の数で抑えられます

　　　2m・（lC2/(k-1)）^p・(k-1)^n

(2)　AПB≦A∧B　が成立しない場合
　補題b（「その8」参照）の時と同様に、A∧BからAПBを作る過程に従って考える

(a)┌Xi┐∧┌Yj┐を┌Xi∪Yｊ┐書き換えるとき

　┌Xi∪Yｊ┐≦┌Xi┐∧┌Yj┐

がどんな否定グラフでも成立するので問題がないことになります


(b)|Xi∪Yｊ|>l+1のとき┌Xi∪Yｊ┐を消すこと

これはサーキットのサイズが小さくなることなので問題ないということになります


(c)花摘みの場合

　これは(1)と同様に考えます。

したがって、全体として

　4m・（lC2/(k-1)）^p・(k-1)^n

となり、mが十分に大きければ

　4m・（lC2/(k-1)）^p・(k-1)^n≦　m^2・（lC2/(k-1)）^p・(k-1)^n

が成り立ちますから証明は終わりました