NP 完全性理论与近似算法

1. 问题的分类

类别	含义
P 类	存在多项式时间算法求解的判定问题
NP 类	存在多项式时间算法验证其解是否正确的判定问题（非确定性图灵机多项式时间可解）
NP 难（NP-hard）	所有 NP 问题都能多项式时间归约到它，但它本身不一定属于 NP
NP 完全（NP-complete，NPC）	同时属于 NP 且是 NP 难的判定问题

显然有 $P \subseteq NP$，但 $P = NP$ 是否成立至今未解。目前普遍认为 $P \ne NP$。

2. 归约（Reduction）

若问题 $A$ 可以在多项式时间内转化为问题 $B$ 的实例，使得 $A$ 的答案为「是」当且仅当 $B$ 的答案为「是」，则称 $A$ 多项式时间归约到 $B$，记作 $A \le_p B$。

• 若 $A \le_p B$ 且 $B$ 有多项式时间算法，则 $A$ 也有；
• 若 $A \le_p B$ 且 $A$ 是 NP 难的，则 $B$ 也是 NP 难的。

3. 第一个 NPC 问题

Cook-Levin 定理：布尔可满足性问题（SAT）是 NP 完全的。

证明 NPC 问题的通用套路：

1. 证明该问题属于 NP（给定解能在多项式时间内验证）；
2. 证明一个已知的 NPC 问题可以多项式时间归约到它。

经典 NPC 问题：SAT → 3-SAT → 团问题、顶点覆盖、哈密顿回路、旅行商问题（TSP）、0-1 背包、图着色、集合覆盖。

4. 近似算法

对于 NP 难问题，若无法在多项式时间内求精确最优解，可以退而求其次：设计多项式时间算法，并证明其解与最优解的比值有界。

设 $A$ 是求解最优化问题的一个近似算法，$A(I)$ 为对实例 $I$ 的输出，$OPT(I)$ 为最优值：

• 绝对近似比：$\left| A(I) - OPT(I) \right| \le k$；
• 相对近似比：$\max\left(\dfrac{A(I)}{OPT(I)}, \dfrac{OPT(I)}{A(I)}\right) \le \rho$，称 $A$ 为 $\rho$-近似算法。

问题	近似算法	近似比
顶点覆盖	反复取一条未覆盖边，把两端点都加入解	2
集合覆盖	每次贪心选取覆盖未覆盖元素最多的集合	$O(\ln n)$
旅行商问题（满足三角不等式）	最小生成树 + 前序遍历（Christofides 可达 3/2）	2
多机调度	贪心（LPT，最长处理时间优先）	$4/3 - 1/(3m)$
装箱问题	首次适应（FF）/ 递减首次适应（FFD）	2 / $11/9$
0-1 背包	贪心按单位价值排序	无常数近似比保证

5. 处理 NP 难问题的实用策略

1. 小规模精确求解：分支限界法、回溯法、动态规划（伪多项式时间）；
2. 近似算法：牺牲最优性换取多项式时间与可证明的近似比；
3. 随机化算法：以可控的出错概率换取效率；
4. 启发式算法：模拟退火、遗传算法、禁忌搜索、蚁群算法，无近似比保证但实践效果好；
5. 参数化算法：把指数部分限制在某个参数 $k$ 上，如 $O(2^k n)$。