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

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

さて、ここまで、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

　　　　　　を意味します

　

今回はこの辺りで。