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

おはようございます。クールジャパンと言いながらもいろんな問題を抱えている日本。その一つが飽食の問題でしょうか。世界中でヒットしている進撃の巨人というマンガも実は飽食の日本に対する子ども達の不安やいらだちを顕したものではないかとも思います。その一方でポケモンなどかわいらしいものもたくさんありますよね。最近妖怪ウオッチが爆発的なヒットだそうです。たまごっちみたいに世界中で社会問題になったものもありますから、これからどうなりますやら。しかし、どうして私の書いたものはどれもこれもヒットしないんでしょうかねえ。

やれやれと。では、前回で予定していた定理の証明まで終えたのですが、もう少しの間、補足説明などをさせて下さい。

まず、テキストから見た今回説明した定理までの位置づけですが、漸く本格的にこのテキストに書いてある内容について、基本的な部分の説明が終わったといったところでしょうか。ここまでご理解頂ければ、あとは、応用して詳しい議論がなされていくことになりますので、入門のブログとしては一通りの役目を終えたかと思います。

さて、mP≠mNPを証明した定理ですが、基本的にモノトーンであるという前提でした。ところが、すべてのモノトーンな命題を表わすサーキットが多項式倍のモノトーン・サーキットで表せるならばP≠NPの証明にもなるわけですが、そうとは限らないという証明が以下の論文でRazborovによってなされているとテキストにはあります。

「A lower bound on the monotone network complexity of the logical permanet, Math Zametyki, 37(6), 1985, 887-900(ロシア語）,英訳 Math. Notes, 37(6), 1985,485-493」

これは、今回説明した定理の証明と似た方法によって, mPに属する二部グラフの問題はモノトーン・サーキットでは多項式サイズで表せないことを証明した、とあります。また、E.Tardosは

「The gap between monotone and  non-montone circuit complexity is exponential, Combinatorica, 8(1),1988,141-142」

でモノトーンとノンモノトーンとの差がべき乗であることを証明しているとあります。要するにクリークのようなNPｰ完全な問題がモノトーンな命題であれば、多項式サイズに収まらないことはここまで見たように分っていることだとして、どうして、ノンモノトーンとの差が出るかということが問題となるわけです。

ノンモノトーンな命題においてサイズが減る様子に関して竹内先生がテキストに述べられているアイディアを説明して今回は終わります。実際の証明は次回以降になりますのでご了承下さい。

「まずアイディアを説明する。a1,…,anを相異なった元とする。このとき集合Aが{a1,…,an-1}であるか{a1,…,an-2,an}であるか,……または{a2,…,an}であるかであるか?という命題を考える。いま{a1,…,ǎi,…,an}をa1,…,anからaiを抜いた元の集合を表わすものとすれば、上のAは{a1,…,ǎi,…,an}のi=1,…,nのどれかということになる。ここで表わされるaの数はn(n-1)である(注：n個の元をとり、それをチェックするのにはn(n-1))。これをAは{a1,a2,…,an}からa1を取ったものかa2を取ったものか、……またはanをとったものかといえば、aの表わされる数は2n（注：取り出す組み合わせがnチェックにn）とすくなくなる」

とあります。先にも少し書きましたが、次回以降はこのことについて、ブール代数の場合に翻訳し、同等であるという定理の証明をします。