4.3 P、NP 与归约：可计算之后还要问算得动吗
不可判定问题没有覆盖所有困难任务。寄存器分配、指令调度和组合优化通常存在穷举算法，因而可以判定；真正麻烦的是候选数量随输入迅速增长，精确最优解可能来不及算完。
本课目标
- 区分可判定性与复杂度；
- 用判定问题定义 P 和 NP；
- 区分 NP-hard 与 NP-complete；
- 理解编译器为什么采用启发式、近似和受限精确算法。
1. 复杂度必须先规定输入规模
算法复杂度描述资源随输入长度 $n$ 的增长。输入长度是编码后的符号或比特数，不一定等于业务对象的数值。
例如整数 $N$ 的二进制编码长度约为 $\log_2N$。一个运行 $N$ 步的算法，相对于数值看似线性，相对于输入位数却是指数级。
复杂度分析还要说明：
- 最坏、平均还是摊还情况；
- 时间还是空间；
- 计算模型和基本操作；
- 参数是否作为输入的一部分。
2. P：多项式时间可判定
P 是能由确定性图灵机在输入长度的多项式时间内判定的语言类：
$$ P=\bigcup_{k\ge1}TIME(n^k). $$
P 常被当作“理论上可行”的粗略边界，但多项式不等于实际快速：$n^{100}$ 无法接受，输入巨大时 $n^3$ 也可能太慢。相反，小规模实例的指数算法可能完全可用。
P 的价值是对计算模型和常数因素相对稳健，并且对算法组合有良好封闭性，不是生产延迟的直接承诺。
3. NP：证书可在多项式时间验证
NP 中的判定问题满足：对每个 yes 实例，存在长度为多项式的证书，可由确定性算法在多项式时间验证。
等价地，NP 是非确定性图灵机多项式时间可判定的语言类。这里的“非确定性”是数学模型，不是随机算法。
以旅行商判定版为例：
输入：带权图和阈值 K
问题：是否存在一条访问每个顶点一次并回到起点、总权重 ≤ K 的路线？证书是一条候选路线。验证顶点是否恰好访问一次并计算总权重，可以在多项式时间完成。
旅行商“找最短路线”是优化问题。谈 NP-complete 时通常先转成上述判定版本；优化版常称 NP-hard，并可通过多次判定或其他技术联系起来。
显然 $P\subseteq NP$：若能快速求解，当然能快速验证。是否 $P=NP$ 仍未解决。
4. 多项式时间归约
若判定问题 $A$ 的实例能在多项式时间转成 $B$ 的实例，并保持答案：
$$ x\in A\iff f(x)\in B, $$
记作 $A\le_p B$。若有 $B$ 的多项式算法，就能先转换再解出 $A$。
- $B$ 是 NP-hard：每个 NP 问题都可多项式归约到 $B$；
- $B$ 是 NP-complete：$B$ 同时属于 NP 且 NP-hard。
要证明新问题 NP-complete，通常需要两部分：
- 给出多项式验证器，证明它在 NP 中；
- 从一个已知 NP-complete 问题归约到它，证明 NP-hard。
只证明“它能归约到 SAT”说明它不比 SAT 更难，不能证明 NP-hard。
5. SAT 为什么居于核心位置
布尔可满足性问题 SAT 问：是否存在变量赋值使布尔公式为真。Cook–Levin 定理证明 SAT 是 NP-complete：任意多项式时间验证过程都能编码成多项式大小的布尔公式。
SAT 求解器在许多实际实例上表现很好，但 NP-complete 结论是最坏情况分类，不代表每个实例都难。结构化输入、预处理、冲突学习和启发式分支可以解决大批现实问题，同时仍存在困难实例族。
6. 编译器中的组合困难
寄存器分配
将变量活跃区间构成冲突图后，理想化的 $k$ 寄存器可分配性对应图 $k$-着色。一般图着色判定是 NP-complete，因此生产编译器常使用图简化、合并、溢出启发式或线性扫描。
真实目标还包括调用约定、寄存器类别、固定寄存器和指令约束，不等于教科书的一张普通图。理论归约揭示核心困难，工程模型仍更复杂。
指令调度
需要在数据依赖、功能单元和延迟约束下排列指令。许多一般形式是 NP-hard，编译器会使用列表调度、局部搜索或限制调度窗口。
指令选择与优化组合
局部树模式可用动态规划高效选择；加入 DAG 共享、复杂机器约束和跨块组合后，某些形式会变难。不能笼统说“代码优化都是 NP-hard”，应明确问题定义和约束。
7. 面对 NP-hard 问题的工具箱
- 限制问题结构：利用树宽、区间图或固定目标架构性质；
- 参数化算法：对小参数 $k$ 做 $f(k)n^{O(1)}$ 计算；
- 近似算法：给出与最优值的可证明差距；
- 启发式：追求实际质量，无统一最坏保证；
- 精确求解器：ILP、SAT、SMT、动态规划或分支定界；
- 混合策略：热路径精确求解，其余使用快速启发式；
- 时间预算：超时返回当前最好解。
“NP-hard 所以只能瞎猜”是错误结论。输入结构、实例规模和目标质量决定该用哪种方法。
8. 三条边界不要混在一起
| 问题 | 关注点 | 典型结论 |
|---|---|---|
| 可计算性 | 是否存在总能给答案的算法 | 可判定 / 不可判定 |
| 复杂度 | 算法资源如何随输入增长 | P、NP、PSPACE 等 |
| 工程性能 | 在具体硬件与数据上是否满足预算 | 延迟、吞吐、内存、能耗 |
一个问题可以可判定但最坏情况昂贵；也可以属于 P 却因常数和规模不实用；还可以理论最坏很难，但现实实例由优秀启发式快速解决。
常见误区
- NP 表示非多项式时间：NP 是多项式时间可验证，不是“not polynomial”。
- NP-hard 问题都属于 NP：优化问题甚至不可判定问题也可能被称为至少 NP-hard；NP-complete 才要求属于 NP。
- 能快速验证数值最优性就等于能快速验证候选可行：优化最优性的证书可能更复杂。
- P 等于实际快速：复杂度类忽略常数、指数和硬件细节。
练习
- 把“找一个大小最大的团”改写成判定问题，并指出证书。
- 说明证明问题 $B$ NP-complete 时归约应该从已知难问题到 $B$，还是反过来。
- 为寄存器不足时的溢出选择提出一个启发式，并说明可能失败的案例。
- 给一个属于 P 但在实际规模上仍可能昂贵的算法例子。
小结
可判定性问算法是否存在，复杂度问资源怎样增长。P 表示多项式时间可判定，NP 表示 yes 证书可多项式验证；NP-complete 同时属于 NP 且承载整个 NP 的困难性。编译器面对组合困难时会利用结构、近似、启发式和精确求解器，而不是追求不存在的万能策略。
理论部分到这里形成完整阶梯：有限状态、栈、图灵机、不可判定性与复杂度。下一章回到工程现场，从字符流中稳定地产生 token。