TMSAT 说明 NP 完全问题存在,但它只是 NP 定义的改写。Cook–Levin 定理给出第一个「自然」的 NP 完全问题 SAT:图灵机的计算是局部的,因而可以用一个多项式大小的公式逐步「检查」。此后证明新问题 NP 完全,只需从 SAT 或它的后代归约,不必再碰图灵机。

1. 布尔公式与 SAT

1971 年前后,Cook 与 Levin 各自独立地提出 NP 完全性的概念,并给出了组合问题的例子;Karp(1972)随即说明 NP 完全性普遍存在,许多有实际意义的组合问题都是 NP 完全的。如今各学科中已有数千个问题被证明 NP 完全,而最简单的例子来自逻辑。

变量 u1,…,unu_1,\dots,u_n 上的布尔公式由变量与逻辑运算 ∧\wedge(与)、∨\vee(或)、¬\neg(非)构成。对 z∈{0,1}nz\in\{0,1\}^n,φ(z)\varphi(z) 表示变量取值为 zz 时 φ\varphi 的值(1 为真,0 为假)。若存在 zz 使 φ(z)=1\varphi(z)=1,称 φ\varphi 可满足,否则称其不可满足。

例如 (u1∨u2)∧(u2∨u3)∧(u3∨u1)(u_1\vee u_2)\wedge(u_2\vee u_3)\wedge(u_3\vee u_1) 为真当且仅当 u1,u2,u3u_1,u_2,u_3 中多数为真,它是可满足的。

文字是变量 uku_k 或其否定 uˉk\bar u_k。公式是合取范式(CNF),若它是若干子句(文字的析取)的合取:

φ=⋀i(⋁jvij).\varphi=\bigwedge_i\Big(\bigvee_j v_{ij}\Big).

若每个子句至多含 kk 个文字,称为 kkCNF。SAT 是全体可满足 CNF 公式构成的语言,3SAT 是全体可满足 3CNF 公式构成的语言。

SAT 与 3SAT 显然属于 NP:证书就是满足赋值,代入检查只需线性时间。

2. 定理与思路

  1. SAT 是 NP 完全的;
  2. 3SAT 是 NP 完全的。

要把任意 L∈NPL\in\mathrm{NP} 归约到 SAT,即给出多项式时间变换 x↦φxx\mapsto\varphi_x,使 x∈L  ⟺  φxx\in L\iff\varphi_x 可满足。困难在于,对 LL 我们一无所知,只知道它有一个多项式时间验证器 MM:

x∈L  ⟺  ∃u∈{0,1}p(∣x∣) such that M(x,u)=1.x\in L\iff\exists u\in\{0,1\}^{p(|x|)}\ \text{such that}\ M(x,u)=1.

于是 φx\varphi_x 的变量应当编码证书 uu 以及 MM 的整个计算过程,子句负责检查这个计算是合法的。为此需要两件工具:

表达能力:任何布尔函数都能写成 CNF(第 3 节),但一般需要指数大小,因此只能用于常数个变量的函数;

局部性:图灵机每一步只依赖常数个比特,但读写头的位置依赖于输入内容;借助健忘图灵机(第 4 节)使位置与内容无关,每一步便只是常数个变量之间的约束(第 5 节)。

3. 工具一:CNF 的普适性

对任意布尔函数 f:{0,1}l→{0,1}f:\{0,1\}^l\to\{0,1\},存在 ll 个变量、大小至多 l2ll2^l 的 CNF 公式 φ\varphi,使对任意 u∈{0,1}lu\in\{0,1\}^l 有 φ(u)=f(u)\varphi(u)=f(u)。这里公式的大小指其中 ∧/∨\wedge/\vee 符号的个数。

对每个 v∈{0,1}lv\in\{0,1\}^l,存在子句 Cv(z1,…,zl)C_v(z_1,\dots,z_l) 使 Cv(v)=0C_v(v)=0,而对任意 u≠vu\ne v 有 Cv(u)=1C_v(u)=1:令 vi=1v_i=1 时取文字 zˉi\bar z_i,vi=0v_i=0 时取 ziz_i,再取析取。例如 C010=z1∨zˉ2∨z3C_{010}=z_1\vee\bar z_2\vee z_3。

令 φ\varphi 为所有满足 f(v)=0f(v)=0 的 CvC_v 的合取,它至多有 2l2^l 个子句,大小至多 l2ll2^l。若 f(u)=0f(u)=0,则 CuC_u 出现在 φ\varphi 中且 Cu(u)=0C_u(u)=0,故 φ(u)=0\varphi(u)=0;若 f(u)=1f(u)=1,则对 φ\varphi 中的每个 CvC_v 有 v≠uv\ne u,从而 Cv(u)=1C_v(u)=1,故 φ(u)=1\varphi(u)=1。□\square

直接对 x↦M(x,⋅)x\mapsto M(x,\cdot) 应用此命题,公式大小可达 p(∣x∣)2p(∣x∣)p(|x|)2^{p(|x|)},归约就不是多项式的了。但当 ll 为常数时,l2ll2^l 也是常数。

例如异或 f(z1,z2)=z1⊕z2f(z_1,z_2)=z_1\oplus z_2 在 0000 与 1111 处为 00,按证明取 C00=z1∨z2C_{00}=z_1\vee z_2、C11=zˉ1∨zˉ2C_{11}=\bar z_1\vee\bar z_2,得 z1⊕z2=(z1∨z2)∧(zˉ1∨zˉ2)z_1\oplus z_2=(z_1\vee z_2)\wedge(\bar z_1\vee\bar z_2)。这个构造一般比最优的 CNF 大得多,但对某些函数,指数大小无法避免:

ll 个变量的奇偶校验函数 z1⊕⋯⊕zlz_1\oplus\cdots\oplus z_l 的任何 CNF 都至少有 2l−12^{l-1} 个子句。
设 φ\varphi 是它的 CNF,CC 是其中一个子句(不妨设没有永真的子句)。若 CC 不含变量 ziz_i,取一个使 CC 为假的赋值 vv,翻转 ziz_i 得到 v′v',C(v′)C(v') 仍为假;但 vv 与 v′v' 中有一个的奇偶校验值为 11,φ\varphi 在它上却为 00,矛盾。所以每个子句都含全部 ll 个变量,恰好在一个赋值上为假。而奇偶校验在 2l−12^{l-1} 个赋值上为 00,每个都要被某个子句「杀死」,故至少 2l−12^{l-1} 个子句。□\square

所以不能指望把整个验证器一次写成 CNF,只能把它切成常数规模的小块。引入新变量可以绕开这一障碍:用中间变量 sis_i 记录前 ii 位的奇偶校验值,约束 si=si−1⊕zis_i=s_{i-1}\oplus z_i 只涉及 33 个变量,各用 44 个子句写出,总大小就是线性的(代价是新公式多了变量,它与原函数不再逐点相等,而是「对新变量取存在」后相等,这对归约已经足够)。下面的快照变量 ziz_i 正是这样的中间变量,它们记录了计算的中间状态。

4. 工具二:健忘图灵机

图灵机 MM 是健忘的,若对任意输入 xx 与 i∈Ni\in\mathbb N,MM 的每个读写头在第 ii 步的位置只是 ∣x∣|x| 与 ii 的函数,与 xx 的内容无关。
任意图灵机 MM 都可被健忘图灵机 M′M' 模拟,使 MM 的 tt 步计算由 M′M' 的 O(t2)O(t^2) 步完成。

不妨设 MM 只有一条双向无限的纸带(由鲁棒性,这只带来多项式开销)。令 M′M' 的读写头按固定的「之字形」轨迹移动:

0,1,0,−1,−1,0,1,2,1,0,−1,−2,⋯ ,−(j−1),…,0,…,j,…,0,…,−j,⋯0,1,0,-1,\quad -1,0,1,2,1,0,-1,-2,\quad\cdots,\quad -(j-1),\dots,0,\dots,j,\dots,0,\dots,-j,\quad\cdots

第 jj 阶段从 −(j−1)-(j-1) 扫到 jj 再扫回 −j-j,约 4j4j 步,模拟 MM 的第 jj 步。MM 在 tt 步内的读写头位置不超出 [−(t−1),t−1][-(t-1),t-1],每个阶段都覆盖了 MM 当前可能用到的全部格子。

具体地,在 MM 的第 tt 步之前,M′M' 用标记记下区间端点 −(t−1)-(t-1)、t−1t-1 以及 MM 读写头的当前位置(字母表中加入带标记的符号)。第 tt 阶段:

  1. 从左端标记向右扫,遇到 MM 的读写头标记时,M′M' 由状态中保存的 qq 与读到的符号 aa 算出 δ(q,a)\delta(q,a),写入新符号、更新状态;若 MM 右移,则在下一步把读写头标记右移一格;若左移,则记住此事待回程时完成;
  2. 继续右扫找到右端标记,将其右移一格;
  3. 回扫到左端标记,途中完成待办的左移,最后将左端标记左移一格。

无论输入如何,读写头轨迹都相同,故 M′M' 是健忘的。tt 步共用时 4(1+2+⋯+t)=O(t2)4(1+2+\cdots+t)=O(t^2)。MM 停机时 M′M' 也停机并给出相同的结果。□\square

算法实现
\begin{algorithm}
\caption{Oblivious-Phase:健忘机 $M'$ 模拟 $M$ 的第 $t$ 步}
\begin{algorithmic}
\PROCEDURE{Phase}{$t$}
  \COMMENT{进入时读写头位于左端标记 $-(t-1)$,状态中保存 $M$ 的当前状态 $q$}
  \FOR{$i \gets -(t-1)$ \TO $t - 1$}
    \IF{格 $i$ 带有 $M$ 的读写头标记}
      \STATE 读出符号 $a$,$(q', b, d) \gets \delta(q, a)$,写入 $b$,$q \gets q'$
      \STATE 在状态中记下移动方向 $d$ \COMMENT{右移在下一格完成,左移留待回程}
    \ENDIF
    \STATE 右移一格
  \ENDFOR
  \STATE 将右端标记移到格 $t$
  \FOR{$i \gets t$ \DOWNTO $-(t-1)$}
    \STATE 如有待办的左移,在相应位置完成;左移一格
  \ENDFOR
  \STATE 将左端标记移到格 $-t$
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}
Fig 1 健忘机的之字形轨迹:第 $j$ 阶段覆盖 $[-j,j]$,在右扫途中模拟 $M$ 的第 $j$ 步
Fig 1 健忘机的之字形轨迹:第 jj 阶段覆盖 [−j,j][-j,j],在右扫途中模拟 MM 的第 jj 步

上一章的课后习题(若 L∈DTIME(T(n))L\in\mathrm{DTIME}(T(n)),则存在 O(T(n)2)O(T(n)^2) 时间的健忘图灵机判定 LL)即由此得到。用更精巧的模拟,开销可降到 O(Tlog⁡T)O(T\log T),思想与上一章通用图灵机的区段缓冲相同:那里的「纸带不动、内容搬运」恰好使读写头的轨迹与内容无关。

5. SAT 是 NP 完全的

设 L∈NPL\in\mathrm{NP},MM 是多项式时间验证器,pp 为证书长度。由前述各种模拟,不妨设:

MM 只有两条带:只读的输入带,以及兼作输出带的工作带;

MM 是健忘的:读写头的移动不依赖于纸带内容。

这些变换只带来多项式的开销。记 QQ 为 MM 的状态集,Γ\Gamma 为其字母表,T=T(n)T=T(n) 为 MM 在长为 n+p(n)n+p(n) 的输入上的运行步数。

MM 在输入 yy 上第 ii 步的快照是三元组 ⟨a,b,q⟩∈Γ×Γ×Q\langle a,b,q\rangle\in\Gamma\times\Gamma\times Q,其中 a,ba,b 是两个读写头读到的符号,qq 是第 ii 步时的状态。每个快照可以编码为长为 cc 的串 ziz_i,常数 cc 只依赖于 MM 的状态数与字母表大小,与输入长度无关。

再定义两个函数:inputpos(i)\mathrm{inputpos}(i) 为第 ii 步输入带读写头的位置;prev(i)\mathrm{prev}(i) 为第 ii 步之前,工作带读写头最后一次访问当前位置的步数(若此前从未访问,则约定读到空白符)。由于 MM 是健忘的,只需在任意一个长为 n+p(n)n+p(n) 的输入(如全 0 串)上模拟 MM 并记录读写头位置,即可在多项式时间内算出所有 inputpos(i)\mathrm{inputpos}(i) 与 prev(i)\mathrm{prev}(i)。

Fig 2 快照的局部性:$z_i$ 只依赖三处常数长度的信息
Fig 2 快照的局部性:ziz_i 只依赖三处常数长度的信息

存在只依赖于 MM 的函数 F:{0,1}2c+1→{0,1}cF:\{0,1\}^{2c+1}\to\{0,1\}^c,使

zi=F(zi−1, yinputpos(i), zprev(i)).z_i=F\big(z_{i-1},\ y_{\mathrm{inputpos}(i)},\ z_{\mathrm{prev}(i)}\big).
第 ii 步的快照由三部分组成:状态 qq 由第 i−1i-1 步的状态与读到的符号经转移函数决定,它们都在 zi−1z_{i-1} 中;输入带读到的符号是 yinputpos(i)y_{\mathrm{inputpos}(i)};工作带当前格的内容是第 prev(i)\mathrm{prev}(i) 步离开该格时写入的符号,它由 zprev(i)z_{\mathrm{prev}(i)}(那一步的状态与读到的符号)经转移函数决定。□\square

(SAT 是 NP 难的)快照序列完全决定了 MM 的计算结果。于是 x∈Lx\in L,当且仅当存在 y∈{0,1}n+p(n)y\in\{0,1\}^{n+p(n)} 与 z1,…,zT∈{0,1}cz_1,\dots,z_T\in\{0,1\}^c 同时满足:

  1. yy 的前 nn 位等于 xx;
  2. z1z_1 编码 MM 的初始快照 ⟨▹,□,qstart⟩\langle\triangleright,\square,q_{\mathrm{start}}\rangle;
  3. 对每个 i∈{2,…,T}i\in\{2,\dots,T\},zi=F(zi−1,yinputpos(i),zprev(i))z_i=F(z_{i-1},y_{\mathrm{inputpos}(i)},z_{\mathrm{prev}(i)});
  4. zTz_T 编码一个停机且输出 1 的快照。

φx\varphi_x 以 y∈{0,1}n+p(n)y\in\{0,1\}^{n+p(n)} 与 z∈{0,1}cTz\in\{0,1\}^{cT} 为变量,取为这四个条件的合取,则 x∈L  ⟺  φx∈SATx\in L\iff\varphi_x\in\mathrm{SAT}(yy 的后 p(n)p(n) 位就是证书 uu)。

大小:条件 1 是 nn 个单文字子句,大小 4n4n;条件 2、4 各只依赖于 cc 个变量,由 CNF 的普适性可写成大小 c2cc2^c 的 CNF;条件 3 是 TT 个条件的合取,每个只依赖于至多 3c+13c+1 个变量,可写成大小至多 T(3c+1)23c+1T(3c+1)2^{3c+1} 的 CNF。合起来大小为 d(n+T)d(n+T),dd 是只依赖于 MM 的常数。而由于 inputpos,prev\mathrm{inputpos},\mathrm{prev} 可在多项式时间内求出,φx\varphi_x 可在 MM 运行时间的多项式时间内构造。□\square

证明的要点在于:23c+12^{3c+1} 是指数的,但指数中的 cc 是常数;整个计算被切成 TT 个常数大小的局部检查,每个都可以暴力地写成 CNF。

另一种写法:计算表格

不借助健忘机也能证明(Sipser 教材的写法)。设 MM 是单带机,TT 步内只用到 TT 格。把 T+1T+1 个格局逐行写成一张 (T+1)×T(T+1)\times T 的表,每格存一个带符号,读写头所在的格再附上当前状态,取值只有常数种,用常数个布尔变量编码。由于每步只改动读写头附近,第 i+1i+1 行第 jj 格由第 ii 行第 j−1,j,j+1j-1,j,j+1 格决定,「表格是一次合法计算」就变成对每个 2×32\times3 窗口的常数大小约束,共 O(T2)O(T^2) 个;再加上「首行是初始格局」与「末行输出 1」,就得到大小 O(T2)O(T^2) 的公式。

两种写法的共同核心都是局部性:表格写法把它体现为「空间上的邻居」,健忘机写法把它体现为「时间上的前驱」zi−1,zprev(i)z_{i-1},z_{\mathrm{prev}(i)}。后者只为每一步设变量、不为每个格子设变量,配合 O(Tlog⁡T)O(T\log T) 的健忘模拟,公式大小可以做到 O(Tlog⁡T)O(T\log T),而表格写法本质上是 Θ(T2)\Theta(T^2) 的。

6. 3SAT 是 NP 完全的

SAT≤p3SAT\mathrm{SAT}\le_p\mathrm{3SAT}。

先看 4 个文字的子句,如 C=u1∨uˉ2∨uˉ3∨u4C=u_1\vee\bar u_2\vee\bar u_3\vee u_4。引入新变量 zz,将 CC 替换为两个子句

C1=u1∨uˉ2∨z,C2=uˉ3∨u4∨zˉ.C_1=u_1\vee\bar u_2\vee z,\qquad C_2=\bar u_3\vee u_4\vee\bar z.

若 CC 被满足:真文字在 C1C_1 中时取 z=0z=0,在 C2C_2 中时取 z=1z=1,两个子句都被满足;反之若 CC 为假,则 C1C_1 要求 z=1z=1,C2C_2 要求 z=0z=0,二者不能同时满足。

一般地,含 k>3k>3 个文字的子句 C=ℓ1∨⋯∨ℓkC=\ell_1\vee\cdots\vee\ell_k 可等价地替换为大小 k−1k-1 的 C1=ℓ1∨⋯∨ℓk−2∨zC_1=\ell_1\vee\cdots\vee\ell_{k-2}\vee z 与大小 33 的 C2=ℓk−1∨ℓk∨zˉC_2=\ell_{k-1}\vee\ell_k\vee\bar z(zz 为新变量)。反复应用,每个大小 kk 的子句变为 k−2k-2 个 3 子句,公式规模只线性增长,得到与原公式同时可满足的 3CNF。例如

ℓ1∨⋯∨ℓ5 ⟼ (ℓ1∨ℓ2∨z2)∧(ℓ3∨z1∨zˉ2)∧(ℓ4∨ℓ5∨zˉ1).\ell_1\vee\cdots\vee\ell_5\ \longmapsto\ (\ell_1\vee\ell_2\vee z_2)\wedge(\ell_3\vee z_1\vee\bar z_2)\wedge(\ell_4\vee\ell_5\vee\bar z_1).

新变量像一条链:若真文字是 ℓ3\ell_3,取 z2=1z_2=1、z1=0z_1=0,两端的子句由新变量满足;若所有 ℓi\ell_i 都为假,从左到右依次迫使 z2=1z_2=1、z1=1z_1=1,最后一个子句必然为假。□\square

算法实现
\begin{algorithm}
\caption{CNF-to-3CNF}
\begin{algorithmic}
\PROCEDURE{To3CNF}{$\varphi$}
  \STATE $\psi \gets$ 空公式
  \FORALL{$\varphi$ 中的子句 $C = \ell_1 \vee \cdots \vee \ell_k$}
    \WHILE{$k > 3$}
      \STATE 引入新变量 $z$
      \STATE 将 $\ell_{k-1} \vee \ell_k \vee \bar z$ 加入 $\psi$
      \STATE $C \gets \ell_1 \vee \cdots \vee \ell_{k-2} \vee z$,$k \gets k - 1$
    \ENDWHILE
    \STATE 将 $C$ 加入 $\psi$
  \ENDFOR
  \RETURN $\psi$
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

由 SAT 的 NP 难性与传递性,3SAT 也是 NP 难的;它属于 NP,故是 NP 完全的。Cook–Levin 定理证毕。

2SAT 属于 P

子句长度从 3 降到 2,问题就变得容易。每个子句 a∨ba\vee b 等价于两条蕴含 aˉ→b\bar a\to b 与 bˉ→a\bar b\to a,以 2n2n 个文字为顶点、蕴含为有向边建立蕴含图。可以证明:公式可满足当且仅当没有变量 uu 使 uu 与 uˉ\bar u 处于同一个强连通分量;且按强连通分量的拓扑序反向赋值即得满足赋值。强连通分量可在 O(m+n)O(m+n) 时间内求出(见稳定匹配与图)。上面的拆分之所以不能把 3 降为 2,是因为拆分 3 子句会得到一个 2 子句与另一个 3 子句,规模不降。

7. 再看 Cook–Levin 定理

规模:用 O(Tlog⁡T)O(T\log T) 的健忘模拟,φx\varphi_x 的大小与构造时间可以做到 O(Tlog⁡T)O(T\log T),其中 TT 是 MM 在 xx 上的步数;

证书可以双向转换:归约 ff 不仅满足 x∈L  ⟺  f(x)∈SATx\in L\iff f(x)\in\mathrm{SAT},证明还给出了把 xx 的证书高效转换为 f(x)f(x) 的满足赋值(填入 uu 并模拟出 zz)、以及反向转换(读出 yy 的后 p(n)p(n) 位)的方法。

若归约 ff 还附带多项式时间的映射,能把 xx 的证书转换为 f(x)f(x) 的证书、并把 f(x)f(x) 的证书转换回 xx 的证书,则称 ff 为 Levin 归约。

Levin 归约保证了「求解 SAT 的搜索版本」就足以求解任意 NP 问题的搜索版本,这将用于证明搜索与判定的等价性。

8. 第一个图论 NP 完全问题:独立集

INDSET={⟨G,k⟩:∃S⊆V(G), ∣S∣=k, ∀u,v∈S, (u,v)∉E(G)}\mathrm{INDSET}=\{\langle G,k\rangle:\exists S\subseteq V(G),\ |S|=k,\ \forall u,v\in S,\ (u,v)\notin E(G)\} 是 NP 完全的。

INDSET 属于 NP 已在上一章证明,下面给出 3SAT≤pINDSET\mathrm{3SAT}\le_p\mathrm{INDSET}。

设 φ\varphi 是 nn 个变量、mm 个子句的 3CNF 公式。构造 7m7m 个顶点的图 GG:

  • 每个子句对应一个由 7 个顶点组成的簇,每个顶点对应该子句所含三个变量的一个满足此子句的部分赋值(三个变量共 23=82^3=8 种赋值,恰有一种使子句为假);
  • 同一簇内的任意两个顶点之间连边;
  • 若两个顶点对应的部分赋值不相容(对某个公共变量赋了不同的值),则在它们之间连边。

令 k=mk=m。GG 可在多项式时间内构造。下证 φ\varphi 可满足   ⟺  \iff GG 有大小为 mm 的独立集。

(⇒\Rightarrow)设 uu 是满足赋值。对每个子句 CC,uu 在 CC 的三个变量上的限制满足 CC,取簇中对应的顶点放入 SS。SS 中的点来自不同的簇,且都是同一个 uu 的限制,两两相容,故 SS 是大小为 mm 的独立集。

(⇐\Leftarrow)设 SS 是大小为 mm 的独立集。簇内两两相连,故 SS 在每个簇中至多一个点;共 mm 个簇,于是每个簇恰有一个点。对每个 i∈[n]i\in[n],若 SS 中某个点的部分赋值给 uiu_i 赋值 aa,则令 ui=au_i=a(其余变量任意);由于不相容的点之间有边,每个 uiu_i 至多得到一个值,赋值是良定义的。每个子句所在簇中的那个点是一个满足该子句的部分赋值,且与 uu 一致,故 uu 满足 φ\varphi 的全部子句。□\square

若某个子句只含 r<3r<3 个变量,相应的簇有 2r−12^r-1 个顶点,论证不变。这个证明体现了归约的典型结构:部件(gadget)模拟原问题的局部结构(簇 = 子句的选择),一致性约束(不相容边)把局部选择粘合成全局解。

三顶点版本

另一种常见构造(Kleinberg–Tardos):每个子句对应一个三角形,三个顶点分别对应子句的三个文字;再在每对互补文字 uiu_i 与 uˉi\bar u_i 对应的顶点之间连边,取 k=mk=m。独立集从每个三角形中选一个文字令其为真,互补边保证不会同时选中 uiu_i 与 uˉi\bar u_i。

9. 小结

结论归约关键
SAT 是 NP 完全的任意 L∈NP≤pSATL\in\mathrm{NP}\le_p\mathrm{SAT}健忘机 + 快照的局部性 + 常数变量函数的 CNF
3SAT 是 NP 完全的SAT≤p3SAT\mathrm{SAT}\le_p\mathrm{3SAT}用新变量拆分长子句
INDSET 是 NP 完全的3SAT≤pINDSET\mathrm{3SAT}\le_p\mathrm{INDSET}子句簇 + 不相容边

Cook–Levin 定理是唯一一次需要直接面对「任意 NP 语言」的证明:它的核心是计算的局部性,图灵机每一步只改动常数个比特,于是整个计算可以由多项式个常数规模的约束刻画。从此 SAT 取代了图灵机,成为证明 NP 完全性的起点;下一章沿归约链继续扩展,得到哈密顿路、集合覆盖、子集和等一大批 NP 完全问题,见NP 完全问题。