“3-SAT NP-Complete 证明”

阅读本篇需要先理解 SAT 问题是 NP 完全的，其主要由 Cook–Levin theorem 证明。有很多非常优秀的资源都对 SAT 的 NP 完全性作了证明，但这里就先省略掉了，还请读者自己参考。以后有时间的话我会补一个我理解的 SAT 证明问题。

3-SAT (3-CNF-SAT）的描述为：判断是否存在一个布尔表达式 ，其中 ，使得 。即判断是否存在布尔表达式 为真。

为了证明 3-SAT 的 NP 完全性，我们需要 1） 证明它是 NP 问题。 2）证明它 NP 难（NP-Hard）。 3-SAT 与 SAT 问题类似，当我们得到一组解时，我们只需要将其带入布尔表达式即可判断解的正确性。所以 3-SAT 显然是 NP 问题。为了证明其 NP 难，**我们将把 SAT 归约到 3-SAT **。

对于每一个 SAT 问题，例如：

他的每一个 都是由一定数量的变量组成的。我们分情况对每一组变量做一下操作。

• 若 ，即只有一个变量参与该 的组成，例如 。我们将其变换为 。
• 若 ，例如 。我们将其变换为 。
• 若 ，我们保持其不变。
• 若 ，例如 。我们将其变换为 。其中 是一个新的变量。
• 如此类推

以上操作显然是在多项式时间内可以做到的。所以，给定一个 SAT ，我们可以在多项式时间内将其转换为一个 3-SAT 。且当 SAT 有解时，3-SAT 一定有解；而 3-SAT 有解时，由于 3-SAT 是 SAT 的一个子类，所以 SAT 也有解。故 3-SAT 是 NP 完全的。