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

さて、またどういうわけか朝からがんばっていますが、さすがに来週は台風さんの来襲も無いようで、ほっと一息ついています。もう、本当に申し訳ありません、とわけも分からぬ自責の念に駆られてしまい謝りたくなるほどの台風の襲来でありました。


さて、前回は、

を求めましたが、今回は


　　　L(Parity(x1,x2,…,x2n))≦4・L(Parity(x1,x2,…,xn))


という事から

　　　

という事を求め、合わせ技で

ということを説明します。


まず思い出して頂きたいのは、


￢Parity(x1,x2,…,xn)=1-Parity(x1,x2,…,xn)

　※厳密には￢は否定演算子で、単なる否定は式にアッパーラインが引いてあるものが正式ですがここでは区別していません


という式。これは、「サーキットというグラフの計算量　その２」で説明しているのですが、要するに結果として0と1が、1と0に反転するという岳ですので、二分木にしても大きさが変わるわけでは無いという、それだけ簡単に納得して頂ければいいわけです。二分木の図を書いても良いのですが、単にリーフ0と1の出力を逆になるように否定を取るだけ良いだけですので省略です。


　　　L(Parity(x1,x2,…,xn))＝L(￢Parity(x1,x2,…,xn)）


ここで、Parityの二分木の例を再掲しますと

Parityの二分木の例

となりますが、この図からも分りますように



　　　Parity(x1,x2,…,x2n))

　　　　　⇔[{Parity(x1,x2,…,xn)∧￢Parity(xn+1,xn+2,…,x2n)}
             ∨{￢Parity(x1,x2,…,xn)∧Parity(xn+1,xn+2,…,x2n)}]

　　　　　⇔[{Parity(x1,x2,…,xn∨Parity(xn+1,xn+2,…,x2n)}
             ∧{￢Parity(x1,x2,…,xn)∨￢Parity(xn+1,xn+2,…,x2n)}]

　　　　　　　※⇔は同値を表わす


ですので、一般的には、


　　　L(Parity(x1,x2,…,x2n))≦4・L(Parity(x1,x2,…,xn))


が言え、これをどんどん展開していくと


　　　L(Parity(x1,x2,…,x2n))≦4・L(Parity(x1,x2,…,xn))
　　　　　　　　　　　　　　　≦4・４・L(Parity(x1,x2,…,xn/2))
　　　　　　　　　　　　　………
　　　　　　　　　　　　　　　≦（ただし上の例図のようにn=2のd乗で表せるとする）


という事になります。

したがって、前回求めた


　　


と合わせて考えると

　　

という事になります。


以上で、ここでサーキットというグラフ計算量のお話はいったん終わらせて頂きます。テキストではこのあとスレッシュホールド関数の計算量の話が少し出てきているのですが、詳しいことは分っていないということで、Krapchenkoの定理を利用して分っている範囲での事に少し触れてありますが、省略したいと思います。基本的にはどういうことをやっているのか、ということをここでは理解して頂ければ十分だと思うからです。興味のある方は、個別に私宛にご連絡頂ければ、ご相談に応じることはやぶさかではありません。



次回からは「このブログを再開するに当たってのこれからの進め方」の回でお話ししている、


　２－２．サーキットの計算量の様々なクラスを考察する


という事に入っていこうと思います。そのあと


　２－３．ユニフォームという概念


ということを説明し、

　　３．モノトーン（否定のリテラルがない論理式）のサーキットが

　　　　多項式時間以内で解けない問題であることを証明する

というところで、再びサーキット（この場合はモノトーンサーキットになりますが）の計算量に関してはじっくり考察することになります。

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

今日も今日とて早朝からがんばっていますが、何となく台風上陸との報に罪悪感を感じてしまう私。関係ないのは分っているのですが。と、とにかく、被害の無いことをお祈りするのみです。


前回はKhrapchenkoの定理の証明を証明しました。今回はこれを用いて、以下の命題を証明するということの説明を行います。






まず、AとBとが２値0か1を元とし、n個の元を持つ集合{0,1}^nの互いに素な部分集合だったという事を思い出して下さい。さらに、今回は以下のようにその互いに素な集合を定義すると

　A={(x1,x2,…,xn)|Parity(x1,x2,…,xn)|=0}
　B={(x1,x2,…,xn)|Parity(x1,x2,…,xn)|=1}

論理式parity(x1,x2,…,xn)が集合Aと集合Bを分離しているのは明らかです。また、

　

　　　 　　　　　　　　※AとBの元はそれぞれのnビット。
　　　　　　　　　　　　　ゆえににAとBの1ビットの差異は
　　　　　　　　　　　　　
　　　　　　　　　　　　　n個×（集合A(もしくはB)の元の個数）


なので、これをKhrapchenkoの定理

に代入してやると求める命題

が出てくるということになります。


意外と簡単に出てくるものですね。頭のいい人の考えることは本当に違いますねえ。

さて、次は

　　　L(Parity(x1,x2,…,x2n)|)≦4・L(Parityx1,x2,…,xn))

という事から

　　　L(Parityx1,x2,…,xn))≦(nの2乗)

という事を求め、今回求めた

　　　L(Parityx1,x2,…,xn))≧(nの2乗)

と合わせ技で

　　　L(Parityx1,x2,…,xn))＝(nの2乗)

ということを説明します。(nの2乗)を




としなかったのは単に説明上の都合です。面倒だからじゃ無いですってば。

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

秋になって、どういうわけかやる気が起こってきたのか、何となくがんばっている私。この時期になっても台風がいくつも来るわけだ、と個人的には納得してはいけないことも納得してしまいそうな今日この頃。皆様はなんの秋でいらっしゃいますでしょうか。

そういうわけで、ってどういうわけか知りませんが、最近早朝からがんばっている私。しかし、このブログ誰が読んでいるんでしょうねって自分でいったらいけないか。

今回はKhrapchenkoの定理の証明ですね。注意しておきますと、これは、パリティのリーフの数を計算すつと言うよりもう少し一般的な定理になり、この定理からパリティのリーフが求まるという順序になります。

再掲すると、

AとBとが集合{0，1}^n（0と1の元をn個持つ集合）の互いに素な部分集合だとするとき論理関数FがAとBとを分離することを、Aに対してはFが0、Bに対してはFが1となることと定義する。また、このようなとき、以下のことを定義していると、


つぎの式が成り立つ、

　　

という事でした。


以下証明です。

【Khrapchenkoの定理の証明】

数学的帰納法により次のように証明していきます。

上の式が成り立つと仮定します。


(i)　L(F)（リーフ）が1のとき
　まずL(F)=1のときの例としてF(x1,x2,…,xn)=x1となるような式を考えます。このときa～bという式は、仮にa=(0,a2,…,an)であるならばb=(1,a2,…,an)であるという事と同等になります。したがって以下のことが言えることとなり、

が成立。少し変形し、二つの式をお互いに掛け合わせれば容易に、

が導けます。


(ii)L(F)>1のとき
　F=F1∧F2とします。このときA1とA2とを次の式で定義することにします。
　
   　A1={a∈A|F1(a)=0},　　　A2=A-A1

すなわち、A1を論理関数F1でBから分離できるものだけにする、ということです。これをi回繰り返してみるとFiによってAiはBから分離できるということになり、帰納法の仮定より

という式が導き出せます。さらに、F=F1∧F2でしたからL(F)=L(F1)+L(F2)が成り立ちますから、

となります。ところで、

であることから

という式が成立することに。これは右辺が定理の右辺に相当しますから（左辺は定理の左辺より当然小さい）、従って数学的帰納法により、Khrapchenkoの定理が証明されました。上の式を変形するとこの式が成り立つことが分ります。つまり、上の式をひらめいたことがこの定理のキモということになるわけですよね。


というわけで次回は、Khrapchenkoの定理から

　　L(Parity(x1,…,xn))≧(nの2乗）

という式を証明します。上の式で(nの2乗）としてきちんと式を図にして表示していないのは、今回関係ないところだったからで、次はきちんとします。単に面倒だったから、とかそう言うわけではありません。多分………。

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

いろいろあって、半年に一本というペースに落ちてきていますが、誰かのせいです。どいつだー。いえ、すべて私のせいなんですが。人間誰しも自分が悪すぎて恥ずかしいときには他人のせいにしたくなりますよね。特に怖い人の前では。幸い私には奥さんがいませんけれども、私の怖い人にはいらっしゃるだろうということで、やはり奥さんは大切にしないといけません。

えっと、なんだか訳が分らなくなってきましたが、話しを続けさせて頂こうと思います。

今回からしばらくは、パリティを計算するようなグラフが持つリーフの数L(Parity)についてお話しします。パリティの基本的な性質をグラフの計算量の例としてて説明するということが主な目的です。これが分ると自然と深さd(Parity)も分ります。

まず、パリティを計算する場合の論理式Fをグラフにしたものの例を下に示します。ブール変数はx1,x2,x3,x4の4ビットですが、リーフL(F)=16,深さd(F)=4となっています。ここからしばらくは、このようなグラフのリーフの数L(parity)の求め方を説明します。

図　 parity関数の例

ちなみにこういうグラフの形を二分木と呼んだりもします。そして一番上のノードを根（root）と呼びます。根からリーフまですべてのノードは下のノードからインプットとして二つの枝を持ちます。そのため二分木と呼ばれるわけです。このようなグラフの深さは必ずd=logL(F)（ただし対数の底は2）となることは自明ですね。ちなみに計算機科学などの計算機を扱う分野では対数の底は特に断らない限り2です。これは計算機の世界が基本的に2進数で物事を表現することが基本だからです。ここでも特に断らない限り以下、対数の底は2ですのでご注意下さい。

今回はまず、準備として以下のことを定義しておきます。

元が0と1からなり、n個の元を持つ集合を{0,1}^nと表記することにします。この集合｛0,1}^nの部分集合で互いに素である二つの集合ＡとＢを論理式Ｆが分離するという事を定義して、FがＡの元に対しては0、Ｂの元に対しては1を取るという事にします。

また、部分集合ＡとＢに対して以下のことを定義します。

このあとはKhrapchenkoの定理と呼ばれる次の不等式を帰納法で証明します。それは次回に。できる方は自分で証明を考えてみると面白いかもしれません。

           

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

前回とは一転、またまた長く間が相手しまい申し訳ありません。どうしてこうなのでしょうか。亀の呪いでもかかっているかのようです。扱っているいる問題がむずかしすぎですよね、まったく。しかし、千里の道も一歩から。少しずつがんばっていきたいと思います。

さて前回の復習ですが、パリティを定義して

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

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

としました。前回言及しなかったのですが、このとき、パリティはブール関数として表されることから、このパリティの否定も定義でき、次のようにすることにします

　￢Parity(x1,x2,…,xn)=1-Parity(x1,x2,…,xn)

また、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

　　　　　　を意味します

　

が成り立つこととしました。

今回は、単調なブール関数f(x1,x2,…,xn)のmintermとmaxtermという言葉を定義したあと、min(f),Max(f)という集合の表記について説明します。以下、繰り返しになりますが、単調なブール関数f(x1,x2,…,xn)において成り立つと考えてください。

まず、mintermから。あるブール代数の集合｛xi1,xi2,…,xik｝(※変数の最後の添え字がkであることに注意。すなわち1≦i≦ｎで1≦k≦n）が単調なブール関数fのmintermという場合、xi1=1,xi2=1,…,xik=1のときのみf=1がなりたつこと。言い方をもっと数学らしくすると、xi1=1,xi2=1,…,xik=1のときのみf=1であり、これらの変数のどんな真部分集合を取ってきてその値をすべて1にしてもf=1とはならない、と定義します。

つぎに、maxterm。あるブール代数の集合｛xi1,xi2,…,xik｝が単調なブール関数fのmaxtermという場合、xi1=0,xi2=,0…,xik=0のときのみf=0であり、これらの変数のどんな真部分集合を取ってきてその値をすべて0にしてもf=0とはならない、と定義します。

こうしておいて、関数fのすべてのmintermの集合をmin(f)、すべてのmaxtermの集合をMax(f)とします。

こうしたときに、次のことが成り立ちます。すなわち、p∈min(f),q∈Max(f)のとき

　　

　　　p∩q≠Φ

テキストでは自明のごとく書いてありますが、これは一般に、mintermが成立するとは、ブール関数fの一部がxi1∧xi2∧…∧xik=1を含むことと同等と考えることが可能で、maxtermが成立するとは、ブール関数fが一部がxi1∨xi2∨…∨xik=0を含むことと同等だと考えると一見成立しないように思われますが、mintemがxi1のみmaxtemもxi1のみと言う場合も当然あるために上の式は成立するということだと思われます。

さて、最後に単調な論理式について少しふれておこうと思います。論理式Fに否定のリラテルすなわち、￢xのような形のブール変数を含まないような論理式を単調な論理式といいます。単調な論理式Fから表せるブール関数fは単調になり、また逆に単調なブール関数は単調な論理式によって表すことができます。

とりあえず、今回はここまでにしておきます。かなりヤヤコシイのですが、あとは、どうか誰か読んでくださいますように、お祈りするのみです。

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

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

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

　　　　　　を意味します

　

今回はこの辺りで。