Soptq

分團問題（Clique Problem） 的描述如下：給定 $<G, k>$，其中 $G$ 是一個無向圖，問圖中是否存在點集 $V$ 組成一個團，且 $\lvert V \rvert <= k$。即 $V$ 中的點相互連接？以下圖為例。$<B,C,D,E>$ 就是符合條件的一個點集，因為這四個點相互連接，即可以構成一個團。

首先我們為了真證明其 NP 完全，我們還是要先證明其是一個 NP 問題。若給定一個點集 $V$，其中 $\lvert V \rvert <= k$。那麼我只需要檢查每一個 $V$ 中的點是否與其他點相連，即可驗證 $V$ 的正確性。顯然該驗證步驟是可以在多項式時間內完成的，所以分團問題在 NP 完全問題中。

接下來，我們將 3-SAT 歸約到分團問題來證明分團問題是 NP 難的。首先我們知道 3-SAT 的形式如下：

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

那麼給定一個 3-SAT 表達式，對於表達式中的任意兩個變量 $x_a^i$ 與 $x_b^j$，有：

• 若 $i \ne j$
• 若 $a = b$，則 $x_a^i$ 與 $x_b^j$ 保持一致性。一致性的意思是，當 $x_a^i$ 取真時，$x_b^j$ 也取真；當 $x_a^i$ 取假時，$x_b^j$ 也取假。

則連接 $x_a^i$ 和 $x_b^j$。這樣我們就把一個 3-SAT 布爾表達式轉換成了圖。舉一個例子，例如一個 3-SAT 布爾表達式為 ：

$C = (x+y+z)\cdot (\overline{x}+\overline{y}+\overline{z})\cdot (x+\overline{y}+z)\cdot (\overline{x}+y+\overline{z})$

則其按照上述規則作出的圖為：

好了，現在我們要證明兩個事情：1）若存在一個有解的 3-SAT，且這個 3-SAT 有 $k$ 個簇（$k$ 個 $C_i$），則由其轉換的圖 $G$ 可以使分團問題 $<G, k>$ 有解。 2）若存在一個分團問題 $<G,k>$ 有解，則我們一定可以從 $G$ 中轉換到一個 3-SAT 有解。

對於（1），若給定的 3-SAT 有解，則由 3-SAT 定義的知，要使其布爾表達式為真，則每一個簇都要為真，則每一個簇中至少有一個變量為真。所以我們可以在圖中把為真的那個變量圈出來。對於上述例子來說，以它的一個解圈出來後的圖是這樣的：

根據我們 3-SAT 轉 $G$ 的規則，每一個變量都與其他所有不跟他在一個簇且不與它矛盾的變量相連了。所以我們可以保證，選出來的點一定可以構成一個團（即相互連接）。

對於（2），若給定一個分團問題 $<G,k>$ 有解，則我們逆向套用轉換規則，將 $G$ 轉換為一個布爾表達式，然後把 $V$ 中的點所對應的變量賦真。因為 $V$ 中的點相互連接，則根據規則它們既不在一個簇又不矛盾，所以可以保證布爾表達式一定為真。

綜上所述，我們成功把 3-SAT 歸約到了分團問題，證明了分團問題 NP 完全。