1 / 4概念
Computational Complexity
计算复杂性回答的是“这个问题在多项式时间内可解吗”。它不讨论某段代码快不快,而是给问题本身分类:P 是可解的,NP 是可验证的,NP 完全是最难的一类;判断标准不是“这题看起来难”,而是能否写出验证器、能否从已知难问题归约。
1 概念
1.1 一句话定义
计算复杂性按资源(时间、空间)给可判定问题分类。P 是确定性图灵机多项式时间可解的问题;NP 是给定证书后多项式时间可验证的问题;NP 完全是 NP 中最难的一类,NP 难是所有 NP 问题都能多项式归约到的问题。
1.2 它解决什么问题
- 判断该不该找多项式算法:NP 难问题通常不该继续找通用精确解,而应转向近似、参数化或启发式。
- 选择求解策略:小 n 精确、可接受误差近似、固定参数 FPT、工程启发式。
- 沟通难度:用“NP 完全”而不是“这题很复杂”描述问题,让团队对预期一致。
- 识别伪多项式:
O(nW)看起来是多项式,但对输入位数是指数,不能当成 P。
没有这套分类,团队会在 NP 难问题上反复尝试“再优化一下”,而真正该做的是改问题或改算法目标。
1.3 不属于本页的内容
| 主题 | 去哪 |
|---|---|
| 可判定性、停机问题、Rice 定理 | Computability |
| 单个算法的渐进分析与摊还 | Complexity Analysis |
| 具体图算法的流程 | Graph Algorithms |
| 近似算法的完整设计与分析 | 近似算法页面(待补) |
| SAT 求解器、ILP 求解器的工程调优 | 求解器工程页面(待补) |
1.4 关键术语
| 术语 | 含义 | 容易混淆的点 |
|---|---|---|
| 判定问题 | 输出是/否的问题 | 不是优化问题本身 |
| 优化 / 搜索问题 | 求最优值 / 求一个解 | 可转成判定问题 |
| 证书 | 用来验证“是”的短证据 | 不是求解过程 |
| P | 确定性多项式时间可解 | 不是“实际很快” |
| NP | 多项式时间可验证 | 不是“非多项式” |
| co-NP | 补集在 NP 中 | 不是 NP 的补集类名 |
| 多项式归约 | 用多项式时间映射实例 | 不是调用求解器 |
| NP 难 | 所有 NP 问题都可归约到它 | 不要求它自己在 NP |
| NP 完全 | NP 难且在 NP 中 | 是最难的一类,不是“不可解” |
| 弱 NP 难 | 存在伪多项式算法 | 子集和是典型 |
| FPT | 固定参数下多项式时间 | 参数必须小 |
2 机制
2.1 心智模型
把问题想成一把锁:P 是“有钥匙,直接开”;NP 是“别人给你一把钥匙,你能快速验证它能不能开”;NP 完全是“NP 里最难开的锁,所有 NP 锁都能改装成它”;NP 难是“至少和这些锁一样难,可能更难”。归约就是“把 A 锁改造成 B 锁”的说明书。
2.2 机制拆解
- 判定问题:输入编码为字符串,输出 yes/no。优化问题可加阈值变成判定问题(如“是否存在 ≤ k 的顶点覆盖”)。
- P:存在确定性图灵机在
poly(n)时间内判定。这里的 n 是输入长度,不是数值大小。 - NP:存在多项式时间验证器
V(x, c),当且仅当存在多项式长度证书 c 使 V 接受。等价于非确定图灵机多项式时间接受。 - co-NP:补集属于 NP;例如“公式不可满足”属于 co-NP。P ⊆ NP ∩ co-NP;是否相等未知。
- 多项式归约:
A ≤_p B表示存在多项式时间可计算映射 f,使x ∈ A ⇔ f(x) ∈ B。若 B ∈ P,则 A ∈ P;若 A 是 NP 难且A ≤_p B,则 B 是 NP 难。 - NP 完全:B ∈ NP 且所有 NP 问题
≤_p B。证明配方:先证 B ∈ NP(给证书和验证器),再从已知 NP 完全问题归约到 B。 - Cook-Levin:SAT 是 NP 完全的;任何 NP 计算都能编码成布尔公式,验证器的每一步都是局部约束。3-SAT 也是 NP 完全的。
- 近似:对最小化问题,α-近似满足
ALG ≤ α·OPT;对最大化问题,满足ALG ≥ OPT/α。PTAS 对任意 ε>0 给(1+ε)近似,固定 ε 时多项式;FPTAS 还对1/ε多项式。 - 参数化:FPT 形如
O(f(k)·n^c);k 是结构参数(解大小、树宽等)。顶点覆盖以 k 为参数是 FPT,独立集以 k 为参数是 W[1] 难。 - 伪多项式:子集和
O(nW)对 n 和 W 多项式,但 W 的输入长度是log W,所以对输入长度是指数;这类问题称为弱 NP 难。
2.3 完整枚举
常见复杂性类:
| 类 | 定义 | 典型问题 | 对补封闭 | 与其他类的关系 |
|---|---|---|---|---|
| P | 确定性多项式时间可解 | 最短路、2-SAT、欧拉回路 | 是 | P ⊆ NP |
| NP | 多项式时间可验证 | SAT、3-SAT、团、顶点覆盖 | 未知 | P ⊆ NP,是否相等开放 |
| co-NP | 补集在 NP | 重言式、UNSAT | 是 | P ⊆ NP ∩ co-NP |
| NP 完全 | NP 难且属于 NP | SAT、3-SAT、团、哈密顿回路 | 未知 | NP 中最难的一类 |
| NP 难 | 所有 NP 问题可归约到它 | 停机问题、TSP 优化、QBF(更强) | 不要求 | 不一定在 NP |
常见 NP 完全/难问题:
| 问题 | 类型 | 已知结果 | 备注 |
|---|---|---|---|
| SAT / 3-SAT | 判定 | NP 完全 | Cook-Levin;3-SAT 是归约起点 |
| 团 / 独立集 | 判定 | NP 完全 | 团与独立集互补;独立集 W[1] 难 |
| 顶点覆盖 | 判定 | NP 完全 | 以解大小 k 为参数是 FPT |
| 哈密顿回路 | 判定 | NP 完全 | 欧拉回路在 P |
| TSP(判定/优化) | 判定/优化 | NP 难 | 度量 TSP 有常数近似 |
| 子集和 | 判定 | NP 完全(弱) | 伪多项式 O(nW) |
| 集合覆盖 | 优化 | NP 难 | ln n 近似,且有下界 |
求解策略:
| 策略 | 时间复杂度 | 保证 | 适用 |
|---|---|---|---|
| 精确指数 | O(2ⁿ)、O(n!) | 最优 | n 很小、必须精确 |
| 近似算法 | 多项式 | 有比率保证 | 可接受误差 |
| 参数化 FPT | f(k)·poly(n) | 最优 | 参数 k 小 |
| 启发式/元启发式 | 多项式或迭代 | 无保证 | 工程可接受 |
| SAT/ILP 求解器 | 最坏指数 | 最优(若跑完) | 工业实例、可编码 |
2.4 关键数字与量级
| 指标 | 量级 | 说明 |
|---|---|---|
| 多项式时间 | n^c | c 固定,n 是输入长度 |
| 指数时间 | 2^n、n! | n=50 已不可行 |
| 子集和 DP | O(nW) | W 是数值,不是输入长度 |
| 顶点覆盖 FPT | O(2^k·n) | k 为解大小 |
| 独立集 W[1] | 无 f(k)·poly(n) 已知 | FPT ≠ W[1] 猜想 |
| 集合覆盖近似 | ln n + 1 | 低于此值困难 |
| 度量 TSP 近似 | 1.5 | Christofides |
3 实践
3.1 最小示例
# NP 的证书验证:给定公式和赋值,多项式时间验证。
VERIFY_SAT(φ, assignment):
for each clause C in φ:
if no literal in C is true under assignment:
return false
return true
# 3-SAT <=p CLIQUE:
# 每个子句的每个文字出现建一个顶点;不同子句的顶点相连,
# 但 x 与 ¬x 不相连;令 k = 子句数。
# φ 可满足 <=> 图中有 k-团。
3.2 常用操作与解法
| 目标 | 做法 | 注意 |
|---|---|---|
| 证明属于 NP | 给证书 + 多项式验证器 | 证书长度必须多项式 |
| 证明 NP 完全 | 先证 ∈ NP,再从已知 NP 完全问题归约 | 归约方向和多项式性都要证 |
| 证明 NP 难 | 从已知 NP 难问题归约到目标 | 不要求目标在 NP |
| 证明属于 P | 构造多项式算法 | 注意输入长度,不是数值 |
| 设计近似 | 给出算法 + 比率证明 | 最小化/最大化比率方向不同 |
| 参数化 | 找小参数 k,设计 f(k)·poly(n) | k 不小时不适用 |
| 判伪多项式 | 检查复杂度是否含数值 W | O(nW) 不是多项式 |
3.3 标准流程
- 把问题写成判定问题:输入编码、阈值、输出 yes/no。
- 先找多项式算法;找不到再尝试证明 NP 难。
- 证 NP 完全:先给证书验证器,再从 3-SAT/团/顶点覆盖等已知问题归约。
- 检查归约:映射多项式时间可计算,答案双向保持。
- 分类后选策略并用边界实例测试:小 n 精确、可近似、可参数化、启发式;覆盖空实例、最小非平凡、对抗结构、大数值。
3.4 与相邻技术的组合
- 算法分析:复杂度分析判断一个具体算法;计算复杂性判断问题本身的下界/难度。
- 可计算性:先确认问题可判定,再谈 P/NP;不可判定问题不进入多项式讨论。
- 图算法:最短路在 P,哈密顿回路 NP 完全,TSP 是优化版 NP 难。
- SAT/ILP:把组合问题编码成 SAT/ILP,用工业求解器求精确解。
3.5 选型维度
| 维度 | 取值 | 影响 |
|---|---|---|
| n 的大小 | 小 / 中 / 大 | 精确 / 近似 / 启发式 |
| 是否必须最优 | 是 / 否 | 精确 vs 近似 |
| 误差容忍 | 有 / 无 | PTAS/近似 vs 精确 |
| 结构参数 | 小 / 大 | FPT vs 通用 |
| 实例来源 | 对抗 / 工业 | 最坏保证 vs 求解器 |
| 时间预算 | 严格 / 宽松 | 启发式 vs 精确 |
3.6 决策规则
- 问题在 P:用多项式算法,不要上指数级求解器。
- 问题 NP 难且 n 很小(≤ 30–40):精确指数/分支定界可能可行。
- 需要可证明的误差:近似算法/PTAS;先确认比率方向。
- 有小的结构参数 k:优先 FPT;k 大时 FPT 会退化成指数。
- 工业实例、可编码:SAT/ILP/CP 求解器往往比手写启发式强。
- 没有保证也能接受:启发式/局部搜索,但要明确“不保证最优”。
3.7 替代方案对比
| 方案 | 优势 | 代价 | 适用 |
|---|---|---|---|
| 精确指数 | 最优、实现直接 | 只能小 n | 小规模、必须精确 |
| 分支定界 | 平均远好于最坏 | 最坏指数、剪枝设计难 | 有结构、可剪枝 |
| 近似算法 | 多项式、有比率 | 不保证最优 | 大规模、可接受误差 |
| PTAS/FPTAS | 误差可控 | 实现复杂、常数大 | 需要 (1+ε) |
| FPT | 对 k 多项式 | k 大时爆炸 | 参数小的结构问题 |
| SAT/ILP | 工业级、精确 | 最坏指数、编码成本 | 组合优化 |
| 启发式 | 快、易实现 | 无保证 | 工程近似 |
3.8 何时不该用
- 还没证明 NP 难就放弃多项式算法:先尝试构造或查文献。
- 对 NP 难问题承诺通用多项式精确解:除非 P=NP,否则不成立。
- 用近似算法却不说明比率/方向:无法判断误差。
- 参数 k 可能很大却选 FPT:
2^k会直接爆炸。 - 把“NP 难”说成“不可解”:指数算法、近似、FPT 都是解。
4 边界
4.1 典型故障
| 症状 | 根因 | 处理 |
|---|---|---|
| 归约结论不成立 | 方向写反或映射不是多项式 | 检查 A ≤_p B 方向与构造 |
| 把 NP 难当成 NP 完全 | 忘了证明目标属于 NP | 补证书验证器 |
把 O(nW) 当多项式 | W 是数值,不是输入长度 | 以输入位数为 n 重新分析 |
| 近似比率方向错 | 最小化/最大化公式混用 | 统一用 max(ALG/OPT, OPT/ALG) |
| FPT 参数没界 | k 随 n 增长 | 选真正小的结构参数 |
| 启发式被当成有保证 | 没有最坏界 | 明确“无保证”,加基准 |
| SAT 求解器超时 | 实例大/编码差 | 改编码、加对称破除、限时 |
| 认为 NP 难 = 无解 | 混淆难度与可解性 | 指数/近似/FPT 都是路径 |
| 归约不是多项式 | 映射里做了指数搜索 | 证明映射复杂度 |
4.2 反模式
| 做法 | 后果 | 替代 |
|---|---|---|
| 一遇到难问题就称 NP 完全 | 结论无依据 | 先证 ∈ NP + 归约 |
| 用“指数”证明不可判定 | 混淆复杂度与可计算性 | 区分两类结论 |
| 只给近似算法不给比率 | 无法评估误差 | 证明近似比 |
| 用伪多项式 DP 处理大 W | 内存/时间爆炸 | 换 FPT/近似/分支定界 |
4.3 可观测信号
求解时间随 n 的增长曲线、SAT/ILP 的冲突数/分支数、近似解与下界的差距、FPT 的 k 实际分布、内存峰值。工程上要记录实例结构(密度、数值范围),否则“平均快”不可复现。
4.4 安全 / 性能 / 一致性边界
- 正确性:NP 难的结论依赖归约的正确性;归约错一步,整个分类失效。
- 性能:P 不等于实际快;多项式次数高或常数大仍可能不可用。
- 保证:近似比是最坏界,不是平均误差;启发式没有保证。
- 假设:P≠NP、FPT≠W[1]、ETH 都是未证明假设;结论要写明依赖。