3-SAT NP-Complete 证明

阅读本篇需要先理解 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 = 1$ 。即判断是否存在布尔表达式 $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 难（NP-Hard）。 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$ 的组成，例如 $C_i = x_a^i$ 。我们将其变换为 $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 完全的。