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 完全。