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

おはようございます。大学は宮崎の大学に通ったのですが、日本も南の方に行けば行くほど時間にはだいたいでして、あちらには日向時間というものが存在しました。だからいつだってじれったかったりするのですが、慣れればそれが良かったりすると言う恐るべきもの。ちゃわちゃわっていう女の子の方言もかわいかったですね。もちろん熊本弁もかわいいですが。何処に行ってもその地方の女の子の方言の語尾ってかわいくて味がありますよね。


さて、今回から少しずつmP≠mNPを説明していくことになります。この結果はテキストによるとA.RazborovとA.E. Andreevがほとんど同時に独立に証明したものである、とあります。

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

　　　　

  ※註　当然のことながら、ここでf(n)=Ω(g(n))は、c>0なる実数が存在していればf(n)≧c・g(n)となるような関数


【証明の方針】
もしサーキットサイズが小さければ、そのサーキットはだいたいの肯定テストグラフに0の値を与えたいていの否定テストグラフには1値を与えることをいう


以上のようなやり方でやっていくのですが、詳細は追々説明するにしても、これがいくつもの補題があるのでややこしいです。

さて、だいたいの、ということがありましたが、考え方としてまず肯定的テストグラフであるか否定テストグラフであるかどうかの判断はn個のノードがある場合k個のノードかk-1個のノードのクリークがあるかどうかを判定してから詳細に判断すればいいわけで、そういう考え方の元、以下にクリーク表示というものを定義します。

【クリーク表示の定義】
　グラフGのノード集合Xがあったときに、これがクリークになっているときに、
　
　 ┌X┐(G)=1

そうでないときには

　 ┌X┐(G)=0

と┌X┐を定義してクリーク表示と言うことにします


また、クリーク表示を用いて近似サーキットというものを考えます。まず定義の方針としては、高々m個のクリーク表示を∨で結んだもの、すなわち┌X1┐∨┌X2┐∨…∨┌Xr┐でr≦m、またさらに|Xi|≦lがすべてのi=1,…,rに対して成立しているものとします。ただしm≧2かつl≧２です。さて元のサーキットのノード数nやいくつのノードのクリークであるかを示すkにk関する制限は後ほど述べていくことにして、モノトーン・サーキットCを近似サーキットC'にする場合の定義の条件というものを記しておきましょう。

【近似サーキットを定義する際の条件】
　1．Cが小さいモノトーン・サーキットならば、たいていの肯定的テストグラフGについて
　　
　　　　C(G)≦C'(G)

　　が成立している。

　　さらに、たいていの否定テストグラフGでは

　　　　C(G)≧C'(G)

　　が成立している。

すなわち、近似サーキットの方が肯定テストグラフにおいては成立するものが多く、否定的テストグラフの方では元のサーキットの方が成立するものが多いという事ですが、証明の方針に従って

　2．すべての近似サーキットは、たいていの肯定的テストグラフに0の値を与えるか、またはたいていの否定的テストグラフに1を与えるかのどちらかである

という条件も加えます

次回は、この近似テストグラフをリーフから順に定義していきます。