P、NP 与归约

复杂度理论的第一组核心问题：P 与 NP、多项式时间归约、NP 完全性。本章讲定义、Cook–Levin 定理、经典 NP 完全问题，以及"如何用归约证明一个新问题是 NP 完全的"（直觉版见渐近复杂度与主定理，实践版见NP 完全问题与近似算法）。

P 与 NP

P：确定性图灵机多项式时间可解的判定问题类——"能高效求解"；
NP：多项式时间可验证的判定问题类——证书（证据）存在时能高效验证。"给你一个答案，我能不能快速检查它是对的？"

NP 是"可高效验证"，不是"不确定"（non-deterministic 只是技术名称）：SAT 的"证书"是一组变量赋值，验证一个赋值满足所有子句是多项式的。

$P \subseteq NP$ （能解就能验证）；P = NP 吗？——P vs NP 是理论计算机科学最重要的开放问题，直觉答案是否（验证似乎严格容易），但八十年没有证明。多数人相信 $P \neq NP$ ，全部现代密码学（→ 公钥密码与密钥交换）建立在它之上。

多项式时间归约

归约 $A \le_p B$ ：把 A 的实例多项式时间转换成 B 的实例，答案保持——"B 不比 A 难"。

方向的纪律： $A \le_p B$ 读作"A 归约到 B"，含义是 B 至少与 A 一样难。

证明 B 难：把已知的难问题 $A \le_p B$ ——从已知难问题归约到新问题；
证明 B 易：把 B $\le_p$ 已知易问题。

归约方向是常见错误：把新问题归约到 SAT 只证明"你的问题不比 SAT 难"（什么都得不到）——正确方向是从 SAT 归约到你的新问题。

NP 完全性

NP 完全：既属于 NP，又是 NP 难（NP 中所有问题都 $\le_p$ 它）。任一 NP 完全问题有多项式算法 ⇒ P = NP。

Cook–Levin 定理（1971）：SAT 是 NP 完全的——第一个。证明思路：把"图灵机在 $T$ 步内接受"编码成 SAT 公式（计算历史的表格化）——**"计算本身可以编码成布尔公式"**是它的深刻内容。

归约链（Karp 1972 的 21 个问题）：SAT → 3-SAT → 团 → 顶点覆盖 → 独立集、3-SAT → 3-着色、哈密顿回路 → TSP（判定版）、3-SAT → 子集和 → 背包……经典 NP 完全问题几乎覆盖所有组合结构——归约链上任何一个都够用。

如何证明新问题 NP 完全

三步法：

证明属于 NP：给出证书 + 多项式验证；
选一个已知 NP 完全问题（结构最像的：图问题选 3-SAT/团/顶点覆盖，数值选子集和，调度选 3-划分）；
构造归约：把已知实例转换成新问题实例，双向证明（有解 ⇔ 有解）。

例子：证明顶点覆盖 NP 完全——证书是一组顶点（验证覆盖所有边是多项式）；从 3-SAT 归约（每个子句造三角形，选点 = 赋值）。归约的构造是艺术：找"结构对应"（赋值 ↔ 选点）。

实践含义

理论的最坏界与实践的实例差距巨大：SAT/ILP 求解器日常解决"NP 完全"的百万变量实例（→ NP 完全问题与近似算法）；
识别比解决重要：拿到优化问题先判断"是不是 NP 完全"——是的话换策略（近似/参数化/求解器），别在指数算法上浪费时间；
伪多项式的陷阱：背包 $O(nC)$ 可解——数值小的时候"NP 完全"实际能解（位数 vs 数值，→ 渐近复杂度与主定理）。

本章要点

NP 是"可高效验证"，不是"不确定"；P ⊆ NP，P = NP 是最重要的开放问题
归约 $A \le_p B$ 意为 B 至少与 A 一样难；归约方向是常见错误
Cook–Levin：SAT 是 NP 完全的——计算历史可编码成布尔公式
Karp 归约链覆盖经典 NP 完全问题；三步法证明新问题：属于 NP → 选已知 → 构造归约
最坏界与实践差距巨大：识别 NP 完全后换策略，别硬解