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

前回まで、簡単にグラフ理論にふれ、サーキットというグラフについて定義しました。今回はもう少しだけ詳しく説明し、そのほかの用語の解説の続きを行います。
　
ところで、ここまでこのブログではいろいろなアメリカのＩＴ企業との関連について（少し無理矢理）触れてきましたが、グラフ理論といえばグーグル。Web上のページをノード、リンクを枝とみなし、インデグリーの数から割り出した順位を、ベージランクと名付けて検索結果における重要度と見なすというのが、基本的なアルゴリズムというのは有名です。私でも知ってますし。そういえば、前回、枝をリンク（link）とも言うと説明しましたね。ちなみにページランクというのは、グーグルの創業者のラリー・ページさんの名前と掛けてあるそうです。ググると分かります。

　

さて、ググってもなかなか出てこない私のブログですが、お話を続けましょう。とほほ。

　

気を取り直して、もう一度サーキットの定義を再掲しましょう。

　

【サーキットの定義】
　いま、ブール変数x1 , … , xnが与えられているとします。グラフは、無サイクルな有方向グラフであり、
　　
　　（１）すべてのノードのインデグリーは0、もしくは、2である
　　　　（１－１）インデグリー0のノードをインプットもしくはリーフと呼ぶ
　　　　　　　　　（一般に、入力であるブール変数x1 , … , xn が相当する）
　　　　（１－２）インデグリー2のノードはゲート（gate）と呼ばれ
　　　　　　　　　∧（論理積）もしくは∨（論理和）が付加されている
　　（２）アウトデグリーの値は任意であるが、アウトデグリー0のノードが
　　　　　ただ一つだけあり、このノードのことをアウトプット(output)と呼ぶ
　
以上を満たすものをこれから、ブール変数x1 , … , xn上のブーリアン・サーキット（Boolean circuit）または、単にサーキットと呼ぶことにする、のでした。
　
ここで、いくつか例を挙げておきましょう。図1は以前「このブログを再開するに当たってのこれからの進め方」でサーキットの例として挙げた図です。インデグリーが２ではないものもありますが、これは、たとえば、図２のようにインデグリー２のグラフに変形できます（ここでは特に節の中（∨で結ばれたもの）だけを変形）。しかし、意味的には元のSAT形式を論理式として考えたときの式と同じでも、直感的な把握は図１の方が勝りますよね。というわけで、実際にはインデグリー２ではなくても意味的にインデグリー２のグラフにできるものも含めて以下サーキットと呼ぶことにします。

　
もう少しだけ、専門用語をお話しして一旦サーキットについての説明を終わりたいと思います。少し予定から先走りしている感じもありますし。
　
まず、論理式Ｆのリーフの数を定義してL(Ｆ)と表すことにします。サーキットＣではL(Ｃ)とも表すことができるのでしょうが、テキストではそこまでは触れていません。また、サーキットの縦の大きさ、これを深さ（depth)と呼びます。またサーキットＣのアウトプットからリーフまでの最大の段数と定義し、d(C)と表します。論理式Fに対しても同じようにd(F)と表わします。ここで、例を挙げるとサーキットで見ると図1と図2では意味的には同じ訳ですが、グラフの形（専門用語ではトポロジーとも言ったりしますが）がちがうわけで、それぞれのグラフの最大の深さをそれぞれ、d(C)=3、d(C)=4と表わすということになるのでちょっと注意が必要です。
　
え？論理式の深さd(F)ですか、さ、3じゃないですか、図１も図２もどちらも同じ論理式ですしね……

じ、実は、この後、論理式やサーキットを、ブール変数 x1 , … , xn から０か１かを与える（ブール）関数fと考えて、fと同じ値を返す論理式Ｆの中で最小のd(F)の値をd(f)とするという定義があるのです……。忘れてました。また、同様にリーフの数L(f)も同様に最小のL(F)の値とするというのがあるのです。随分と面倒ですよね。

グラフ理論についての簡単なお話

私が、電子工学出身と言うこともあり、グラフ理論においての用語は、そちら方面のいわゆる方言を用いているので、元々の数学をご専門とされている方にはなかなかわかりにくいかもしれません。それに、グラフ理論で閉路をサーキットという場合もあるようで、このブログで用いているブーリアン・サーキットと言葉が同じでも全く違った意味で使っているということになっています。

そこでWikipediaの記事をいくつか参考にしながら、標準的なグラフ理論に関しても少しだけ説明させていただきたいと思います（参考文献やそのリンクはその都度示すことにしますが、それ以外にも参考にしたものはこの記事の末尾に示します）

グラフ理論というのは、もともとは、一筆書きから出発したと言われています。その一筆書きにも原点がありまして、１８世紀、プロイセン王国の首都であったケーニヒスベルグに流れる大きな川に架かる７つの橋を同じ橋は二度通らずに一度にすべて渡れるか、という問題に端を発しているようです。これを、オイラーという人が、橋を辺、橋と橋を結ぶ部分を頂点と見なして、一筆書きという形で洗練させて、数学的に解方を示した、ということが元になっているようです（http://ja.m.wikipedia.org/wiki/一筆書き）

このあと、それが位相幾何学として発展していったために、頂点と辺という言葉が数学で一般的に使われるようになったものと思われます（http://ja.m.wikipedia.org/wiki/位相幾何学）

位相幾何学とは、簡単にいうと、すべての図形を点と線だけで分類しよう、という数学の分野です。たとえば、我々が平面に正三角形を書きます。そのとき、一つの角の大きさは６０度です。しかし、地球上にものすごく大きな正三角形を書いたとしたらどうでしょう。地球は球体なので、この正三角形の一つの角度は６０度を超えてしまいます。このように、われわれの正三角形の概念は、実は非常に曖昧です。そこで、点と線の数と結びつき方だけで、図形を分類して性質や特徴について調べようという考え方を発展させていったものが位相幾何学というものなのです。

参考；http://ja.m.wikipedia.org/wiki/グラフ理論

サーキットというグラフ その1

ここからは論理式をグラフとして扱う方法についてしばらく述べます。まじめに、やります。
　
さて、まず、グラフということについて簡単な説明をしましょう。
　
数学には、点と点をつないでその構造を扱う分野があり、かなり大きな一分野として確立されています。それをグラフ理論という呼び方をするわけですが、グラフというのは 、この点と点を線でつないだもの、と考えて下さい。そして、もう少し学問らしくしかめっ面をしながら格好を付けて、グラフの点のことを、「頂点」もしくは「接点」あるいは英語で「ノード（node）」という言い方をし、頂点同士をつなぐ線のことを「辺」もしくは「枝」あるいは英語では「エッジ（edge）」、「アーク（arc）」、「リンク（link）」などと呼びます。
　
呼び方がたくさんあるのは、数学にもいろいろな分野があり、また、広く、コンピュータ科学やその他の工学などにも応用、利用されているため、それぞれの専門分野に適した呼び名がされています。このブログでは、点を「接点」もしくは「ノード」、線を「枝」もしくは「エッジ」と呼ぶことにします。理由は、単に、私がそれに慣れているから、です。ちなみに、一般的な数学での標準的な呼び方は、「頂点」と「辺」のようです。だいたいそう書いてあります。
　
さて、グラフには、枝に向きがあるかないかで、大きく二つに分けることができます。枝に向きがある物を有方向グラフと言い、無グラフを無方向グラフと言います。はい、退屈ですね。良く分かります。しばらく退屈ですから寝てても良いですよ。ええ、私も眠たいですし。
　
では、ここからしばらくは、有方向グラフについて、いろいろな専門用語の定義です。まず、ノードv1からノードv2を結ぶ有方向の枝のことを、

　

　
という書き方をします。このほかの専門用語の解説です。
　
・サイクル（cycle）のあるグラフ
いくつかのノードを一周回るような枝のつなぎ方になっている場合をサイクルがあると言います
　
・無サイクル（acycle）グラフ
　サイクルがないようなグラフを無サイクル（acycle）なグラフと言います
　
・インデグリー（in degree）とアウトデグリー(out degree)
　無サイクルのグラフに限定した話になりますが、あるノードvに注目したとき、いくつの枝が入ってきているかをインデグリー（in degree）、いくつの枝が出て行っているかをアウトデグリー（out degree）と呼びます（下図参照）
　　

ここまで来てようやくサーキットというグラフについて説明となります。

サーキットという言葉には、もともとにはいろいろな意味があるようですが、ここではおそらく電子回路（それも、一つの伝線はオンかオフしかないデジタル回路）を指していると思われます。

つまり、サーキットというグラフは、デジタル回路を数学的に扱うためのグラフの一つと思えばいいわけです。サーキットの狼というマンガを知っている人は、おそらく私と同年代ですが、サーキット違いですのでロータス・ヨーロッパなどを想像しないように。
　
さて、そうなると、入力は当然0か1、あるいはT(True)かF(Flase)で考えることができます。すなわち、Bool代数の出番ということです。
　
Bool代数で使う専門用語を再掲しておくと、x1 ,…, xn をブール変数と呼び0（Ｆ）か1（Ｔ）のどちらかしかとりません。またこのブログでは、￢xiを便宜上ブール変数xiの否定と同等と扱い、ブール変数xiや￢xiと書かれたものを、リテラル、と呼んだりもするのでした。

では、いよいよサーキットというグラフについての定義をきちんとしましょう。基本的にやっているのは数学ですからね。定義は大事です。
　
【サーキットの定義】
　いま、ブール変数x1 , … , xnが与えられているとします。グラフは、無サイクルな有方向グラフであり、
　　
　　（１）すべてのノードのインデグリーは0、もしくは、2である
　　　　（１－１）インデグリー0のノードをインプットもしくはリーフと呼ぶ
　　　　　　　　　（一般に、入力であるブール変数x1 ,…, xn が相当する）
　　　　（１－２）インデグリー2のノードはゲート（gate）と呼ばれ
　　　　　　　　　∧（論理積）もしくは∨（論理和）が付加されている
　　（２）アウトデグリーの値は任意であるが、アウトデグリー0のノードが
　　　　　ただ一つだけあり、このノードのことをアウトプット(output)と呼ぶ
　
以上を満たすものをこれから、ブール変数x1 ,…, xn 上のブーリアン・サーキット（Boolean circuit）または、単にサーキットと呼ぶことにします。


少し話が長くなりました。もう少しだけ用語の定義がありますが、これは次回にしましょう。

３SAT その３

今回は3SATの三回目の説明です。できれば、今回で終わりにしたいので、それこそ、さんさんさっと済ませたいですね。はい、またも駄洒落です。予告通りですよね？今回は結構大変なので、余裕がないんです。いつにもまして、つまらないのはそのせいです。多分………。

さて、前回（３SAT　その２）は、

SAT∝3SAT

となるように、SATのブール変数の集合Uと節集合Cから３SATのブール変数U'と節集合C'

とする時に、節C'jの要素の数｜C'j｜が必ず3になるような変換を一通り説明したのですが、前回Cjの要素の数kが3より大きい時の証明が残っていました。もう一度その変換式を見てみると、

k＞3のとき（再掲）

でした。これが、Cjを論理式にした式、

　z1∨z2∨…∨zk　　　　　（１）

と等しくなるという事を証明する、というのが今回の説明の趣旨です。

さて、第一段階として、ある論理式、（例えば、ここでは上記式（１））を真とするような関数tを真理関数という言い方をします。ここでは、C'jのすべての節が真になるということを満たす真理関数t'をC'jをの各節ごとに求めていきます。

もう少しだけ説明を加えると、たとえば、真理関数t=z1∨z2は、t=Tであれば、上記式（１）を真にしますね。そのような真理関数tがあったとして、求めるべき、C'jのすべての節が真になるということを満たす真理関数t'、というのは、一般的に次のように場合分けして定義すればいいことになります。

１）t(z1)またはt(z2)が真

とする。

※注）これは、上記C'jを構成する式の第一項部分

に相当します。

２）t(zk-1)またはt(zk)が真

とする。

※注）これは、上記C'jを構成する式の第三項部分

に相当します。

３）3≦l≦k-2なるlについてt(zl)が真

とする。

※注）これは、上記C'jを構成する式の第二項部分

に相当します。

第二段階では、このように定義したあと、逆に、このC'jを真とするような真理関数t'があったときに、これが、論理式（１）と等しくなるかどうかを見ていきます。

なかなか、さんさんさっとっとは行かないですね。ちなみに、九州のある地方では、「この席は私が取ってるの」、というのは方言で、「こん席は私がとっとっと」、と言います。「窓からすきま風が入ってきてすーすーする」というのは、「すーすーすー」です。はい、どうでもいいですね。では、もう少しがんばろうと思います。

さて、C'jをそのまま論理式に書き換えると、次のようになります。

￢A∨B=A⊃Bという事より上の式は次のように書き換えられ、

充足問題では、上の式の最初の部分が、

　　

と書き換える事ができるので、これを最後まで繰り返すと、

　z1∨z2∨…∨zk　　　　

が出てくる事になります。

したがって、第二段階の結論としてはこのC'jを真とするような真理関数t'の真理変数をz1,z2,…,zkに制限したものをtとすれば、tは式（１）を満たす真理関数と言う事になります。

さて、全体を振り返れば、SATから3SATへの変形の手順は、多項式時間以内で終了する事は明らかですから、

SAT∝3SAT

つまり、3SATはNP-完全であることが証明されました。

参考文献：「PとNP」竹内外史　日本評論社  p.15-p.17

３SAT その２

今回は3SATの説明の二回目です。さんさっと済ませたいですね。はい、前回も言いましたね、この駄洒落。あと一回ぐらいこれで引っ張るつもりなのは内緒です。

さて、前回、

SAT∝3SAT

となるように、SATのブール変数の集合Uと節集合Cから３SATのブール変数U'と節集合C'を以下のように求めるという話をしました。

この時、節C'jの要素の数｜C'j｜が必ず3になるような変換を求めるのでした。前回Cjの要素の数kが1のときと、3のときを例として説明しましたが、今回はそれらを含めてすべての場合の変換に関して説明します。

k=1のとき（再掲）

という具合になります。C'jを論理式で書くと、

ですので、U'jの要素の値に拘わらず集合Ujの要素であるブール変数z1の値のみでC'jの値が決定されるという事が分かると思います。

k=2のとき

となります。k=1の時と同様にC'jを論理式で書くと、

となり、同じく集合Ujの要素であるブール変数z1,z2によってのみC'jの値が決定される事が分かります。

k=3のとき（再掲）

Cjの要素数が3すなわちk=3のときは、そのまま３SATとして使えますので、

U'j=φ(空集合),  C'j=Cj

となります。

k＞3のとき

※クリックすると拡大されます

という具合になります。これが、Cjを論理式にした式、

　z1∨z2∨…∨zk

と等しいという証明は意外にややこしいので、次回（リンクの予定）に説明させて頂きます。あまり難しくはないので、自分で解いてみたいという人は是非やってみて下さいね。

参考文献：「PとNP」竹内外史　日本評論社  p.15-p.17

３SAT その１

今回は3SATを説明します。さんさっと済ませたいですね。はい、駄洒落です。予想通りですね。

3SATから頂点カバーまでがNP-完全という証明は、これもCook先生が証明したものです。素晴らしいですよね、私の駄洒落とは反比例するかのように………。

さて、３SATは、SAT形式で表わす論理式、SATで言えば節の集合ですが、これの各節の長さが必ず3になるような、節集合Cを３SATと呼びます。数式で書けば、

　C={c1,c2,c3,...,cm}

と表わす時に、

　　|ci|=3　｛1≦i≦m}

となる形式の節の充足問題を3SATと呼びます。

これが、NP-完全であると証明する事という事が今回の記事の目的です。

そのためには、SATがNP-完全である事から、

SAT∝3SAT

を証明すればいいわけです。すなわち、3SATがSATへ多項式時間以内で変換できればそれで証明は完了となります。

さて、充足問題　その１　で説明しましたが、SATにでてくる、n個のブール変数の集合U=｛u1,u2,…,un｝とし、節集合C=｛c1,c2,…,cm｝とします。

このSATのUとCを使って、３SATに同様なU’とC’を作り、Cが充足されれば、同様にC’も充足されるという事を証明するというのが今回の証明の手順になります。

まず、U’とC’は次の式で表わす事ができます。

つまり、このUj’とCj’をうまく作って、Cが充足するようにすれば良いと言う事になります。Cは、

で表わされますが、もちろん、各Cjの要素の数｜Cj｜は3に限りませんので、Cj={z1,z2,z3,...,zk}（ziは集合Uのブール変数の要素）と表せるとき、kの値で場合分けして、各Uj’，Cj’を決める事になります。ややこしいですね。

とりあえず、構成がどうなるかは次回説明するにしても、例として、k=3のときとk=1というのを見てみましょう。

まず、Cjの要素数が3すなわちk=3のときは、そのまま３SATとして使えますので、

　U’j=φ(空集合), C’j=Cj

となりますね。

では、Cjの要素数が1のときはどうなるかというと、実はこちらの方がややこしくて、

　　

という具合になります。C’jを論理式で書くと、

　

ですので、U’jの要素の値に拘わらず集合Ujの要素であるブール変数z1の値のみでC’jの値が決定されるという事が分かると思います。

参考文献：「PとNP」竹内外史　日本評論社 p.15-p.17

このブログを再開するに当たってのこれからの進め方

お久しぶりです。以前、Cookの定理を説明してから随分経ちました。いろいろありましたが、ようやくこの「P=NP?問題についての覚え書き」を再開する事ができそうです。もっとも、私の能力不足のせいなので本当に読者の皆様にはご迷惑をおかけして申し訳ありませんでした。まずは、お詫びを申し上げます。

再開するに当たって、これからの進め方について、まず一通り説明していきたいと思っています。

ここまで、P=NP?問題はNP完全な問題であるSATが多項式時間で解けるか？という問題に帰着できる事を説明してきました。

あ、そこ、もう眠くなってませんか？だめですよ。もう面白い事言わないつもりなんでがんばって下さいね。

で、何言ってたんでしたっけ？というギャクはもう使ったっけ？あ、そうですね、先進めなきゃ。

いやね、私だって、逃避したくな、あ、ダメ、痛い、やめて.........

おっほん。

で、では、先に進めましょう。

これからの事に必要な分だけ、これまでの復習を簡単にすると、一般的にある論理式が答えを持つかどうか、という問題がNP完全であるということは、充足問題（SAT)として与えられ、Cookの定理によってSATがNP完全と言う事から、NP完全であるという事が証明されました。

それで、先にも述べたように一般的な論理式が多項式時間で解ける事が分かれば、それはすなわちクラスPということなので、P=NPという事が証明されます。逆に、多項式時間で解けないことが証明されれば、P≠NPという事が分かるわけです。これが、P=NP?問題のごく大まかな証明の流れになります。

ところで、一般的な論理式は、この分野では『サーキット』と呼ばれる、グラフ（この場合特に木構造）として表せる事は何となく分かりますよね？たとえば、下に例を挙げておきました。

こうして、すなわち、ある複雑な論理式を表わしたサーキットが、多項式時間で解ける近似解を持ち、その近似解から正解までたどり着くまでの時間も多項式時間であるならば、そのサーキットは多項式時間で解けるという事になります、よね？

このことが一般的に言えれば、P=NPという事が証明されたと言う事になるわけです。

というわけで、これからの説明の流れとしては、大きく次のようになると現在のところ考えています。

１．一般的なサーキットがNP完全である事を証明する

　１－１.　サーキットがNP完全である事を証明するためにSATを変形した３SATがNP完全である事を証明する

　１－２.　一般的なサーキットの問題のうちVC（頂点カバー）問題、独立セット問題、

クリーク(clique)の問題が本質的に同じ問題である事を示す

　１－３.　上記の三つの問題のうちVC問題がNP完全ということ３SATを使って示す

２．一般的なサーキットの計算量を求める

　２－１.　論理式がサーキットで表せる事を示す

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

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

３．モノトーン（否定のリテラルがない論理式）のサーキットが多項式時間以内で解けない問題である事を証明する

３．を不思議に思われると思いますが、否定のリテラルがあると複雑な論理式の計算量が減る場合があるのです。なので、否定のリテラルないサーキットの計算量をまず計算するわけですが、これはすでに多項式時間以内で解けない問題である事が分かっています。このブログのゴールはそこです。

でも、ちょっと私が考えた否定のリテラルがどれくらい計算量を減らすかっていう事も説明するかもしれません。さて、どうなるんでしょうか。私自身も少々不安ですが、これからまた、がんばっていきますので宜しくお願いいたします。