TMSAT 说明 NP 完全问题存在,但它只是 NP 定义的改写。Cook–Levin 定理给出第一个「自然」的 NP 完全问题 SAT:图灵机的计算是局部 的,因而可以用一个多项式大小的公式逐步「检查」。此后证明新问题 NP 完全,只需从 SAT 或它的后代归约,不必再碰图灵机。
1. 布尔公式与 SAT# 1971 年前后,Cook 与 Levin 各自独立地提出 NP 完全性的概念,并给出了组合问题的例子;Karp(1972)随即说明 NP 完全性普遍存在,许多有实际意义的组合问题都是 NP 完全的。如今各学科中已有数千个问题被证明 NP 完全,而最简单的例子来自逻辑。
变量 u 1 , … , u n u_1,\dots,u_n u 1 , … , u n 上的布尔公式 由变量与逻辑运算 ∧ \wedge ∧ (与)、∨ \vee ∨ (或)、¬ \neg ¬ (非)构成。对 z ∈ { 0 , 1 } n z\in\{0,1\}^n z ∈ { 0 , 1 } n ,φ ( z ) \varphi(z) φ ( z ) 表示变量取值为 z z z 时 φ \varphi φ 的值(1 为真,0 为假)。若存在 z z z 使 φ ( z ) = 1 \varphi(z)=1 φ ( z ) = 1 ,称 φ \varphi φ 可满足 ,否则称其不可满足 。 例如 ( u 1 ∨ u 2 ) ∧ ( u 2 ∨ u 3 ) ∧ ( u 3 ∨ u 1 ) (u_1\vee u_2)\wedge(u_2\vee u_3)\wedge(u_3\vee u_1) ( u 1 ∨ u 2 ) ∧ ( u 2 ∨ u 3 ) ∧ ( u 3 ∨ u 1 ) 为真当且仅当 u 1 , u 2 , u 3 u_1,u_2,u_3 u 1 , u 2 , u 3 中多数为真,它是可满足的。
文字 是变量 u k u_k u k 或其否定 u ˉ k \bar u_k u ˉ k 。公式是合取范式 (CNF),若它是若干子句 (文字的析取)的合取:
φ = ⋀ i ( ⋁ j v i j ) . \varphi=\bigwedge_i\Big(\bigvee_j v_{ij}\Big). φ = i ⋀ ( j ⋁ v ij ) . 若每个子句至多含 k k k 个文字,称为 k k k CNF 。SAT 是全体可满足 CNF 公式构成的语言,3SAT 是全体可满足 3CNF 公式构成的语言。
SAT 与 3SAT 显然属于 NP:证书就是满足赋值,代入检查只需线性时间。
2. 定理与思路# SAT 是 NP 完全的; 3SAT 是 NP 完全的。 要把任意 L ∈ N P L\in\mathrm{NP} L ∈ NP 归约到 SAT,即给出多项式时间变换 x ↦ φ x x\mapsto\varphi_x x ↦ φ x ,使 x ∈ L ⟺ φ x x\in L\iff\varphi_x x ∈ L ⟺ φ x 可满足。困难在于,对 L L L 我们一无所知,只知道它有一个多项式时间验证器 M M M :
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 ∈ L ⟺ ∃ u ∈ { 0 , 1 } p ( ∣ x ∣ ) such that M ( x , u ) = 1. 于是 φ x \varphi_x φ x 的变量应当编码证书 u u u 以及 M M M 的整个计算过程,子句负责检查这个计算是合法的。为此需要两件工具:
表达能力 :任何布尔函数都能写成 CNF(第 3 节),但一般需要指数大小,因此只能用于常数个变量 的函数;
局部性 :图灵机每一步只依赖常数个比特,但读写头的位置依赖于输入内容;借助健忘 图灵机(第 4 节)使位置与内容无关,每一步便只是常数个变量之间的约束(第 5 节)。
3. 工具一:CNF 的普适性# 对任意布尔函数 f : { 0 , 1 } l → { 0 , 1 } f:\{0,1\}^l\to\{0,1\} f : { 0 , 1 } l → { 0 , 1 } ,存在 l l l 个变量、大小至多 l 2 l l2^l l 2 l 的 CNF 公式 φ \varphi φ ,使对任意 u ∈ { 0 , 1 } l u\in\{0,1\}^l u ∈ { 0 , 1 } l 有 φ ( u ) = f ( u ) \varphi(u)=f(u) φ ( u ) = f ( u ) 。这里公式的大小指其中 ∧ / ∨ \wedge/\vee ∧ / ∨ 符号的个数。
对每个 v ∈ { 0 , 1 } l v\in\{0,1\}^l v ∈ { 0 , 1 } l ,存在子句 C v ( z 1 , … , z l ) C_v(z_1,\dots,z_l) C v ( z 1 , … , z l ) 使 C v ( v ) = 0 C_v(v)=0 C v ( v ) = 0 ,而对任意 u ≠ v u\ne v u = v 有 C v ( u ) = 1 C_v(u)=1 C v ( u ) = 1 :令 v i = 1 v_i=1 v i = 1 时取文字 z ˉ i \bar z_i z ˉ i ,v i = 0 v_i=0 v i = 0 时取 z i z_i z i ,再取析取。例如 C 010 = z 1 ∨ z ˉ 2 ∨ z 3 C_{010}=z_1\vee\bar z_2\vee z_3 C 010 = z 1 ∨ z ˉ 2 ∨ z 3 。
令 φ \varphi φ 为所有满足 f ( v ) = 0 f(v)=0 f ( v ) = 0 的 C v C_v C v 的合取,它至多有 2 l 2^l 2 l 个子句,大小至多 l 2 l l2^l l 2 l 。若 f ( u ) = 0 f(u)=0 f ( u ) = 0 ,则 C u C_u C u 出现在 φ \varphi φ 中且 C u ( u ) = 0 C_u(u)=0 C u ( u ) = 0 ,故 φ ( u ) = 0 \varphi(u)=0 φ ( u ) = 0 ;若 f ( u ) = 1 f(u)=1 f ( u ) = 1 ,则对 φ \varphi φ 中的每个 C v C_v C v 有 v ≠ u v\ne u v = u ,从而 C v ( u ) = 1 C_v(u)=1 C v ( u ) = 1 ,故 φ ( u ) = 1 \varphi(u)=1 φ ( u ) = 1 。□ \square □
直接对 x ↦ M ( x , ⋅ ) x\mapsto M(x,\cdot) x ↦ M ( x , ⋅ ) 应用此命题,公式大小可达 p ( ∣ x ∣ ) 2 p ( ∣ x ∣ ) p(|x|)2^{p(|x|)} p ( ∣ x ∣ ) 2 p ( ∣ x ∣ ) ,归约就不是多项式的了。但当 l l l 为常数时,l 2 l l2^l l 2 l 也是常数。
例如异或 f ( z 1 , z 2 ) = z 1 ⊕ z 2 f(z_1,z_2)=z_1\oplus z_2 f ( z 1 , z 2 ) = z 1 ⊕ z 2 在 00 00 00 与 11 11 11 处为 0 0 0 ,按证明取 C 00 = z 1 ∨ z 2 C_{00}=z_1\vee z_2 C 00 = z 1 ∨ z 2 、C 11 = z ˉ 1 ∨ z ˉ 2 C_{11}=\bar z_1\vee\bar z_2 C 11 = z ˉ 1 ∨ z ˉ 2 ,得 z 1 ⊕ z 2 = ( z 1 ∨ z 2 ) ∧ ( z ˉ 1 ∨ z ˉ 2 ) z_1\oplus z_2=(z_1\vee z_2)\wedge(\bar z_1\vee\bar z_2) z 1 ⊕ z 2 = ( z 1 ∨ z 2 ) ∧ ( z ˉ 1 ∨ z ˉ 2 ) 。这个构造一般比最优的 CNF 大得多,但对某些函数,指数大小无法避免 :
l l l 个变量的奇偶校验函数 z 1 ⊕ ⋯ ⊕ z l z_1\oplus\cdots\oplus z_l z 1 ⊕ ⋯ ⊕ z l 的任何 CNF 都至少有 2 l − 1 2^{l-1} 2 l − 1 个子句。
设 φ \varphi φ 是它的 CNF,C C C 是其中一个子句(不妨设没有永真的子句)。若 C C C 不含变量 z i z_i z i ,取一个使 C C C 为假的赋值 v v v ,翻转 z i z_i z i 得到 v ′ v' v ′ ,C ( v ′ ) C(v') C ( v ′ ) 仍为假;但 v v v 与 v ′ v' v ′ 中有一个的奇偶校验值为 1 1 1 ,φ \varphi φ 在它上却为 0 0 0 ,矛盾。所以每个子句都含全部 l l l 个变量,恰好在一个赋值上为假。而奇偶校验在 2 l − 1 2^{l-1} 2 l − 1 个赋值上为 0 0 0 ,每个都要被某个子句「杀死」,故至少 2 l − 1 2^{l-1} 2 l − 1 个子句。□ \square □ 所以不能指望把整个验证器一次写成 CNF,只能把它切成常数规模的小块。引入新变量 可以绕开这一障碍:用中间变量 s i s_i s i 记录前 i i i 位的奇偶校验值,约束 s i = s i − 1 ⊕ z i s_i=s_{i-1}\oplus z_i s i = s i − 1 ⊕ z i 只涉及 3 3 3 个变量,各用 4 4 4 个子句写出,总大小就是线性的(代价是新公式多了变量,它与原函数不再逐点相等,而是「对新变量取存在」后相等,这对归约已经足够)。下面的快照变量 z i z_i z i 正是这样的中间变量,它们记录了计算的中间状态。
4. 工具二:健忘图灵机# 图灵机 M M M 是健忘的 ,若对任意输入 x x x 与 i ∈ N i\in\mathbb N i ∈ N ,M M M 的每个读写头在第 i i i 步的位置只是 ∣ x ∣ |x| ∣ x ∣ 与 i i i 的函数,与 x x x 的内容无关。 任意图灵机 M M M 都可被健忘图灵机 M ′ M' M ′ 模拟,使 M M M 的 t t t 步计算由 M ′ M' M ′ 的 O ( t 2 ) O(t^2) O ( t 2 ) 步完成。
不妨设 M M M 只有一条双向无限的纸带(由鲁棒性 ,这只带来多项式开销)。令 M ′ 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 0 , 1 , 0 , − 1 , − 1 , 0 , 1 , 2 , 1 , 0 , − 1 , − 2 , ⋯ , − ( j − 1 ) , … , 0 , … , j , … , 0 , … , − j , ⋯ 第 j j j 阶段从 − ( j − 1 ) -(j-1) − ( j − 1 ) 扫到 j j j 再扫回 − j -j − j ,约 4 j 4j 4 j 步,模拟 M M M 的第 j j j 步。M M M 在 t t t 步内的读写头位置不超出 [ − ( t − 1 ) , t − 1 ] [-(t-1),t-1] [ − ( t − 1 ) , t − 1 ] ,每个阶段都覆盖了 M M M 当前可能用到的全部格子。
具体地,在 M M M 的第 t t t 步之前,M ′ M' M ′ 用标记记下区间端点 − ( t − 1 ) -(t-1) − ( t − 1 ) 、t − 1 t-1 t − 1 以及 M M M 读写头的当前位置(字母表中加入带标记的符号)。第 t t t 阶段:
从左端标记向右扫,遇到 M M M 的读写头标记时,M ′ M' M ′ 由状态中保存的 q q q 与读到的符号 a a a 算出 δ ( q , a ) \delta(q,a) δ ( q , a ) ,写入新符号、更新状态;若 M M M 右移,则在下一步把读写头标记右移一格;若左移,则记住此事待回程时完成; 继续右扫找到右端标记,将其右移一格; 回扫到左端标记,途中完成待办的左移,最后将左端标记左移一格。 无论输入如何,读写头轨迹都相同,故 M ′ M' M ′ 是健忘的。t t t 步共用时 4 ( 1 + 2 + ⋯ + t ) = O ( t 2 ) 4(1+2+\cdots+t)=O(t^2) 4 ( 1 + 2 + ⋯ + t ) = O ( t 2 ) 。M M M 停机时 M ′ 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 阶段覆盖 [ − j , j ] [-j,j] [ − j , j ] ,在右扫途中模拟 M M M 的第 j j j 步 上一章的课后习题(若 L ∈ D T I M E ( T ( n ) ) L\in\mathrm{DTIME}(T(n)) L ∈ DTIME ( T ( n )) ,则存在 O ( T ( n ) 2 ) O(T(n)^2) O ( T ( n ) 2 ) 时间的健忘图灵机判定 L L L )即由此得到。用更精巧的模拟,开销可降到 O ( T log T ) O(T\log T) O ( T log T ) ,思想与上一章通用图灵机的区段缓冲相同:那里的「纸带不动、内容搬运」恰好使读写头的轨迹与内容无关。
5. SAT 是 NP 完全的# 设 L ∈ N P L\in\mathrm{NP} L ∈ NP ,M M M 是多项式时间验证器,p p p 为证书长度。由前述各种模拟,不妨设:
M M M 只有两条带:只读的输入带,以及兼作输出带的工作带;
M M M 是健忘的:读写头的移动不依赖于纸带内容。
这些变换只带来多项式的开销。记 Q Q Q 为 M M M 的状态集,Γ \Gamma Γ 为其字母表,T = T ( n ) T=T(n) T = T ( n ) 为 M M M 在长为 n + p ( n ) n+p(n) n + p ( n ) 的输入上的运行步数。
M M M 在输入 y y y 上第 i i i 步的快照 是三元组 ⟨ a , b , q ⟩ ∈ Γ × Γ × Q \langle a,b,q\rangle\in\Gamma\times\Gamma\times Q ⟨ a , b , q ⟩ ∈ Γ × Γ × Q ,其中 a , b a,b a , b 是两个读写头读到的符号,q q q 是第 i i i 步时的状态。每个快照可以编码为长为 c c c 的串 z i z_i z i ,常数 c c c 只依赖于 M M M 的状态数与字母表大小,与输入长度无关。再定义两个函数:i n p u t p o s ( i ) \mathrm{inputpos}(i) inputpos ( i ) 为第 i i i 步输入带读写头的位置;p r e v ( i ) \mathrm{prev}(i) prev ( i ) 为第 i i i 步之前,工作带读写头最后一次 访问当前位置的步数(若此前从未访问,则约定读到空白符)。由于 M M M 是健忘的,只需在任意一个长为 n + p ( n ) n+p(n) n + p ( n ) 的输入(如全 0 串)上模拟 M M M 并记录读写头位置,即可在多项式时间内算出所有 i n p u t p o s ( i ) \mathrm{inputpos}(i) inputpos ( i ) 与 p r e v ( i ) \mathrm{prev}(i) prev ( i ) 。
Fig 2 快照的局部性:z i z_i z i 只依赖三处常数长度的信息 存在只依赖于 M M M 的函数 F : { 0 , 1 } 2 c + 1 → { 0 , 1 } c F:\{0,1\}^{2c+1}\to\{0,1\}^c F : { 0 , 1 } 2 c + 1 → { 0 , 1 } c ,使
z i = F ( z i − 1 , y i n p u t p o s ( i ) , z p r e v ( i ) ) . z_i=F\big(z_{i-1},\ y_{\mathrm{inputpos}(i)},\ z_{\mathrm{prev}(i)}\big). z i = F ( z i − 1 , y inputpos ( i ) , z prev ( i ) ) .
第 i i i 步的快照由三部分组成:状态 q q q 由第 i − 1 i-1 i − 1 步的状态与读到的符号经转移函数决定,它们都在 z i − 1 z_{i-1} z i − 1 中;输入带读到的符号是 y i n p u t p o s ( i ) y_{\mathrm{inputpos}(i)} y inputpos ( i ) ;工作带当前格的内容是第 p r e v ( i ) \mathrm{prev}(i) prev ( i ) 步离开该格时写入的符号,它由 z p r e v ( i ) z_{\mathrm{prev}(i)} z prev ( i ) (那一步的状态与读到的符号)经转移函数决定。□ \square □ (SAT 是 NP 难的 )快照序列完全决定了 M M M 的计算结果。于是 x ∈ L x\in L x ∈ L ,当且仅当存在 y ∈ { 0 , 1 } n + p ( n ) y\in\{0,1\}^{n+p(n)} y ∈ { 0 , 1 } n + p ( n ) 与 z 1 , … , z T ∈ { 0 , 1 } c z_1,\dots,z_T\in\{0,1\}^c z 1 , … , z T ∈ { 0 , 1 } c 同时满足:
y y y 的前 n n n 位等于 x x x ;z 1 z_1 z 1 编码 M M M 的初始快照 ⟨ ▹ , □ , q s t a r t ⟩ \langle\triangleright,\square,q_{\mathrm{start}}\rangle ⟨ ▹ , □ , q start ⟩ ;对每个 i ∈ { 2 , … , T } i\in\{2,\dots,T\} i ∈ { 2 , … , T } ,z i = F ( z i − 1 , y i n p u t p o s ( i ) , z p r e v ( i ) ) z_i=F(z_{i-1},y_{\mathrm{inputpos}(i)},z_{\mathrm{prev}(i)}) z i = F ( z i − 1 , y inputpos ( i ) , z prev ( i ) ) ; z T z_T z T 编码一个停机且输出 1 的快照。φ x \varphi_x φ x 以 y ∈ { 0 , 1 } n + p ( n ) y\in\{0,1\}^{n+p(n)} y ∈ { 0 , 1 } n + p ( n ) 与 z ∈ { 0 , 1 } c T z\in\{0,1\}^{cT} z ∈ { 0 , 1 } c T 为变量,取为这四个条件的合取,则 x ∈ L ⟺ φ x ∈ S A T x\in L\iff\varphi_x\in\mathrm{SAT} x ∈ L ⟺ φ x ∈ SAT (y y y 的后 p ( n ) p(n) p ( n ) 位就是证书 u u u )。
大小:条件 1 是 n n n 个单文字子句,大小 4 n 4n 4 n ;条件 2、4 各只依赖于 c c c 个变量,由 CNF 的普适性可写成大小 c 2 c c2^c c 2 c 的 CNF;条件 3 是 T T T 个条件的合取,每个只依赖于至多 3 c + 1 3c+1 3 c + 1 个变量,可写成大小至多 T ( 3 c + 1 ) 2 3 c + 1 T(3c+1)2^{3c+1} T ( 3 c + 1 ) 2 3 c + 1 的 CNF。合起来大小为 d ( n + T ) d(n+T) d ( n + T ) ,d d d 是只依赖于 M M M 的常数。而由于 i n p u t p o s , p r e v \mathrm{inputpos},\mathrm{prev} inputpos , prev 可在多项式时间内求出,φ x \varphi_x φ x 可在 M M M 运行时间的多项式时间内构造。□ \square □
证明的要点在于:2 3 c + 1 2^{3c+1} 2 3 c + 1 是指数的,但指数中的 c c c 是常数 ;整个计算被切成 T T T 个常数大小的局部检查,每个都可以暴力地写成 CNF。
另一种写法:计算表格
不借助健忘机也能证明(Sipser 教材的写法)。设 M M M 是单带机,T T T 步内只用到 T T T 格。把 T + 1 T+1 T + 1 个格局逐行写成一张 ( T + 1 ) × T (T+1)\times T ( T + 1 ) × T 的表,每格存一个带符号,读写头所在的格再附上当前状态,取值只有常数种,用常数个布尔变量编码。由于每步只改动读写头附近,第 i + 1 i+1 i + 1 行第 j j j 格由第 i i i 行第 j − 1 , j , j + 1 j-1,j,j+1 j − 1 , j , j + 1 格决定,「表格是一次合法计算」就变成对每个 2 × 3 2\times3 2 × 3 窗口的常数大小约束,共 O ( T 2 ) O(T^2) O ( T 2 ) 个;再加上「首行是初始格局」与「末行输出 1」,就得到大小 O ( T 2 ) O(T^2) O ( T 2 ) 的公式。
两种写法的共同核心都是局部性 :表格写法把它体现为「空间上的邻居」,健忘机写法把它体现为「时间上的前驱」z i − 1 , z p r e v ( i ) z_{i-1},z_{\mathrm{prev}(i)} z i − 1 , z prev ( i ) 。后者只为每一步设变量、不为每个格子设变量,配合 O ( T log T ) O(T\log T) O ( T log T ) 的健忘模拟,公式大小可以做到 O ( T log T ) O(T\log T) O ( T log T ) ,而表格写法本质上是 Θ ( T 2 ) \Theta(T^2) Θ ( T 2 ) 的。
6. 3SAT 是 NP 完全的# S A T ≤ p 3 S A T \mathrm{SAT}\le_p\mathrm{3SAT} SAT ≤ p 3SAT 。
先看 4 个文字的子句,如 C = u 1 ∨ u ˉ 2 ∨ u ˉ 3 ∨ u 4 C=u_1\vee\bar u_2\vee\bar u_3\vee u_4 C = u 1 ∨ u ˉ 2 ∨ u ˉ 3 ∨ u 4 。引入新变量 z z z ,将 C C C 替换为两个子句
C 1 = u 1 ∨ u ˉ 2 ∨ z , C 2 = u ˉ 3 ∨ u 4 ∨ z ˉ . C_1=u_1\vee\bar u_2\vee z,\qquad C_2=\bar u_3\vee u_4\vee\bar z. C 1 = u 1 ∨ u ˉ 2 ∨ z , C 2 = u ˉ 3 ∨ u 4 ∨ z ˉ . 若 C C C 被满足:真文字在 C 1 C_1 C 1 中时取 z = 0 z=0 z = 0 ,在 C 2 C_2 C 2 中时取 z = 1 z=1 z = 1 ,两个子句都被满足;反之若 C C C 为假,则 C 1 C_1 C 1 要求 z = 1 z=1 z = 1 ,C 2 C_2 C 2 要求 z = 0 z=0 z = 0 ,二者不能同时满足。
一般地,含 k > 3 k>3 k > 3 个文字的子句 C = ℓ 1 ∨ ⋯ ∨ ℓ k C=\ell_1\vee\cdots\vee\ell_k C = ℓ 1 ∨ ⋯ ∨ ℓ k 可等价地替换为大小 k − 1 k-1 k − 1 的 C 1 = ℓ 1 ∨ ⋯ ∨ ℓ k − 2 ∨ z C_1=\ell_1\vee\cdots\vee\ell_{k-2}\vee z C 1 = ℓ 1 ∨ ⋯ ∨ ℓ k − 2 ∨ z 与大小 3 3 3 的 C 2 = ℓ k − 1 ∨ ℓ k ∨ z ˉ C_2=\ell_{k-1}\vee\ell_k\vee\bar z C 2 = ℓ k − 1 ∨ ℓ k ∨ z ˉ (z z z 为新变量)。反复应用,每个大小 k k k 的子句变为 k − 2 k-2 k − 2 个 3 子句,公式规模只线性增长,得到与原公式同时可满足的 3CNF。例如
ℓ 1 ∨ ⋯ ∨ ℓ 5 ⟼ ( ℓ 1 ∨ ℓ 2 ∨ z 2 ) ∧ ( ℓ 3 ∨ z 1 ∨ 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). ℓ 1 ∨ ⋯ ∨ ℓ 5 ⟼ ( ℓ 1 ∨ ℓ 2 ∨ z 2 ) ∧ ( ℓ 3 ∨ z 1 ∨ z ˉ 2 ) ∧ ( ℓ 4 ∨ ℓ 5 ∨ z ˉ 1 ) . 新变量像一条链:若真文字是 ℓ 3 \ell_3 ℓ 3 ,取 z 2 = 1 z_2=1 z 2 = 1 、z 1 = 0 z_1=0 z 1 = 0 ,两端的子句由新变量满足;若所有 ℓ i \ell_i ℓ i 都为假,从左到右依次迫使 z 2 = 1 z_2=1 z 2 = 1 、z 1 = 1 z_1=1 z 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 ∨ b a\vee b a ∨ b 等价于两条蕴含 a ˉ → b \bar a\to b a ˉ → b 与 b ˉ → a \bar b\to a b ˉ → a ,以 2 n 2n 2 n 个文字为顶点、蕴含为有向边建立蕴含图 。可以证明:公式可满足当且仅当没有变量 u u u 使 u u u 与 u ˉ \bar u u ˉ 处于同一个强连通分量;且按强连通分量的拓扑序反向赋值即得满足赋值。强连通分量可在 O ( m + n ) O(m+n) O ( m + n ) 时间内求出(见稳定匹配与图 )。上面的拆分之所以不能把 3 降为 2,是因为拆分 3 子句会得到一个 2 子句与另一个 3 子句,规模不降。
7. 再看 Cook–Levin 定理# 规模 :用 O ( T log T ) O(T\log T) O ( T log T ) 的健忘模拟,φ x \varphi_x φ x 的大小与构造时间可以做到 O ( T log T ) O(T\log T) O ( T log T ) ,其中 T T T 是 M M M 在 x x x 上的步数;
证书可以双向转换 :归约 f f f 不仅满足 x ∈ L ⟺ f ( x ) ∈ S A T x\in L\iff f(x)\in\mathrm{SAT} x ∈ L ⟺ f ( x ) ∈ SAT ,证明还给出了把 x x x 的证书高效转换为 f ( x ) f(x) f ( x ) 的满足赋值(填入 u u u 并模拟出 z z z )、以及反向转换(读出 y y y 的后 p ( n ) p(n) p ( n ) 位)的方法。
若归约 f f f 还附带多项式时间的映射,能把 x x x 的证书转换为 f ( x ) f(x) f ( x ) 的证书、并把 f ( x ) f(x) f ( x ) 的证书转换回 x x x 的证书,则称 f f f 为 Levin 归约 。 Levin 归约保证了「求解 SAT 的搜索版本」就足以求解任意 NP 问题的搜索版本,这将用于证明搜索与判定的等价性。
8. 第一个图论 NP 完全问题:独立集# I N D S E T = { ⟨ 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)\} INDSET = {⟨ G , k ⟩ : ∃ S ⊆ V ( G ) , ∣ S ∣ = k , ∀ u , v ∈ S , ( u , v ) ∈ / E ( G )} 是 NP 完全的。
INDSET 属于 NP 已在上一章证明,下面给出 3 S A T ≤ p I N D S E T \mathrm{3SAT}\le_p\mathrm{INDSET} 3SAT ≤ p INDSET 。
设 φ \varphi φ 是 n n n 个变量、m m m 个子句的 3CNF 公式。构造 7 m 7m 7 m 个顶点的图 G G G :
每个子句对应一个由 7 个顶点组成的簇 ,每个顶点对应该子句所含三个变量的一个满足此子句的部分赋值(三个变量共 2 3 = 8 2^3=8 2 3 = 8 种赋值,恰有一种使子句为假); 同一簇内的任意两个顶点之间连边; 若两个顶点对应的部分赋值不相容 (对某个公共变量赋了不同的值),则在它们之间连边。 令 k = m k=m k = m 。G G G 可在多项式时间内构造。下证 φ \varphi φ 可满足 ⟺ \iff ⟺ G G G 有大小为 m m m 的独立集。
(⇒ \Rightarrow ⇒ )设 u u u 是满足赋值。对每个子句 C C C ,u u u 在 C C C 的三个变量上的限制满足 C C C ,取簇中对应的顶点放入 S S S 。S S S 中的点来自不同的簇,且都是同一个 u u u 的限制,两两相容,故 S S S 是大小为 m m m 的独立集。
(⇐ \Leftarrow ⇐ )设 S S S 是大小为 m m m 的独立集。簇内两两相连,故 S S S 在每个簇中至多一个点;共 m m m 个簇,于是每个簇恰有一个点。对每个 i ∈ [ n ] i\in[n] i ∈ [ n ] ,若 S S S 中某个点的部分赋值给 u i u_i u i 赋值 a a a ,则令 u i = a u_i=a u i = a (其余变量任意);由于不相容的点之间有边,每个 u i u_i u i 至多得到一个值,赋值是良定义的。每个子句所在簇中的那个点是一个满足该子句的部分赋值,且与 u u u 一致,故 u u u 满足 φ \varphi φ 的全部子句。□ \square □
若某个子句只含 r < 3 r<3 r < 3 个变量,相应的簇有 2 r − 1 2^r-1 2 r − 1 个顶点,论证不变。这个证明体现了归约的典型结构:部件 (gadget)模拟原问题的局部结构(簇 = 子句的选择),一致性约束 (不相容边)把局部选择粘合成全局解。
三顶点版本
另一种常见构造(Kleinberg–Tardos):每个子句对应一个三角形,三个顶点分别对应子句的三个文字;再在每对互补文字 u i u_i u i 与 u ˉ i \bar u_i u ˉ i 对应的顶点之间连边,取 k = m k=m k = m 。独立集从每个三角形中选一个文字令其为真,互补边保证不会同时选中 u i u_i u i 与 u ˉ i \bar u_i u ˉ i 。
9. 小结# 结论 归约 关键 SAT 是 NP 完全的 任意 L ∈ N P ≤ p S A T L\in\mathrm{NP}\le_p\mathrm{SAT} L ∈ NP ≤ p SAT 健忘机 + 快照的局部性 + 常数变量函数的 CNF 3SAT 是 NP 完全的 S A T ≤ p 3 S A T \mathrm{SAT}\le_p\mathrm{3SAT} SAT ≤ p 3SAT 用新变量拆分长子句 INDSET 是 NP 完全的 3 S A T ≤ p I N D S E T \mathrm{3SAT}\le_p\mathrm{INDSET} 3SAT ≤ p INDSET 子句簇 + 不相容边
Cook–Levin 定理是唯一一次需要直接面对「任意 NP 语言」的证明:它的核心是计算的局部性 ,图灵机每一步只改动常数个比特,于是整个计算可以由多项式个常数规模的约束刻画。从此 SAT 取代了图灵机,成为证明 NP 完全性的起点;下一章沿归约链继续扩展,得到哈密顿路、集合覆盖、子集和等一大批 NP 完全问题,见NP 完全问题 。