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

おはようございます。と言ってもまたお昼を廻ってしまいました。申し訳ありません。昨日は冬至だったようです。最近道理でミカンがおいしい。ええ、冬に到っても食欲は落ちていません。それにしても、昨日の十五夜お月様も綺麗でしたね。十三夜のお月様はミラクルムーンと言ったらしいですが、十五夜お月様も丸々としていて実においしそう、いや美しかったです。

今回は定理の証明の続きですね。難しい言葉を使えば承前。

(b)近似サーキットC'が少なくても(1/2)(k-1)^nの否定的テストグラフの値に1を与えるとき

このときは補題c(「その9」()参照 )より

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

が成立。このとき、l≦(1/2)(k-1)から次の不等式が得られます。

　　　　　((n-l-1)C(k-l-1)//(k-1)=l(l-1)/(2(k-1))≦(K^(1/2)(K^(1/2)-1))/(2(k-1))<1/2

したがって、このほか1<k≦n^(1/4)、m=(p-1)^l・l!などを用いて次の不等式がすべて成立します。

　　　　　size(C)・m^2・2^(-p)≧1/2
          size(C)=2^(p-1)/m^2

　　　　　2^(p-1)≧2^(9・k^(1/2)・logn)=n^(9・k^(1/2))

　　　　　(p-1)^(2l)≦(11・k^1/2・logn)^(2・k^(1/2))≦(n^(5/32))^(2・k^(1/2))=n^(5/16・k^(1/2))

　　　　　(l!)^2≦(└k^(1/2)┘)^(2・k^(1/2))=n^((1/4)・k^(1/2))
　　　　

以上より

          size(C)=2^(p-1)/m^2≧n^(8・k^(1/2))

が求められ、定理は証明されました。

次回は補足説明などを予定しています