P vs NP · verifier · Cook–Levin

判定问题与 NP-complete

站内十几页正文写着同一句话：这个问题是 NP-hard。精确解：回溯、剪枝与对称据此改去剪搜索树，分支限界的拆解据此改去算乐观上界，多重子集和据此改去做整数化加剪枝。这句话本身却从未被展开过。图灵完备划出的是「算不算得出来」那条线，本页要划的是线内的第二条线：算得出来的问题里，哪些算得快。

1 · 判定问题与优化问题的改写

同一个问题通常有三种问法。以 vertex cover 为例：给一张图，求一个最小的点集使每条边至少有一端落在里面（求解版）；这个最小点集有多大（求值版）；有没有大小不超过 $k$ 的这样的点集（判定版）。三者的答案分别是一个集合、一个整数、一个是或否。

复杂度理论只给判定版建类。理由不是判定版更常用，而是「答案只有两种」让问题退化成一个字符串集合：所有该答「是」的输入构成一个语言，一台机器解不解得了这个问题，就是它认不认得这个语言。求解版的输出五花八门，没有这种统一形式。

改写不会把问题变简单。求值版可以靠反复调用判定版得到： $k$ 从 $0$ 试到点数，第一个答「是」的位置就是最小值；把线性扫换成二分，调用次数降到 $O(\log n)$ 次。判定版若有多项式算法，求值版也就有。反过来更直接，最小值算出来了，判定只是一次比较。这层等价是后面所有讨论的前提：谈判定版的难度，等于谈原问题的难度。

注 · 站内已有一页在做同一件改写。精确解：回溯、剪枝与对称 §1 把「求色数 $\chi$ 」拆成一串「 $k$ 种颜色够不够」，理由与本节一致：回溯框架只会答是或否，优化问题必须先落到判定形式才能套进去。

图 1-1 · 同一张图上，判定问题在各个阈值

k

上的答案组成一条单调的是否带，翻转点就是最优值。可拖动

k

，也可单击顶点自行拼一个候选点集，结论条会核对它是否盖住每条边。

2 · P 与 NP

定义 2.1（P） 存在一台确定性机器，对每个输入都在输入规模的多项式时间内给出正确的是否答案，这样的判定问题构成类 P。

定义 2.2（NP） 判定问题属于 NP，若存在一个多项式时间的 verifier：对每个该答「是」的输入，存在一份长度为多项式的 certificate，verifier 读入两者后接受；对该答「否」的输入，任何 certificate 都不能让它接受。

定义 2.2 常被写成另一副样子：非确定图灵机在多项式时间内接受。两个定义等价：非确定机的一条接受路径就是一份 certificate，反过来 verifier 的 certificate 就是猜测的内容。但 verifier 版好用得多，因为它把「难」拆成了一件可以分别掂量的事：找解要搜多久，与验解要花多久，是两个独立的量。SAT 的 certificate 是一份 assignment，验它只需按 clause 扫一遍。

certificate 只对「是」这一侧有效，这个不对称是定义里最容易读漏的一处，§3 会回到它。

图 2-1 · 暴力 solver 逐个展开 assignment，与 verifier 核对同一份 certificate 的工作量对照。两条读数条同以 literal 取值次数计量，可换成不可满足的实例观察 solver 走完整个空间。

本页那个可满足实例上的实测：搜索空间 $32$ 个 assignment，第一个解落在第 $26$ 个位置，solver 花掉 $246$ 次 literal 取值；verifier 拿到同一份 assignment， $10$ 个 clause 扫完只用 $16$ 次，差 $15$ 倍。这个实例是搜出来的，不是随手写的。第一版写了 $7$ 个 clause，解落在第 $6$ 个位置，solver 只用 $32$ 次取值、verifier 用 $12$ 次，两条读数条几乎一样长，「解难找」这句话在图上完全看不出来。小实例里指数与多项式的差距还没拉开，得刻意把解推到枚举序的靠后位置，读数才说得出话。

P 是 NP 的子集，这一步没有难度：一个多项式时间就能自己算出答案的问题，其 verifier 把 certificate 丢掉、自己重算一遍即可。反向的包含关系（NP 里的每个问题是否都有多项式算法）至今没有答案，这就是 P $=$ NP 问题。

3 · 「否」这一侧的不对称

NP 的定义只保证「是」有短 certificate。SAT 答「是」时交出一份 assignment，谁都能在几十次比较里核对完；答「否」时要交出什么？「我试遍了全部 $2^n$ 个 assignment」不是一份短 certificate，它的长度本身就是指数的。

把 NP 里每个问题的是否两侧对调，得到的类叫 co-NP：它收的是那些「否」有短 certificate 的问题。UNSAT（判定一个 CNF 不可满足）落在 co-NP 里，却不知道它在不在 NP 里。本页那个不可满足的实例上，solver 必须把 $8$ 个 assignment 全部走完才敢下结论，这正是「否」缺少 certificate 的现场：结论不是从某个证据读出来的，而是从「没有反例」推出来的，而「没有反例」只能靠穷举来说。

这条不对称与图灵完备 §2 的停机问题有形式上的相似：那里「会停」可以靠跑一遍来证实，「不会停」却无法在有限步内证实。两者的差别在于层级——停机问题连有限步都做不到，是不可判定；UNSAT 是可判定的，只是没人知道怎么把「否」的理由压缩到多项式长度。

4 · NP-hard 与 NP-complete

这两个词在工程语境里几乎被当成同义词用，实际它们说的是两件事。

定义 4.1（NP-hard 与 NP-complete） 问题 $B$ 是 NP-hard 的，若 NP 里的每一个问题都能在多项式时间内归约到 $B$ ； $B$ 是 NP-complete 的，若它既是 NP-hard 的，又本身属于 NP。

NP-hard 是一个下界断言： $B$ 至少和 NP 里最难的问题一样难。它不要求 $B$ 属于 NP，也不要求 $B$ 是判定问题。三类容易被混起来的情形对照如下：

问题	NP-hard	属于 NP	NP-complete
SAT · 判定一个 CNF 可满足	是	是	是
TSP · 求最短回路（求解版）	是	不适用，它不是判定问题	否
停机问题	是	否，它连可判定都不是	否

站内各页写「这是 NP-hard」时，指的几乎都是中间那一栏的情形：手上是一个优化问题，它的判定版是 NP-complete，于是优化版至少一样难。措辞用 NP-hard 是准确的——优化版本来就不是判定问题，套不上 NP-complete 这顶帽子。

警示 · 「NP-complete 所以没有多项式算法」这句话每天都在被说，但它不是定理。已知的只有：若 P $\ne$ NP，则 NP-complete 问题没有多项式算法。P $=$ NP 尚未被排除，一旦成立，全部 NP-complete 问题同时坍缩进 P。工程上把 NP-complete 当作「别再找多项式算法了」的信号是合理的，把它当作已被证明的不可能则不是。

5 · Cook–Levin 定理与第一块砖

定义 4.1 有个循环味道：要证明某个问题 NP-hard，得让 NP 里每一个问题都归约到它。NP 里有无穷多个问题，逐个归约不可能。

Cook 与 Levin 在 1971 年前后各自独立地把第一块砖砌上了：SAT 是 NP-complete [1]。定理断言的是，对 NP 里任意一个问题，都能构造出一个多项式时间的翻译过程，把它的实例变成一个 CNF，使得原实例答「是」当且仅当那个 CNF 可满足。

证明的路子说起来只有一句：NP 里的问题都有一个多项式时间的 verifier，而 verifier 就是一台运行时间有限的机器；把这台机器的整段计算过程（每一时刻每一格纸带上写着什么、读写头在哪、处于哪个状态）全部用布尔变量记下来，再用 clause 把「相邻两个时刻之间必须合法转移」写成约束，这个 CNF 可满足当且仅当存在一份让 verifier 接受的 certificate。构造细节不在本页展开，重要的是它把一件无穷的事变成了有穷的一步。

有了这块砖，后续的证明就不必再回到定义：要证明新问题 NP-hard，只需把一个已知 NP-hard 的问题归约到它。归约链怎么搭、方向为什么容易搞反，是归约：把难度从一个问题搬到另一个的内容；而被证明为 NP-hard 之后还能拿到什么，见近似算法与不可近似性。

6 · 参考文献

Cook, S. A. (1971). The complexity of theorem-proving procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing, 151–158.
Levin, L. A. (1973). Universal sequential search problems. Problems of Information Transmission, 9(3), 265–266.
Karp, R. M. (1972). Reducibility among combinatorial problems. In R. E. Miller & J. W. Thatcher (Eds.), Complexity of Computer Computations, 85–103. Plenum Press.