经典 NP-Complete 问题与证明

首先，clique problem 是 NP 问题。这个比较好证明。
其次，我们尝试把 3SAT 归约到 Clique. 对于每一个 clause $c_i=x_1\lor x_2\lor x_3$，建立三个节点 $n_{i,1},n_{i,2},n_{i,3}$.

对于图中不属于同一个 clause 的两个节点 $x_i, x_j$，只要 $x_i\ne \lnot x_j$，就建立一条边。

我们令 $k=m$，检查图里是否存在大小为 $k$ 的 clique.

我们证明 $\text{3SAT} \propto_p \text{Subset Sum}$

考虑 3SAT 有 $n$ 个变量和 $m$ 个 clause，对于每一个 3SAT 变量 $x_i$，在 subset sum 里创建两个变量 $t_i,f_i$

我们令 set 里的变量均有 $n+m$ 位，前 $n$ 位记为变量部分，后 $m$ 位记为子句部分。

• $t_i$ 变量部分第 $i$ 位设置为 $1$，子句部分若 $\text{clause}_j$ 包含 $x_i$ 则子句部分的第 $j$ 位设置为 $1$
• $f_i$ 变量部分第 $i$ 位设置为 $1$，子句部分若 $\text{clause}_j$ 包含 $\lnot x_i$ 则子句部分的第 $j$ 位设置为 $1$

同时，对每一个子句 $\text{clause}_i$，创建变量 $c_i$，其变量部分为全 $0$，子句部分仅第 $i$ 位为 $1$.

考虑如何构造 $T$，令 $T$ 的变量部分的每一位都是 $1$，子句部分的每一位都是 $3$.

我们证明 $\text{Subset Sum}\propto_p \text{Equal Sum Partition}$

令 $s=\sum a_i$，

• 如果 $t=\frac s2$，那么问题不变
• 如果 $t\gt \frac s2$，那么添加一个数 $a_{n+1}=2t-s$
• 否则 $t\lt \frac s2$，那么添加一个数 $a_{n+1}=s-2t$

思路：我们证明 $\text{Subset Sum}\propto_p \text{Knapsack}$

【归约】令物品 $w_i=v_i=a_i$，且 $W=V=T$.

我们证明 $\text{3SAT}\propto_p \text{H-Cycle}$

【归约】
令 3SAT 有 $n$ 个变量和 $m$ 个子句。对于一个变量 $x_i$：

1. 让其对应一行节点 $row_i$，包含 $3m+3$ 个节点，这一行的相邻节点之间连双向边
2. 在这一行节点中，从第二个节点开始，每三个节点代表一个 clause $c_j$，颜色顺序为黄、绿、绿
3. 额外有一个黄色节点，分别指向这一行的开头结尾两个节点
   1. 规定 $x_i=\texttt{true}$ 则往左走，否则往右走
4. 一行的开头结尾两个节点又分别指向 $x_{i+1}$ 的额外黄色节点

对应 $x_i$

对于每一个子句 $c_j$，找到其所包含的三个变量的行 $row_i$ 中，对应 $c_j$ 的两个绿色节点 $row_{i,1},row_{i,2}$，分别连不同方向的有向边。

• 如果是 $x_i$，则连边方向为：靠左的绿色节点

对应 $c_j$