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

おはようございます。今日から新章に入ります。そう言えば新米の季節ですね。おいしい新米。うれしい新米。楽しい新米。まだまだ新米（？）の私ですが宜しくお願いいたします。ちょっと嘘が入ってますかね。ええ、分っています。新米ってほどでもないって事ですよね。


さて、この章ではモノトーンのサーキットを検討していきます。思い出して頂きたいのですがこの章で言うモノトーンは「サーキットというグラフの計算量　その１」などで出てきていて、

　　　x≦y　　ならば　f(x)≦f(y)
　　　
　　ただし、x=(x1,x2,…,xn),y=(y1,y2,…,yn)で、
　　　　　　x≦yはx1≦y1∧x2≦y2∧…∧xn≦yn
　　　　　　を意味します
　
となっています。

では、本題に入り、まず今回と次回は定義をいくつか述べます。今回はモントーンな関数fや言語L、そしてクラスPの表記の一種predicate Pのモノトーンについて定義します。ただし、この章でも特に断らない限り^はべき乗を表わす二項演算子であるとします。

【モノトーンな関数ｆや言語Ｌやpredicate Pの表記によるモノトーンなクラスPの定義】

　ブール関数fがf:{0,1}^n→{0,1}、即ちこれをn個の二進数の元を持つ集合から0か1かへの2値への写像であるとする場合、fを言語

　　L={x|x∈{0,1}^nでf(x)=1}

で表わすこととします。また同時にfをクラスPのブール変数x1,x2,…,xnのpredicate P（predicateは日本語で述語の意味）とい表記の仕方で表わすときは

　P(x1,x2,…,xn)　iff　f(x1,x2,…,xn)=1

という定義になります。

さて、fがモノトーンであるとします。このとき、Ｌやpredicate Pもモノトーンとなります。

すなわち、Lのモノトーンとは

　(x1,x2,…,xn)∈L,(x1,x2,…,xn)≦(y1,y2,…,yn)→ (y1,y2,…,yn)∈L

となります。同様にpredicate Pがモノトーンであるということは

 P(x1,x2,…,xn),(x1,x2,…,xn)≦(y1,y2,…,yn)→ P(y1,y2,…,yn)
　
が成立するということです。ちょっとややこしいので今回はとりあえずここまでにしましょう。