讨论课 12：NP 完全性归约与进阶话题

由于 \(A\) 可归约到 \(B\)，我们知道 \(B\) 的算法可用来求解 \(A\)，这意味着「求解 \(B\) 至少和求解 \(A\) 一样难」。

(a) 若 \(A \in P\)，则 \(B\) 至少和某个 P 中问题一样难。因此 \(B\) 可能在 \(P\)、\(NP\) 或 NP-难中，无法推出关于 \(B\) 的任何确定信息。

(b) 若 \(B \in P\)，则「求解 \(A\) 的难度至多和求解 \(B\) 相当」，因此 \(A\) 也属于 \(P\)。

(c) 若 \(A\) 是 NP-难的，则 \(B\) 至少和某个 NP-难问题一样难，因此 \(B\) 也是 NP-难的。

(d) 若 \(B\) 是 NP-难的，则 \(A\) 可能属于 \(P\)、\(NP\) 或 NP-难，无法推出关于 \(A\) 的任何确定信息。

(a) 从 3-SAT 到 Exact 4-SAT

给定一个 3-SAT 实例，引入一个新变量 \(y\)。对每个 3-SAT 子句，例如 \((x_1 \lor x_2 \lor x_4)\)，创建两个 4-SAT 子句：

\[(x_1 \lor x_2 \lor x_4 \lor y) \land (x_1 \lor x_2 \lor x_4 \lor \lnot y)\]

把这些子句一起交给 Exact 4-SAT 求解器。

正确性：若求解器令 \(y = \text{true}\)，则所有含 \(y\) 的子句被立即满足，而含 \(\lnot y\)（即 \(y = \text{false}\)）的那一半子句就等价于原 3-SAT 子句，因此 \(x_i\) 的赋值必须满足原 3-SAT 实例。\(y = \text{false}\) 时同理。无论哪种情况，\(x_i\) 的赋值都必须是原 3-SAT 实例的一组有效解。

(b) 从 Exact 4-SAT 到 3-SAT

要把每个 4 文字子句转化为至多 3 文字的子句，对每个 4-SAT 子句（例如 \((x_1 \lor x_2 \lor x_3 \lor x_4)\)），引入一个新变量 \(y\)，加入以下两个子句：

\[(x_1 \lor x_2 \lor y) \land (x_3 \lor x_4 \lor \lnot y)\]

正确性：

• 若原 4-SAT 实例可满足，则对每个子句，若前两个文字为假，令 \(y = \text{true}\) 以满足第一个子句，此时第二个子句要求 \(x_3 \lor x_4\) 为真，即原 4 文字子句被满足；否则令 \(y = \text{false}\)。因此 3-SAT 实例可满足。

• 反之，若该 3-SAT 实例可满足，则由于 \(y\) 与 \(\lnot y\) 必有一个为假，每组两个子句中必有一个依赖原 4-SAT 子句的某个文字为真，因此原 4-SAT 实例也可满足。

给定环覆盖实例 \(G\)，构造二分图 \(G'\) 如下：对 \(G\) 的每个顶点，在 \(L\) 中放一个顶点 \(v_L\)，在 \(R\) 中放一个顶点 \(v_R\)。对 \(G\) 中的每条边 \((u, v)\)，在二分图中加入无向边 \((u_L, v_R)\)。我们断言：\(G\) 有环覆盖 当且仅当 \(G'\) 有完美匹配。

正向：若 \(G\) 有环覆盖，则环覆盖中每个顶点恰好有一条入边，因此每个 \(v_R\) 恰好与一条所选边相邻；环覆盖中每个顶点恰好有一条出边，因此每个 \(v_L\) 恰好与一条所选边相邻。于是对应的二分图边集构成一个完美匹配。

反向：若 \(G'\) 有完美匹配，则通过取 \(G\) 中对应该完美匹配的边，可以构造出 \(G\) 的一个环覆盖。例如，若完美匹配中包含边 \((a_L, b_R), (b_L, c_R), \ldots, (z_L, a_R)\)，则在 \(G\) 中加入环 \(a \to b \to c \to \cdots \to z \to a\)。由于 \(v_L\) 和 \(v_R\) 都恰好与一条匹配边相邻，每个顶点都会被包含在对应的环覆盖中。

(a) Public Funds 属于 NP。

我们可以在多项式时间内验证 Public Funds 的一个解：给定一组选中的账户，验证它们的余额之和是否恰好等于某个围栏的价格，以及使用的账户数是否不超过 \(k\)。这可在多项式时间内完成。

(b) Public Funds 是 NP-难的——从 Subset Sum 归约。

对 Subset Sum 的实例，设其有 \(m\) 个数、目标和为 \(s\)。构造 Public Funds 实例如下：

• 让 \(m\) 个数分别对应 \(m\) 个银行账户的余额 \(b_m\)；

• 令目标和 \(s\) 对应唯一围栏的价格 \(c_1\)（即只设一个围栏）；

• 将最多可使用的账户数 \(k\) 设为 \(m\)。

正确性（双向性）： 1. 若 Subset Sum 实例有解，则取该解中元素对应的账户，它们的余额之和恰为 \(s\)，即等于唯一围栏的价格 \(c_1\)，因此 Public Funds 实例有解。 2. 若符合该变换格式的 Public Funds 实例有解，则算法选出的那组账户对应 Subset Sum 实例中一个和为 \(s\) 的子集，因此 Subset Sum 实例有解。

因此 Subset Sum \(\leq_P\) Public Funds，Public Funds 是 NP-难的。结合 (a)，Public Funds 是 NP-完全的。

我们根据一个 3-SAT 公式显式地构造一个整数线性规划，并证明该 ILP 可行 当且仅当 SAT 公式可满足。

设变量为 \(x_1, \ldots, x_n\)，加入约束 \(x_i \in \{0,1\}\)；这里 \(x_i = 1\) 对应 \(x_i = \text{true}\)，\(x_i = 0\) 对应 \(x_i = \text{false}\)。

接下来把布尔子句如 \((x_1 \lor \lnot x_4 \lor x_7)\) 翻译成线性约束。我们要求 \(x_1, x_4, x_7\) 中至少一个为真，即在 ILP 中要求 \(x_1 = 1\) 或 \(x_4 = 0\) 或 \(x_7 = 1\)。于是按如下方式系统地进行转换：

\[x_1 \lor \lnot x_4 \lor x_7 \quad \Longleftrightarrow \quad x_1 + (1 - x_4) + x_7 \ge 1\]

也就是说，把每个否定文字 \(\lnot x_i\) 替换为 \((1 - x_i)\)，把每个 OR 运算符替换为 \(+\)。该约束保证了至少一个文字为真——因为 \(x_1, (1-x_4), x_7\) 中至少有一个必须被置为 1。对每个子句都执行此变换，便得到一组关于 0-1 变量的线性约束。

正确性：任何可满足的赋值都对应整数规划的一组可行解，反之亦然。因此求解整数线性规划的可解性足以求解 3-SAT。

(a)

穷举全部 \(2^n\) 组赋值。对每组赋值，可在 \(O(m)\) 时间内检查其是否满足所有子句。因此可在 \(O(2^n m)\) 时间内找到一组满足赋值（若存在）。

(b)

设 \(L\) 是 NP 中的任意问题。由于 3-SAT 是 NP-难的，\(L\) 可在多项式时间内归约为一个 3-SAT 实例。该归约耗时多项式时间，且写出每个变量/子句至少需要 \(O(1)\) 时间，因此该 3-SAT 实例的变量数不超过 \(n^b\)，子句数也不超过 \(n^b\)，其中 \(b\) 是某个常数（对所有足够大的 \(n\) 成立）。

算法：先将问题归约为 3-SAT，再用 (a) 的算法求解该 3-SAT 实例，耗时 \(O(2^{n^b} \cdot n^b) = O(2^{n^{b+1}})\)。取 \(c = b + 1\)，即为 \(O(2^{n^c})\)。

另一种方法：由于问题属于 NP，若答案为「是」，则存在一个多项式规模的「证据」（witness），可送入验证器在多项式时间内输出「是」；若答案为「否」，则没有任何证据能使验证器输出「是」。因此可穷举所有证据并逐一送入验证器；证据数量为多项式级别（即 \(O(2^{n^c})\)），验证器运行时间为多项式，总时间为 \(O(2^{n^c})\)。

(c)

该归约说明停机问题是 NP-难的。但我们可证明停机问题不在 NP 中，因此它不是 NP-完全的：由 (a)/(b)，NP 中任何问题都有有限时间（指数时间）算法，但停机问题没有有限时间算法。因此停机问题不是 NP-完全的（它是 NP-难的，但更难——不属于 NP）。