３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を使って示す

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

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

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

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

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

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

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

Cookの定理 その8

それでは、Cookの定理、手続き２の7回目です。

さて、前回から、なんとチリの鉱山事故の救出劇で33人全員が救出されるというすばらしいニュースがありました。（執筆当時：今回はこの記事を再掲し始めてここまで東北・関東大震災一週間を迎えました）時間というのは、ちゃんと把握してるようで、なんだか夢を見ているような、そんな感覚ですね。そして、このCookの定理の説明もようやく最後の回を迎えました。

では、そろそろCookの定理の説明ですけど、NTMをSATに変換する項目G6の説明の続きです。

G6は簡単に言うと、マシンMLのi番目の状態をi+1番目の状態へ遷移する状態遷移関数δについてということになるでしょう。前回は、ヘッドのないテープのi+1番目の状態はi番目の状態と同じ、ということについて説明しました。残りは、i+1番目のヘッド、ヘッドのある部分のテープの状態、およびマシンの状態です。

これは、もういちど、状態遷移関数の定義（NTMの数理モデルとクラスPとNPの違いの回を参照）から、論理式でまず考えてみましょう。でも、更にその前に、論理式を考える前に、文章で、この問題を考えてみることにします。われわれの思考をまずはっきりさせとかないとですね。

では、ヘッドのある場所で、i番目の状態からi+1番目の状態で変化するのは、ヘッドの位置、マシンの状態、テープの状態を表わす、ブール変数、H[i,j],Q[i,k],S[i,j,l]はすべて変化するでしょう。つまり、ヘッドの位置jはj+Δとなり、そのときのマシンの状態はqkからqk’へと変化し、テープの状態slはsl’と変化します。では、前回やったA⇒Bという論理式を使って、この状態遷移を考えてみるとどうなるか？そう難しくないので、自分で考えたい人は、以下を見ないでしばらく自分で考えても良いと思います。

さて、まず、問題になるのは、前提条件Aの部分ですね。結論となるBの方はそのまま表わせばいいでしょう。ここはちょっと迷うところですが、要するに、すべての条件がそろっていることを、それぞれのブール変数でその状態遷移を別々の論理式で書けば良いという分かったような分からないような日本語を論理式として表わすと次のようになります。

H[i,j]∧Q[i,k]∧S[i,j,k]⇒H[i+1,j+Δ]　

H[i,j]∧Q[i,k]∧S[i,j,k]⇒Q[i+1,k’]

H[i,j]∧Q[i,k]∧S[i,j,k]⇒S[i+1,j,l]

0≦i≦p(n),　-p(n)≦j≦p(n)+1,　0≦k≦r,　0≦l≦ν

テープのj番地の状態が変わることだけに注意すればこの論理式もそう問題なく分かると思います。H[i,j]∧Q[i,k]∧S[i,j,k]という条件とはブール変数H[i,j],Q[i,k],S[i,j,k]がすべてTのとき、という意味ですよね。このときに、それぞれが、H[i+1,j+Δ],Q[i+1,k’],S[i+1,j,l]へと状態遷移するという意味です。

SATへ変形するには、これを、論理式ORで結ぶように変形すると良いのでした。一つだけやれば、後は同様ですからH[i,j]の部分だけやると、

H[i,j]∧Q[i,k]∧S[i,j,k]⇒H[i+1,j+Δ]

＝￢(H[i,j]∧Q[i,k]∧S[i,j,k])∨H[i+1,j+Δ]

＝￢H[i,j]∨￢Q[i,k]∨￢S[i,j,k]∨H[i+1,j+Δ]　（ド・モルガンの法則を用いてます）

というわけで、最終的には以下のような三つのSATの形式に直せるわけです。

{￢H[i,j],￢Q[i,k],￢S[i,j,k],H[i+1,j+Δ]}　

{￢H[i,j],￢Q[i,k],￢S[i,j,k],Q[i+1,k’]}　

{￢H[i,j],￢Q[i,k],￢S[i,j,k],S[i+1,j,l]}　

0≦i≦p(n),　-p(n)≦j≦p(n)+1,　0≦k≦r,　0≦l≦ν

となります。

あとは、このマシンMLが結論qy,もしくはqnを出すまでの計算中は、

δ(qk,ql)=(qk’,sl’,Δ)

でqk’,sl’,Δが表わされ、結論が出た場合つまりqk∈{qy,qn}のときは、

qk＝qk’,sl＝sl’,Δ＝0

となるわけです。

これで、NTMをSAT変換するG1～G6のすべての説明が終わりました。最終的には節C＝G1∪G2∪G3∪G4∪G5∪G6というSATがプログラムMLが入力xを受容する計算になっているということになります。あとは、この変換が多項式時間内に終わる、ということがNP完全の条件ですが、それぞれのステップが数回であることと、入力xの長さがn、プログラムMLの長さ有限で固定されている（つまり定数）、プログラムの状態遷移のステップ数も最大でp(n)であるなどを考えると、多項式時間でこの変換は済むという事は自明ですので、Cookの定理は証明されたということになります。

今回は、ちょっとだけ内容が濃いかったですけどどうだったでしょうか。わたしのここまでついてきて頂いたことに本当に感謝します。また、こっそり誤りを指摘して頂いた米国PBSのかたがた、ありがとうございました。こっそり修正しました。もしかして、もしかするとですか？いや、考えないようにしてるので、何も言わないで下さいね。もし私の考えてる通りならしびれすぎです。恥をさらしまくってますしねぇ。

ちょっとおしゃべりでした。では、また次回、できればすぐにでも（笑い）

Cookの定理 その7

それでは、Cookの定理、手順2の6回目です。

カニは静かに

今回は、今日テレビで見た駄洒落をぱくりました。白いワニが見える（(c)江口寿史）

おっほん。さて、静かになったところで、そろそろCookの定理の説明も大詰めです。前回はNTMをSATに変換するためにはG1～G6を行えば良いということと、そのうちG1～G５にあたっては具体的なSAT形式を説明しました。

今回はG6のSAT形式での表現を説明します。まず、G6を再掲しましょう

　　G6　：i番目の段階(ただし、0≦i<p(n))において,

　　　　　マシンMLのi+1番目の状態は、

　　　　　i番目の状態からチューリングマシンの状態遷移関数δ

　　　　　によって決定される　　　

でした。

チューリングマシンの状態遷移関数δにかんしては、NTMの数理モデルとクラスPとNPの違いの回を参照して下さい。

最初に一番ややこしいところを説明しましょう。

実は、G6をSATに変換するときに一番ややこしいのは、ヘッドのないところのテープの状態は、次もそのままであるという、われわれにとっては一番当たり前に思えるところだったりします。

テープの番地は以下のブール変数で表せるのでした。

　　S[i,j,k]　（0≦i≦p(n),　-p(n)≦j≦p(n)+1,　0≦k≦ν）

　　　i番目の処理の段階でテープのj番地のデータはskである

そういうわけで、i番目にヘッドのないテープの番地kのデータlは、i+1番目もそのままである、というのをちょっと考えてみてみましょう。

われわれがいきなりSAT形式で考えるのは難しいので、比較的考えやすい論理式から入ることにしましょう。自分で考えたい人は、ここからしばらくは飛ばしても良いと思います。

では、まず、i番目にテープの番地kにヘッドがないというブール変数を考えます。これは簡単で、

¬H[i,k]

がTになればいいのですね。

つぎにi番目のテープの番地kのデータlは、i+1番目もそのままであると言うのは、次のように表わします。

S[i,k,l]⇒S[i+1,k,l]　（S[i,k,l]ならばS[i+1,k,l]）

これは、次のような式に置換されると言うことが分かっています。

S[i,k,l]⇒S[i+1,k,l]＝￢S[i,k,l]∨S[i+1,k,l]

真理値表をつけておきましょうか。

　　　　　　

と、なります。こういう定義なので、こういうもんだと思って下さい。つまり、AがTならばBを判定しますが、AがFであれば、この式事態は、判定せずにTとしておくという意味になります。こういう定義です。まぁ、AがFであればこの式はFとしてもいいのですが、たくさんの計算が必要な論理式においてTにしておいた方が計算がうまくいくようです。納得いかない方はネットで調べてみて下さい。分かりやすく説明してあるところがあります。これは、ある種の経験則といって良いでしょう。わたしも、大学の卒業論文でプロダクションシステムというのをやったので、だいぶこの論理式にはお世話になったのですが、確かにこれで問題はありませんでした。

さて、まとめましょう。

¬H[i,k]⇒(S[i,k,l]⇒S[i+1,k,l])

という三段論法の論理式で表わされるわけですね。変形していくと、

¬H[i,k]⇒(S[i,k,l]⇒S[i+1,k,l])＝H[i,k]∨(S[i,k,l]⇒S[i+1,k,l])

＝H[i,k]∨(￢S[i,k,l]∨S[i+1,k,l])

最後の式は括弧をとっても問題ないので、最終的に、i番目にヘッドのないテープの番地kのデータlは、i+1番目もそのままである、という事はつぎのSATの表現で表わされることになります

{H[i,k],￢S[i,k,l],S[i+1,k,l]}

というわけです。われわれにとって一番簡単にみえることががけっこう難しいという変な感じですが、まぁこういうことです。

今回はカニもAB（エビ）もでてきたというわけで、お後がよろしいようで。

という論理式を最後に書いて終わります（笑い）