P、NP 与归约
P 与 NP 的定义、多项式时间归约、NP 完全性与 Cook–Levin 定理、经典 NP 完全问题（SAT、3-SAT、团、顶点覆盖、哈密顿回路）。本章讲如何用归约证明一个新问题是 NP 完全的。
- NP 是”可高效验证”，不是”不确定”
- 归约方向是常见错误：从已知难问题归约到新问题
- P vs NP 是理论计算机科学最重要的开放问题
P 与 NP 的定义、多项式时间归约、NP 完全性与 Cook–Levin 定理、经典 NP 完全问题（SAT、3-SAT、团、顶点覆盖、哈密顿回路）。本章讲如何用归约证明一个新问题是 NP 完全的。