まむの備忘録

まむです。備忘録です。

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

以下の問題3SATはNP完全である。証明の概略を示す。

3SAT

INPUT：
Uを変数集合とする。 Uの任意の元 xか、その否定 \lnot xをリテラル(literal)という。幾つかのリテラル u_1,u_2,...,u_mの選言 \cup_{i=1}^m p_iをクローズ(clause)という。 m=3であるような幾つかのクローズたち C_1, C_2, ..., C_n の連言 C = \cap_{i=1}^n C_iが入力である。
OUTPUT：
Cが充足可能かどうか判定する。すなわち、 Cを真にするような各変数への真偽割り当てが存在するか判定する。

NP完全性の証明の流れ

ある判定問題 Aが、NP完全であることを示したいときは以下の二つを示せばよい。
・ A \in NPであること。
・あるNP完全である問題 Bが存在して、 Bの任意のインスタンス Iが Aのインスタンス I'に多項式時間で変形でき、 B(I) = A(I')が成り立つ。（多項式時間多対一帰着という）

3SATのNP完全性証明

3SATがNPに属することを簡単に述べておく。 3SATの入力とその真偽割り当てが与えられたら、その割り当てが入力の論理式を充足するかを多項式時間で判定できるので3SATはNPに属する。 後者の帰着証明には、Cookの定理を用いる。 すなわち、SATがNP完全であることを用いる。 SATのインスタンス C = \cap_{i=1}^n C_i = \cap_{i=1}^n \cup_{j=1}^{m_i} p_{i_j} から3SATのインスタンス C'を構成し、 Cが充足可能であるときにのみ C'が充足可能であることを示せばよい。 各 C_iがいくつのリテラルから成っているかで場合に分ける。

(1) m_i = 1のとき

新しい変数 x_1, x_2を導入して、 C_{i_1}' = p_{i_1} \lor x_1 \lor x_2, C_{i_2}' = p_{i_1} \lor \lnot x_1 \lor x_2, C_{i_3}' = p_{i_1} \lor x_1 \lor \lnot x_2, C_{i_4}' = p_{i_1} \lor \lnot x_1 \lor \lnot x_2, とする。

(2) m_i = 2のとき

新しい変数 xを導入して、 C_{i_1}' = p_{i_1} \lor p_{i_2} \lor x, C_{i_2}' = p_{i_1} \lor p_{i_2} \lor \lnot xとする。

(3) m_i = 3のとき

C_i' = C_iとする。

(4) m_i \ge 4のとき

新しい変数 x_1, x_2, ..., x_nを導入して、 C_{i_1}' = p_{i_1} \lor p_{i_2} \lor x_1, C_{i_{k - 1}}' = \lnot x_{k- 2} \lor p_{i_k} \lor x_{k - 1} \ \ \ (3 \le k \le m_i - 2), C_{i_{m_i - 2}}' = \lnot x_{m_i - 2} \lor p_{i_{m_i - 1}} \lor p_{i_{m_i}}とする。

以上のように構成した C_iの選言を C'とする。 Cと C'の充足可能性が同値であることは後者の構成から明らか。