NP 完全性 · 判定、归约与近似

图灵完备 划的是「算不算得出来」这条线：停机问题落在线外，其余都落在线内。线内还有第二条线——算得出来与在可接受的时间内算得出来。一个 30 个点的图着色实例，判定它能否用 3 种颜色着色，理论上一定有答案；把点数抬到 300，同一段程序就得跑到宇宙热寂。这第二条线由 P 与 NP 两个类划出，本系列讲的是它的画法、证法与绕法。

三页依次是：判定问题与 P / NP / co-NP 的定义，以及 NP-hard 与 NP-complete 这对常被混用的概念；多项式时间归约的方向与一条完整的归约链；以及被证明为 NP-hard 之后仍能拿到的东西——带证明的近似算法。每页的构造与算法都预先展开成帧序列，可单步、可回退、可就地改实例。

P vs NP · verifier · Cook–Levin

判定问题与 NP-complete

优化问题先改写成只答是或否的判定形式，类才好定义。NP 是「解不好找、给了解好验」的类；NP-hard 说的是难度下界，NP-complete 是它与 NP 的交集，Cook–Levin 给出第一个成员。

3-SAT · gadget · Karp 链

归约：把难度搬到新问题上

多项式时间归约的方向决定结论：把已知难的问题归约到新问题，证明的是新问题难。沿 SAT → 3-SAT → independent set → vertex cover → clique 走一条完整的链，每一步都对着具体实例看解怎么搬。

2-approximation · Christofides · FPTAS

近似算法与不可近似性

NP-hard 之后仍能拿到带证明的次优解：vertex cover 的 2-approximation、metric TSP 的 Christofides、subset sum 的 FPTAS，以及一般 TSP 连常数比都拿不到的边界。

这套判据在站内什么地方被用到

「NP-hard」这个断言在全站十余页里充当同一个角色：放弃找多项式算法的许可证。精确解：回溯、剪枝与对称 因此改去剪搜索树，分支限界的拆解 因此改去算乐观上界，多重子集和 因此改去做整数化加剪枝。反方向的例子同样重要：建模与归约：把问题翻译成网络流 把问题归约到 max-flow，那是归约到一个 P 里的问题，得到的是一个多项式算法而不是一条难度证明。同一件工具，方向一反，结论就反。

相关链接

• 图灵完备 · 从一条纸带到「万物皆可计算」 本站 可计算与不可计算的分界，以及停机问题。本系列接着往下切：可计算的那一侧再分出「可行」与「不可行」。
• 精确解：回溯、剪枝与对称 本站 把优化问题拆成一串判定、再对判定做回溯，是本系列 §1 那套写法的实例。
• 建模与归约：把问题翻译成网络流 本站 归约到 P 里的问题：同样的翻译动作，方向朝下，产出的是算法而非难度证明。
• Cook (1971) — The complexity of theorem-proving procedures doi.org 第一个 NP-complete 问题的出处：任何 NP 里的问题都能多项式时间归约到 SAT。
• Karp (1972) — Reducibility among combinatorial problems doi.org 21 个经典问题的归约网，本系列第二页走的那条链即出自其中。
• Håstad (1999) — Some optimal inapproximability results doi.org 不可近似性的代表结果：若 P ≠ NP，MAX-3SAT 的近似比不可能优于 7/8。