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

おはようございます。何故か休みの日の朝が一番しんどいという気がするのですが何故でしょうか。そうです、それはこのブログの記事をを書かないといけないから……。え、あ、なぜか、またしーんとしちゃって……。え、あの、もとい、その前の日にしっかりと仕事をがんばってきているからです。ええ、多分、そうです。いや、多分、そうに違いありません。


さて、今回は引き続き定義となります。

前回は言語Lやpredicate Pがモノトーンであるとはどういうことかと言うことを定義しました。今回はそれらがクラスmNPやクラスmPに属することがどういうことかということについて定義していきます。

【クラスmNPに属するという事の定義】

• 言語LがmNPに属することをLがモノトーンであってさらにNPに属することとする
• predicate PがmNPに属することも同様にpredicate PがモノトーンであってさらにNPに属することとする

【クラスmPに属するという事の定義】

• 言語LがmPに属することをLが多項式サイズのユニフォームなモノトーン・サーキットで表わされることとする
• predicate PがmNPに属することも同様にpredicate Pが多項式サイズのユニフォームなモノトーン・サーキットで表わされることとする
  ※ここでモノトーン・サーキットとはリーフのブール変数がx1,x2,…,xnで表わされ、￢x1,￢x2,…,￢xnではないということ

さてこのほかに問題を扱う上で重要となるのが、predicate Pの扱いですが、すべての言語は自然数にコーディングできます。このコーディングした自然数を二進法で{0,1}*に変換した上で、その二進法での{0,1}*のpredicateがmPかmNPかであるかという判断をすると定義しておきます。ここはちょっと難しいですが、前回と合わせてよく考えてみて下さいね。


さて、ここまでが前提としての定義ですが、もう少し、今回の証明に必要な定義を予めやっておこうと思います。

「頂点カバー、独立セット、クリーク　その１」で頂点カバーやクリークというサーキットの問題を説明し、以下、これら三つが同等でNP完全（「頂点カバー問題がNP完全であるということ　その１」～「その４」）であるという話をさせて頂いていますが、今回このうちクリーク問題を使って考えます。


【Clique k,n(G)、肯定的テストグラフ・否定的テストグラフの定義】

そこで、Clique k,n(G)を、Gはn個のノードをもつグラフで、そこにk個のノードによるクリークが存在するかを決定する問題とします。存在すればClique k,n(G)=1、しなければClique k,n(G)=0となります

また、このときn個のノードを持つグラフが肯定的テストグラフであるということを、k個のノードのクリークを持っていて、それ以外の枝を一つも持っていないとします。肯定的テストグラフであれば、すなわちClique k,n(G)=1であることは自明です。またn個のノードからk個のノードを取ってくる組み合わせですので、nCm個の肯定的テストグラフが存在します。

同様に、n個のノードを持つグラフが否定的テストグラフであるということを、n個すべてのノードに1～k-1の値のうちどれか一つを振り当て、異なった値を持つ二つの頂点だけが辺で結ばれているグラフと定義します。否定的テストグラフであれば、すなわちClique k,n(G)=0です。またn個のノードに1～k-1の値を振り当てる組み合わせは(k-1)^n通りあります。否定的テストグラフのノードに与える値の組み合わせが違ってもグラフの形が同じだという場合もありますが、これはすべて違うグラフと見なすということにします。



以上を予備的な定義としまして、他にもう少し近似サーキットの定義などもありますが、これは、次回以降、mP≠mNPを示す定理とその証明の説明の中でしていくことにします。