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

おはようございます。収穫の秋、食欲の秋でおなかがすいて困りますね。もっともおなかがすかないのも困りますが。小さい秋はここにもあります、とだけ今日は自己主張しましょうか。もっとも、ありがた迷惑でもう飽き飽きだ、というご意見の方がマスメディアでも述べられるかのように大多数かもしれませんが


さて、今回から三つ補題を紹介することにします。どういう名付けにするかに少し困りましたが、とりあえず補題a,b,cとすることにします。まず補題aから。


まず、補題aから

【補題a】
すべての近似サーキットは0だけからなるサーキットであるか、または否定的テストグラフの少なくとも

　　(1-lC2/(k-1))・(k-1)^n

の部分に対して1をアウトプットして計算する


【証明】いま近似サーキットを
　

　　　　　


とする。A≠0ならばA≧┌X1┐は明らか。

また、否定的テストグラフ（「その2」参照）においてクリーク表示┌X1┐が0となるのはテストグラフに付加された1,2,…,k-1で、X1の二つの頂点が同じ値を取る場合。一方、1,2,…,k-1の番号をn個のノードに付加する仕方は(k-1)^n通りで、どの付加の仕方も同じ確率で生じます。ノード集合X1の二つのノードが同じ番号を取る確率がをPx1とすると


　　　Px1≦|x1|C2/(k-1)≦lC2/(k-1)　　（1）

したがって、否定テストグラフにおいて┌X1┐が0を取る確率も（1）式で表わされるため、逆に否定テストグラフがあるクリーク表示┌X1┐で１を取る確率は

　　1-Px1≧1-lC2/(k-1)　　　　　　　　　　（2）

として表わされる。これが(k-1)^n個ある否定テストグラフの組み合わせそれぞれに言えるということから、補題は証明された、

ということになります。