３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