3-SAT NP-完全証明

この記事を読むには、まず SAT 問題が NP 完全であることを理解する必要があります。これは Cook–Levin theorem によって主に証明されます。SAT の NP 完全性に関する多くの優れたリソースがありますが、ここでは省略します。読者は自分で参照してください。時間があれば、私が理解している SAT の証明問題を補完します。

**3-SAT (3-CNF-SAT）** の説明は次のとおりです：ブール式 $C = C_1 \cap C_2 \cap \cdots \cap C_n$ が存在するかどうかを判断します。ただし、 $C_i = x_a \cup x_b \cup x_c$ です。つまり、ブール式 $C = (x_a^1 \cup x_b^1 \cup x_c^1)\cap (x_a^2 \cup x_b^2 \cup x_c^2)\cap \cdots\cap (x_a^n \cup x_b^n \cup x_c^n)$ が真であるかどうかを判断します。

3-SAT の NP 完全性を証明するためには、1）それが NP 問題であることを証明する必要があります。 2）それが NP 困難であることを証明する必要があります。 3-SAT は SAT 問題と似ていますが、解のセットが得られた場合、それをブール式に代入するだけで解の正当性を判断するだけです。したがって、3-SAT は明らかに NP 問題です。NP 困難性を証明するために、SAT を 3-SAT に帰着させます。

各 SAT 問題について、例えば：

$\begin{cases} C = C_1 \cap C_2 \cap \cdots \cap C_n \\ C_i = x_a^i \cup x_b^i \cup \cdots \cup x_m^i \end{cases}$

それぞれの $C_i$ は、一定数の変数で構成されています。各変数のグループに対して以下の操作を行います。

もし $\lvert C_i \rvert = 1$ 、つまり、 $C_i = x_a^i$ のように、 $C_i$ に参加する変数が 1 つだけの場合、それを $C_i = x_a^i \cup x_a^i \cup x_a^i$ に変換します。
もし $\lvert C_i \rvert = 2$ の場合、例えば $C_i = x_a^i \cup x_b^i$ の場合、それを $C_i = x_a^i \cup x_a^i \cup x_b^i$ に変換します。
もし $\lvert C_i \rvert = 3$ の場合、そのままにします。
もし $\lvert C_i \rvert = 4$ の場合、例えば $C_i = x_a^i \cup x_b^i \cup x_c^i \cup x_d^i$ の場合、それを $C_i = (x_a^i \cup x_b^i \cup w^i)$ $\cap ( \overline{w^i} \cup x_c^i \cup x_d^i)$ に変換します。ここで、 $w^i$ は新しい変数です。
この操作を繰り返します。

上記の操作は、多項式時間で行うことができます。したがって、与えられた SAT を多項式時間で 3-SAT に変換することができます。また、SAT が解を持つ場合、3-SAT も必ず解を持ちます。逆に、3-SAT が解を持つ場合、3-SAT は SAT のサブクラスであるため、SAT も解を持ちます。したがって、3-SAT は NP 完全です。