P、NP 与 NP 完全

复杂度理论不再只问“这个算法多快”，而是问“这类问题是否存在高效算法”。P、NP 和 NP 完全讨论的是输入规模增长时的渐近可解性。

1. 先把优化问题变成判定问题

复杂度类别通常定义在答案为“是/否”的判定问题上。例如：

• 优化版旅行商：最短环路多长？
• 判定版旅行商：是否存在长度不超过 $K$ 的环路？

若能多项式时间求优化答案，自然能回答判定问题；很多情况下也能通过多次判定恢复最优值。

2. P 类

P 是可由确定性算法在输入长度的多项式时间内解决的判定问题集合，例如排序后的查找、最短路、最小生成树对应的判定版本。

多项式时间不是“实际一定快”，$n^{100}$ 仍不可用；它代表一种在规模扩张下相对稳定、对机器模型也较鲁棒的“可有效计算”边界。

3. NP 类

NP 是“给出一个多项式长度的候选证书后，可以在多项式时间验证其正确性”的判定问题集合。

例如 Hamilton 环问题的证书是一串顶点顺序。验证者只需检查每个顶点恰出现一次、相邻顶点有边、首尾有边，都是多项式时间。

NP 不是“非多项式”，也不是“目前不知道怎么做”。因为能多项式时间求解的问题当然也能验证，所以

$$P\subseteq NP.$$

是否 $P=NP$ 仍是开放问题。

4. 多项式时间规约

记

$$A\le_p B$$

表示存在多项式时间变换 $f$，使得

$$x\in A\iff f(x)\in B.$$

含义是：若会解 $B$，就能借它解 $A$，所以 $B$ 至少和 $A$ 一样难。

方向最容易写反。要证明新问题 $B$ 很难，应从一个已知困难问题 $A$ 规约到 $B$，而不是把 $B$ 规约到 $A$。

5. NP-hard 与 NP-complete

• $H$ 是 NP-hard：所有 NP 问题都可多项式规约到 $H$；$H$ 本身不一定在 NP，甚至不一定是判定问题；
• $C$ 是 NP-complete（NPC）：$C\in NP$ 且 $C$ 是 NP-hard。

若任一 NP 完全问题有多项式算法，则所有 NP 问题都有多项式算法，从而 $P=NP$。

6. 证明一个问题 NP 完全

标准两步不能漏：

1. 证明 $B\in NP$：说明证书是什么，验证为何是多项式时间；
2. 选已知 NP 完全问题 $A$，构造 $A\le_p B$：说明变换是多项式时间，并证明“是实例当且仅当是实例”。

只写“显然很难”不算证明；只给 NP-hard 规约也没有证明它属于 NP。

7. SAT、3SAT 与顶点覆盖

SAT 问布尔公式是否存在满足赋值，是第一个被证明 NP 完全的问题。3SAT 限制每个子句恰含至多三个文字，仍为 NP 完全。

顶点覆盖（VC）问是否能选不超过 $K$ 个顶点覆盖每条边。经典链条可从 3SAT 规约到 VC：

• 为每个变量构造一对互斥文字顶点；
• 为每个子句构造三角形；
• 用连边表达文字与子句出现关系；
• 选择预算迫使方案同时表达一致赋值和每个子句至少一个真文字。

考试若要求规约，必须把构造、预算 $K$、正向和反向证明都写清，而不能只画图。

8. 常见逻辑错误

• “没有找到多项式算法，所以问题是 NP 完全”：错误；
• “问题在 NP，所以它很难”：错误，P 也包含于 NP；
• 从待证问题规约到已知 NPC：只能说明待证问题不比它难；
• 用指数时间能验证证书：不能证明属于 NP；
• 把数值大小当输入长度：二进制整数 $W$ 的长度是 $\Theta(\log W)$。

9. 遇到 NP 完全问题怎么办

NP 完全并不意味着“小规模也不能算”。实际可使用回溯剪枝、分支定界、动态规划、参数化算法、近似算法、启发式和整数规划。复杂度结论告诉我们不要期待对所有大实例都有通用精确多项式算法，除非 $P=NP$。