Soptq

閱讀本篇需要先理解 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 完全的。