サーキットというグラフの計算量 その１

われながら、びっくりするぐらいがんばって書いているこのブログ。二日と経たずまた新しい記事です。どうなっちゃっているんでしょうね。しかし、これでソニーが黒字になるとか地球温暖化もびっくりして止まっちゃうとかになれば良いのですけどね。

さて、ここまで、P=NP？問題をグラフ理論の問題として扱うための方法をここまで説明してたところを、少しまとめてみたいと思います。

まず、P=NP？問題を定義する上で、ノイマン型コンピュータを数学的に扱うために考え出された概念であるチューリングマシンをを使ってクラスＰやクラスNPなど、計算量に応じた問題のクラスについて簡単に説明してきました

そのあと、クラスNPの問題を扱う上でNP完全という概念が重要であること、そして、そのNP完全な問題として、SATがNP完全な問題であること(Cookの定理)であることを述べました。以下、概要を述べると次の通りです。

• 　3SATが3SAT∝SATであることよりNP完全であること
• 　論理式がサーキットというグラフとして表されること
• 　グラフ理論の問題でVCや独立セット問題、クリーク問題が実は同等の問題であること
• 　VC∝3SATによりVCがNP完全であることを証明することにより独立セット問題やクリーク問題もNP完全な問題であること

このようにして、P=NP？問題について、グラフ理論におけるクラスNPであるVCや独立セット、クリーク問題を扱えばよいという準備ができました。

さて、以前（「サーキットというグラフ　その１、その２」）、論理式FをサーキットCというグラフで表せること、及び、論理式Fやそれを関数として考えたときの関数fにおいて、それぞれのリーフの数をL(C)やL(F)やL(f)、グラフの深さをd(C)、d(F)、d(f)などを定義したのでした。

ここでは、あと二つ、パリティ(Parity)とモノトーン(monotone)という、これからグラフ理論でP=NP?問題を扱う上で重要な概念を説明します。

まず、このような計算機の世界でパリティといえば、2進数で表される情報において、1ビット冗長な信号を付け加えて、ある2進数の情報が以前と同じく正しいかを簡易的に判断する手段と言うことになります。

具体的には、2進数の１の数を数えて、必ず、偶数か奇数になるように冗長のビットを0か1かを付け加えます。

たとえば、１００１０１という信号を送信する前ときに信号に含まれる1の数が偶数であるという約束をしているとします。そのとき、送信される信号は１００１０１１（最後の1が冗長なパリティ信号）となり、受信する方は、受信した信号の1の数を数えて偶数であればとりあえず問題なく信号が送られたということになります。

ここで数学的に定義すれば、ブール変数x1,x2,…,xnにおけるパリティをParity(x1,x2,…,xn)と表記することにすると、

　Parity(x1,x2,…,xn)=(x1+x2+…+xn) mod 2

   (※a mod bはaをbで割ったときの剰余）

と定義できます。このほか、x1,x2,…,xnのk番目のthreshold関数を（このブログでは)Th(k,n)(x1,x2,…,xn)と表すことにすると、

　　Th(k,n)(x1,x2,…,xn)=1　　iff 　x1+x2+…+xn ≧k

    (※iffは if and only if の省略形で同値を意味する）

と数学的に定義できます。

さて、もう一つ最後にモノトーン(monotone)もしくは日本語で単調という言葉をここで定義しておくと、ブール関数fが以下の性質が成り立つ場合にモノトーンであるとします。すなわち

　　　x≦y　　ならば　f(x)≦f(y)

　　　

　　ただし、x=(x1,x2,…,xn),y=(y1,y2,…,yn)で、

　　　　　　x≦yはx1≦y1∧x2≦y2∧…∧xn≦yn

　　　　　　を意味します

　

今回はこの辺りで。

頂点カバー問題がNP完全であるということ その４

 また前回から長い時間がたってしまいました。一体いつ終わるのか、私も少々疑問に思っているこのP=NP?問題を扱った連載。本当に頭の良い方々のおかげです。つまり、ほら。自分の健康問題を他人のせいにしてはいけませんが、本当に参っちゃうんですよ、いろいろと絡まれて。なんたって頭が良いうえにお育ちもよいらしいですから、その分アレでですね。私みたいな人間とは頭を下げないと口も聞いてくれないらしいですし、不幸が楽しくて仕方がないとまでおっしゃるんですから、仕方ありません、私は私なりにがんばるほかないと思っているところ。おまけに、別件で計算機理論の入門の記事をブログに書いて、もう関係ないけど、ソニー製品を買ってね、とお願いしたにも関わらず、なぜかソニーの赤字幅が増えてるらしく、私もまた及ばずながら少々何かしないといけないかと。

前置きが長い上に面白くなくてすいません。え？面白くないのはいつもだって？そ、それは言わない約束じゃないですか。

さて、気を取り直して、前回（ 「頂点カバー問題がNP完全であるということ　その１　その２　その３」） まで、3SATの問題がどのようにしてVC（頂点カバー）の問題に置き換えられるか、そして、置き換えたあとのグラフG=(V,E)がK≦|V|においてをVCの問題が3SATの問題を満たしているか解説をしてきました。

今回は、前回とは逆に、3SATの問題すなわち、リテラルの集合U={u1,u2,…,un}と節集合C={c1,c2,…,cm}が与えられた場合、真理関数t:U→{T,F}がCを充足するとした場合、3SATからVCの問題へと変換されたグラフG=(V,E)とK≦|V|で与えられるVCの問題が、節の部分集合W∈V,|W|≦KでVCであるということを述べたいと思います。

「頂点カバー問題がNP完全であるということ　その２」では、3SATの問題をVCの問題に変換する手続きを説明しました。

そこで、

　手順1.ではリテラルの集合Uを 部分グラフをTi={Vi,Ei}と表すとき

　　　　Vi={　ui,　￢ui　}
　　　　Ei={　{ui,￢ui}　}
　
と表すことにし、
　手順2．では、節の集合Cについて、部分グラフ Sj={V'j,E'j}と表し、

　　　　V'j={　a1[j],　a2[j],　a3[j]　},
　　　　E'j={　{a1[j],a2[j]},　 {a2[j], a3[j]}, 　{a3[j], a1[j]}　}
　
　　　（ただし、a1[j]∈Vかつa　[j]∈Vかつa3[j]∈V）
　　
とするのでした。

　手順3．では、以上の手順を用いて、頂点の集合Vが


と言う式で表されることを述べ、

　手順4．では、同様に枝の集合Eについて考えると、

　　　　　すべてのcj∈Cについて、cj={xj,yj,zj}と節を表すとき
　　　　　枝の部分集合を、
　　　　　　　
　　　　　　　E"j={　{a1[j],xj},　 {a2[j], yj}, 　{a3[j], zj}　}
　
　　　　　と表すことにすると、最終的には、



となり、K=n+2mと定義したのでした


さて、まず、上のViのなかから、真理関数tにおいて、真(T)になるものをVCのノードの集合Wとします。

そこで、E"jについて考えると、3SATの節cj={xj,yj,zj}が真理関数tで充足される、ということを考えると、最低でもxj,yj,zjのどれかが真理関数tにおいて真にならなければいけないということになります。したがって、E"jを満たすためには、a1[j],a2[j],a3[j]のいずれか二つがVCのノード集合Wに含まれていれば良いわけです。

ここで、|Vi|=n。また|E"j|=mより、多くてもa1[j],a2[j],a3[j]のいずれか二つが集合Wに含まれる必要があることから、2m個、すなわち、n+2m個のノードが集合Wに含まれ、K=n+2mと定義したことから|W|=Kを満たすことから、このときノード集合Wは|W|=KでのVCということを満たす、ということになるわけです。