３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