4.3 P、NP 与归约：可计算之后还要问算得动吗

不可判定问题没有覆盖所有困难任务。寄存器分配、指令调度和组合优化通常存在穷举算法，因而可以判定；真正麻烦的是候选数量随输入迅速增长，精确最优解可能来不及算完。

本课目标

• 区分可判定性与复杂度；
• 用判定问题定义 P 和 NP；
• 区分 NP-hard 与 NP-complete；
• 理解编译器为什么采用启发式、近似和受限精确算法。

1. 复杂度必须先规定输入规模

算法复杂度描述资源随输入长度 $n$ 的增长。输入长度是编码后的符号或比特数，不一定等于业务对象的数值。

例如正整数 $N$ 的二进制编码长度为 $\lfloor {\log }_{2}N\rfloor +1$。一个运行 $N$ 步的算法，相对于数值看似线性，相对于输入位数却是指数级。

复杂度分析还要说明：

• 最坏、平均还是摊还情况；
• 时间还是空间；
• 计算模型和基本操作；
• 参数是否作为输入的一部分。

2. P：多项式时间可判定

P 是能由确定性图灵机在输入长度的多项式时间内判定的语言类：

$$P=\bigcup _{k\ge 1}TIME(n^k).$$

P 常被当作“理论上可行”的粗略边界，但多项式不等于实际快速：$n^{100}$ 无法接受，输入巨大时 $n^3$ 也可能太慢。相反，小规模实例的指数算法可能完全可用。

P 的价值是对计算模型和常数因素相对稳健，并且对算法组合有良好封闭性，不是生产延迟的直接承诺。

3. NP：证书可在多项式时间验证

NP 中的判定问题有一个多项式时间验证器：每个 yes 实例都有一个长度受输入规模的某个多项式限制、能被接受的证书；每个 no 实例都没有能被接受的证书。第二半不能省略，否则“把所有证书都判对”的验证器也会混进来。

等价地，NP 是非确定性图灵机多项式时间可判定的语言类。这里的“非确定性”是数学模型，不是随机算法。

以旅行商判定版为例：

输入：边权与阈值 K 均以二进制编码的非负整数带权图
问题：是否存在一条访问每个顶点一次并回到起点、总权重 ≤ K 的路线？

证书是一条候选路线。验证顶点是否恰好访问一次、路线使用的边是否存在，并计算总权重，可以在多项式时间完成。

旅行商“找最短路线”是优化问题。谈 NP-complete 时通常先转成上述判定版本；优化版常称 NP-hard，并可通过多次判定或其他技术联系起来。

显然 $P\subseteq NP$：若能快速求解，当然能快速验证。是否 $P=NP$ 仍未解决。

4. 多项式时间归约

若判定问题 $A$ 的实例能在多项式时间转成 $B$ 的实例，并保持答案：

$$x\in A⟺f(x)\in B,$$

记作 $A{\le }_{p}B$。若有 $B$ 的多项式算法，就能先转换再解出 $A$。

• $B$ 是 NP-hard：每个 NP 问题都可多项式归约到 $B$；
• $B$ 是 NP-complete：$B$ 同时属于 NP 且 NP-hard。

要证明新问题 NP-complete，通常需要两部分：

1. 给出多项式验证器，证明它在 NP 中；
2. 从一个已知 NP-complete 问题归约到它，证明 NP-hard。

只证明“它能归约到 SAT”说明它不比 SAT 更难，不能证明 NP-hard。

5. SAT 为什么居于核心位置

布尔可满足性问题 SAT 问：是否存在变量赋值使布尔公式为真。Cook–Levin 定理证明 SAT 是 NP-complete：任意多项式时间验证过程都能编码成多项式大小的布尔公式。

SAT 求解器在许多实际实例上表现很好，但 NP-complete 结论是最坏情况分类，不代表每个实例都难。结构化输入、预处理、冲突学习和启发式分支可以解决大批现实问题，同时仍存在困难实例族。

6. 编译器中的组合困难

寄存器分配

用变量活跃范围的冲突关系构图后，理想化的 $k$ 寄存器可分配性对应图 $k$-着色。对一般图，固定 $k\ge 3$ 的判定是 NP-complete；$k=2$ 则可用二分图检查解决。生产编译器会使用图简化、合并、溢出启发式或线性扫描。

不要把所有冲突图都理解成区间图。若模型确实限制为一条线上的活跃区间，区间图着色可以多项式求解；一般控制流下的活跃范围及机器约束不能直接套用这个结论。

真实目标还包括调用约定、寄存器类别、固定寄存器和指令约束，不等于教科书的一张普通图。理论归约揭示核心困难，工程模型仍更复杂。

指令调度

需要在数据依赖、功能单元和延迟约束下排列指令。许多一般形式是 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 等于实际快速：同属 P 的算法仍可有不同的固定多项式次数、常数和硬件开销。

参考资料

• Clay Mathematics Institute：P vs NP

练习

1. 把“找一个大小最大的团”改写成判定问题，并指出证书。
2. 说明证明问题 $B$ NP-complete 时归约应该从已知难问题到 $B$，还是反过来。
3. 为寄存器不足时的溢出选择提出一个启发式，并说明可能失败的案例。
4. 给一个属于 P 但在实际规模上仍可能昂贵的算法例子。

小结

可判定性问算法是否存在，复杂度问资源怎样增长。P 表示多项式时间可判定，NP 表示 yes 证书可多项式验证；NP-complete 同时属于 NP 且承载整个 NP 的困难性。编译器面对组合困难时会利用结构、近似、启发式和精确求解器，而不是追求不存在的万能策略。

理论部分到这里形成完整阶梯：有限状态、栈、图灵机、不可判定性与复杂度。下一章回到工程现场，从字符流中稳定地产生 token。