Soptq

3 色問題（3-Color）的描述如下：給定一個圖 $G$，為 $G$ 中每一個頂點塗色，要求每兩個相鄰的頂點顏色不一致。問是否可以用 3 種顏色完成上面的要求。

首先我們證明這個問題是 NP 問題。顯然，若給定一個解，我們只需要遍歷每一個節點，檢查其與其相鄰節點的顏色是否一致，即可判斷解是否正確。這個操作顯然是可以在多項式時間內完成的，所以 3 色問題是 NP 問題。

接下來我們通過將 SAT 轉換到 3 色問題來證明 3 色問題是 NP 難問題。即任意給定一個 SAT ，我可以在多項式時間內將其轉化為 3 色問題。實際上，通過下面的證明我們可以最終知道，3 色問題和 SAT 問題實際上是完全等價的。

首先我們知道 SAT 實際上與電路問題是等價的。即任意一個 SAT，它的布爾表達式都可以轉換為一個等價的電路。我們利用電路作為中介，證明 3 色問題可以來構成電路來說明 3 色問題與電路問題的等價性，進而說明其與 SAT 問題的等價性。

首先我們規定我們要用的 3 種顏色分別叫做 $T$ , $F$ , $N$。其中 $T$ 代表真， $F$ 代表假， $N$ 代表其他某種顏色（例如中性）。假設我們的輸入變量是 $P$，我們先試著連接 $P$ 和 $N$ 來使 $P$ 的取值只能為 $T$ 和 $F$，即構造了一個布爾變量。

接著，我們引入一個新的節點 $NOT(P)$ 並嘗試構造一個否門（NOT Gate）。我們構造的方法為先將 $NOT(P)$ 與 $N$ 連接，使其成為一個布爾變量，再將其與 $P$ 連接，使其不能和 $P$ 取值相同。這時，當 $P$ 為真時， $NOT(P)$ 為假；當 $P$ 為假時， $NOT(P)$ 為真。

這樣我們就成功構造出了一個否門。現在我們嘗試構造一個 或門（OR Gate）。我們引入三個節點 $P$ , $Q$ , $P~OR~Q$ 分別表示兩個輸入和或門的輸出。我們首先將 $P$ , $Q$ , $P~OR~Q$ 分別連接 $N$ 使它們變成布爾變量，然後按下圖連接各個節點。

當 $P$ 為真， $Q$ 為假時，我們由圖可得 $P~OR~Q$ 只能為真，同理當 $P$ 為假， $Q$ 也為假時，我們由圖可得 $P~OR~Q$ 只能為假。

與是我們成功使用 3 色問題構造出了非門和或門。結合他們我們得到了 或非門。根據邏輯電路，使用或非門我們可以構造出其他所有門。於是乎我們從 3 色問題出發，構造出了電子邏輯。於是對於任何一個電路問題，我都可以通過替換的方式將其轉換為一個 3 色問題；對於任意一個 3 色問題，我也可以通過替換的方式將其轉換為一個電路問題。替換的過程顯然是可以在多項式時間內完成的。所以我們證明了 3 色問題與 SAT 問題的等價性，即 3 色問題是 NP 完全的。