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

おはようございます。ではなく、こんにちはになってしまいましたか。何でも、日本の若い方の70％は生まれ変わっても日本に生まれたいとか。最近これが一番日本らしいなと思いました。窮屈な日本ですが、それなりになれると住みやすく離れづらい、そういうことなのでしょうか。それとも、いったん外国に出たら最後、なかなか就職なども難しくなるらしいというのが影響しているのか。まさか、生まれ変わってまで、ずっと日本人じゃ無きゃいじめられる世界というのも怖いですね。いろんな意味で開かれた日本というのも大事だと思います。


いよいよ今回は、問題となっているA.RazborovとA.E. Andreevが証明した定理（「その3」参照）の証明に入りたいと思います。

【定理】（再掲）

1<k≦n^(1/4)とするときClique k,nを表わすモノトーンサーキットのサイズは少なくても

　n^Ω(k^(1/2))

【証明】

ここでは、まず、lとpを以下のように定めておくことにします。

　　l=└k^(1/2)┘,　　p=┌10k^(1/2)logn┐

　　※ここで└a┘は≦aを満たす最大の整数、また┌a┐は≧aを満たす最少の整数

またlogの底は断らない限り2で、mはいままで通りm=(p-1)^l・l!(「その６」参照)です。


さて、つぎに、補題a(「その7」参照)を再掲すると

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

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

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


とありましたが、いまこの　(1-lC2/(k-1))の部分を考えますと、k<1でl=└k^(1/2)┘より、2lC2<k-1が求められ（例：k-1=1が最少。このときl=1で1C2=0。lはごくゆっくりとしか増加しない事が分れば帰納法的にすぐ分ります）、サーキットCの近似サーキットC'は0であるか、少なくても1/2・(k-1)^n個の否定テストグラフに1を与えることが分ります。

この場合を二つに分けて考えていきます。

(a)近似サーキットC'=0を取るとき

　このとき肯定テストグラフが誤って0を出力する即ち、C'＜Cとなるようなグラフの数は補題b（「その8」参照）より求まっていますので

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

これより、

　　　size(C)≧(n!(k-l-1)!)/(k!(n-l-1)!m^2)

が、求まります。

いま1<k≦n^(1/4)としていますから、上の式の(k-l-1)!/k!の部分を考えると、

　　　　(k-l-1)!)/k!≧k^(-(l+1))≧n^(-(1/4)k^(1/2))

同様にn!/(n-l-1)!の部分を考えると

　　　　n!/(n-l-1)!≧(n-l)^(l+1)≧(n-n^(1/8))^(k^(1/2))≧n^((15/16)k^(1/2))

また、
　　　　m=(p-1)^l・l!と　l=└k^(1/2)┘より

　　　　m^2＜p^(2l)・(k^(1/2))^(2l)=(p(k^(1/2)))^(2l)＜n^((9/16)k^(1/2))

　　　　1/m＞n^(-(9/16)k^(1/2))

ですから

　　　size(C)≧(n!(k-l-1)!)/(k!(n-l-1)!m^2)≧n^((1/8)k^(1/2))

となり、定理を満たしています。

次回、(b)否定的テストグラフの少なくとも

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

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

を説明します。もちろん頭の良い方でしたら、もう自分で導き出せますよね。