Toshusai blog

知識の保管庫

3SATがNP完全であることの証明

数学

はじめに

CNF論理式とは

リテラル（論理変数またはその否定）の論理和である節の論理積からなる論理式
CNF論理式: { \displaystyle (x_1 \lor x_2 \lor …) \land (x_1 \lor \lnot x_2 \lor …) \land … }
リテラル: { \displaystyle x_1, x_2, \lnot x_2 }
節: { \displaystyle (x_1 \lor x_2 \lor ...) }

SAT問題とは

あるCNF論理式を真にするようなリテラルの組み合わせは存在するかどうかの充足可能性問題。 { \displaystyle (x_1 \lor x_2) \land (\lnot x_1 \lor \lnot x_2) }
x1を真にx2を偽にすればこのCNF論理式は真になるので回答はYes。

3-SAT問題

SAT問題の中で節のリテラル数が高々3つのもの。 { \displaystyle (\lnot x_1 \lor x_2 \lor x_3) \land (x_1 \lor \lnot x_2 \lor \lnot x_3) \land … }

3SATがNP完全であることの証明

SATがNP完全であることはCook Levinの定理より自明である。 3SAT問題に関して、リテラルへの値の代入は多項式時間で検証できるため、3SATはNPである。
SATが多項式時間で3SATに変換できるならば3SATがNP完全であるので、これを示す。

以下のようにして3つ以上のリテラルを含むSATの各節を3SATのいくつかの新しい節の連接節に縮小する。
SATの1つの節を例とする
{\displaystyle (x_1 \lor \lnot x_2 \lor x_3 \lor \lnot x_4 \lor x_5 \lor \lnot x_6) }

1.対応するSATの節の最初の2つのリテラルと自由変数z1との論理和である3SATの新しい節を作る。
{\displaystyle (x_1 \lor \lnot x_2 \lor z_1) }

2.SATの節の次のリテラルとz1の否定と自由変数z2の論理和の節を作る。
{\displaystyle (x_1 \lor \lnot x_2 \lor z_1) \land (x_1 \lor \lnot z_1 \lor z_2) }

3.これをSATの節のリテラルが残り2つになるまで繰り返し、最後の2つのリテラルと最後の自由変数の否定で論理和の節を作る。
{\displaystyle (x_1 \lor \lnot x_2 \lor z_1) \land (x_3 \lor \lnot z_1 \lor z_2) \land (\lnot x_4 \lor \lnot z_2 \lor z_3) \land (x_5 \lor \lnot x_6 \lor \land \lnot z_3) }

4.1から3ををSATの各節に対して行い新しい3SAT問題を作成する。

このSAT3への変換は元のSATがm個(m>3)のリテラルを含む場合、変換されたSAT3はm-2の節を持ち、m-3の自由変数を持つ。 したがってこの変換は多項式時間、多項式空間でできる。

次に、この変換を行った際、問題の真偽が変わらないことを示す。
{\displaystyle I} あるSATが充足可能のとき、対応する3SATも充足可能である。

SATはすべての節が同時に真と評価されるときに充足可能である。SATの節が真のとき、少なくとも1つのリテラルは真である。したがって、対応する3SATでは、その真であるリテラルを含む節は真であり、3SARTのその節の自由変数を偽にすることで隣の3CNF節を真にすることができる。よってすべての3CNF節を真にするように変数を変えることができる。

{\displaystyle I\hspace{-1pt}I} 3SATが充足可能なとき、対応するSATも充足可能である。

3SATのすべての節は真になる。これはSATのすべての節に少なくとも1つ真であるリテラルが存在する場合である。SATのある節のすべてのリテラルが偽の場合、3SATの自由変数に関わらず節を真にすることができないため。よってSATの節のリテラルは少なくとも1つ真であり、対応するSAT節を真にする。

{\displaystyle I}, {\displaystyle I\hspace{-1pt}I}より、3SAT問題はNP完全である。