３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