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 问题的通用套路：
- 证明该问题属于 NP（给定解能在多项式时间内验证）；
- 证明一个已知的 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 难问题的实用策略
- 小规模精确求解：分支限界法、回溯法、动态规划（伪多项式时间）；
- 近似算法：牺牲最优性换取多项式时间与可证明的近似比；
- 随机化算法：以可控的出错概率换取效率；
- 启发式算法：模拟退火、遗传算法、禁忌搜索、蚁群算法，无近似比保证但实践效果好；
- 参数化算法：把指数部分限制在某个参数 $k$ 上，如 $O(2^k n)$。
评论