有了 SAT、3SAT 与独立集,证明一个新问题 X X X 是 NP 完全的就有了固定的模板:先说明 X ∈ N P X\in\mathrm{NP} X ∈ NP ,再把某个已知的 NP 完全问题归约到 X X X 。难点全在归约的设计:用部件 模拟变量与子句,再用约束迫使部件的局部选择拼成一个全局一致的解。
1. 引入:归约的模板# 已知 Y Y Y 是 NP 完全的,要证明 X X X 是 NP 完全的。 第一步,X ∈ N P X\in\mathrm{NP} X ∈ NP :指出证书,说明它长度多项式、可在多项式时间内验证。这一步通常是平凡的,但不能省略;
第二步,Y ≤ p X Y\le_p X Y ≤ p X :给出多项式时间变换 f f f ,并证明 y ∈ Y ⇒ f ( y ) ∈ X y\in Y\Rightarrow f(y)\in X y ∈ Y ⇒ f ( y ) ∈ X (由 Y Y Y 的解构造 X X X 的解)与 f ( y ) ∈ X ⇒ y ∈ Y f(y)\in X\Rightarrow y\in Y f ( y ) ∈ X ⇒ y ∈ Y (由 X X X 的解读回 Y Y Y 的解)。
本章的归约关系如下,箭头 A → B A\to B A → B 表示 A ≤ p B A\le_p B A ≤ p B :
Fig 1 本章的归约关系 按问题的结构,可以粗分为序列型 (哈密顿路)、覆盖与打包型 (集合覆盖、顶点覆盖、独立集、团)与数值型 (子集和、划分、调度)三类。
2. 序列型:有向哈密顿路# 有向图中的有向哈密顿路 是恰好经过每个顶点一次的有向路径。d H A M P A T H \mathrm{dHAMPATH} dHAMPATH 为全体含有向哈密顿路的有向图构成的语言。 dHAMPATH 是 NP 完全的。
dHAMPATH 显然属于 NP(证书是顶点序列)。下面给出 S A T ≤ p d H A M P A T H \mathrm{SAT}\le_p\mathrm{dHAMPATH} SAT ≤ p dHAMPATH 。
设 φ \varphi φ 是 n n n 个变量、m m m 个子句的 CNF 公式。构造有向图 G G G ,顶点包括:
每个子句 C C C 对应一个顶点 v C v_C v C ,共 m m m 个; 起点 v s t a r t v_{\mathrm{start}} v start 与终点 v e n d v_{\mathrm{end}} v end ; 每个变量 u j u_j u j 对应一条由 4 m 4m 4 m 个顶点组成的链 v 1 , … , v 4 m v_1,\dots,v_{4m} v 1 , … , v 4 m ,相邻的 v i , v i + 1 v_i,v_{i+1} v i , v i + 1 之间有双向边。 边包括:
v s t a r t v_{\mathrm{start}} v start 到第 1 条链的两个端点;第 j j j 条链的两个端点到第 j + 1 j+1 j + 1 条链的两个端点(j ∈ [ n − 1 ] j\in[n-1] j ∈ [ n − 1 ] );第 n n n 条链的两个端点到 v e n d v_{\mathrm{end}} v end ;对第 i i i 个子句 C C C 与其中出现的变量 u j u_j u j ,在第 j j j 条链上取专属于 C C C 的一对相邻顶点 v 4 i − 2 , v 4 i − 1 v_{4i-2},v_{4i-1} v 4 i − 2 , v 4 i − 1 (不同子句的「插口」互不相邻,中间隔有缓冲顶点):若 C C C 含 u j u_j u j ,加边 v 4 i − 2 → v C → v 4 i − 1 v_{4i-2}\to v_C\to v_{4i-1} v 4 i − 2 → v C → v 4 i − 1 ;若 C C C 含 u ˉ j \bar u_j u ˉ j ,则方向相反,加边 v 4 i − 1 → v C → v 4 i − 2 v_{4i-1}\to v_C\to v_{4i-2} v 4 i − 1 → v C → v 4 i − 2 。 于是从左到右走一条链表示 u j = 1 u_j=1 u j = 1 ,从右到左表示 u j = 0 u_j=0 u j = 0 ;子句顶点只能从「方向正确」的链上绕道访问。构造显然是多项式时间的。
(⇒ \Rightarrow ⇒ )设 u u u 是满足赋值。从 v s t a r t v_{\mathrm{start}} v start 出发依次走完各条链,最后到达 v e n d v_{\mathrm{end}} v end :u j = 1 u_j=1 u j = 1 时从左到右走第 j j j 条链,u j = 0 u_j=0 u j = 0 时从右到左。每个子句 C C C 至少有一个真文字,在该文字对应的链上,走到 C C C 的插口时绕道 v C v_C v C 再回到链上即可。这样每个子句顶点恰被访问一次,得到哈密顿路。
(⇐ \Leftarrow ⇐ )设 P P P 是哈密顿路。v s t a r t v_{\mathrm{start}} v start 没有入边,v e n d v_{\mathrm{end}} v end 没有出边,故 P P P 从 v s t a r t v_{\mathrm{start}} v start 开始、在 v e n d v_{\mathrm{end}} v end 结束。关键观察:若 P P P 走了链上的边 v → v C v\to v_C v → v C ,则下一步必须走 v C → w v_C\to w v C → w ,其中 w w w 是 v v v 在该插口中的相邻顶点;否则 P P P 此后访问 w w w 时会被「困住」:w w w 的邻居(链上两侧的点与 v C v_C v C )都已访问过,w w w 只能作为终点,与终点是 v e n d v_{\mathrm{end}} v end 矛盾。因此把子句顶点的绕道去掉后,P P P 依次完整地走过每条链,且每条链要么从左到右、要么从右到左。令 P P P 从左到右走第 j j j 条链时 u j = 1 u_j=1 u j = 1 ,否则 u j = 0 u_j=0 u j = 0 。P P P 经过每个 v C v_C v C ,而它只能从方向与某个文字一致的链上绕道,该文字在 u u u 下为真,故 u u u 满足 φ \varphi φ 。□ \square □
Fig 2 φ = ( u 1 ∨ u 2 ) ∧ ( u ˉ 1 ∨ u ˉ 2 ) \varphi=(u_1\vee u_2)\wedge(\bar u_1\vee\bar u_2) φ = ( u 1 ∨ u 2 ) ∧ ( u ˉ 1 ∨ u ˉ 2 ) 的构造与赋值 u 1 = 1 , u 2 = 0 u_1=1,\ u_2=0 u 1 = 1 , u 2 = 0 对应的哈密顿路 部件的分工很清楚:链 是变量部件,只有两种走法;绕道 是子句部件,只在方向正确时可用;链与链的首尾相接保证每个变量恰好被「赋值」一次。
从 dHAMPATH 出发,哈密顿问题的各种变体都能用很小的改动得到:
有向哈密顿圈 :在上面的构造里加一条边 v e n d → v s t a r t v_{\mathrm{end}}\to v_{\mathrm{start}} v end → v start 。v s t a r t v_{\mathrm{start}} v start 原本没有入边,所以任何哈密顿圈都必须经过这条新边,去掉它就是一条从 v s t a r t v_{\mathrm{start}} v start 到 v e n d v_{\mathrm{end}} v end 的哈密顿路;反之亦然。故 dHAMCYCLE 是 NP 完全的。
无向哈密顿圈 :把有向图的每个顶点 v v v 拆成三个顶点 v i n − v m i d − v o u t v_{\mathrm{in}}-v_{\mathrm{mid}}-v_{\mathrm{out}} v in − v mid − v out ,每条有向边 u → v u\to v u → v 改成无向边 u o u t − v i n u_{\mathrm{out}}-v_{\mathrm{in}} u out − v in 。v m i d v_{\mathrm{mid}} v mid 的度数为 2,哈密顿圈必须连续经过 v i n , v m i d , v o u t v_{\mathrm{in}},v_{\mathrm{mid}},v_{\mathrm{out}} v in , v mid , v out ;而 v o u t v_{\mathrm{out}} v out 只与 v m i d v_{\mathrm{mid}} v mid 及各 w i n w_{\mathrm{in}} w in 相邻,沿圈的一个方向看,各个三元组都按 in → \to → mid → \to → out 的顺序经过,三元组之间的边都是某条 u o u t − v i n u_{\mathrm{out}}-v_{\mathrm{in}} u out − v in ,对应原图的有向边。故两个图同时有或没有哈密顿圈。
旅行商 :再用上一章的 H A M C Y C L E ≤ p T S P \mathrm{HAMCYCLE}\le_p\mathrm{TSP} HAMCYCLE ≤ p TSP 。
拆点的技巧值得记住:用一个度数为 2 的中间点「钩住」两个端点,就把方向信息编码进了无向图。
3. 覆盖与打包型# 3.1 集合覆盖# 集合覆盖 :给定有限集族 S 1 , … , S m S_1,\dots,S_m S 1 , … , S m 与整数 K K K ,判定是否存在至多 K K K 个集合覆盖 ⋃ i = 1 m S i \bigcup_{i=1}^m S_i ⋃ i = 1 m S i ,即存在下标 i 1 , … , i K i_1,\dots,i_K i 1 , … , i K 使 ⋃ j = 1 K S i j = ⋃ i = 1 m S i \bigcup_{j=1}^K S_{i_j}=\bigcup_{i=1}^m S_i ⋃ j = 1 K S i j = ⋃ i = 1 m S i 。集合覆盖是 NP 完全的。
集合覆盖显然属于 NP。下面给出 S A T ≤ p S E T C O V E R \mathrm{SAT}\le_p\mathrm{SETCOVER} SAT ≤ p SETCOVER 。
设 φ \varphi φ 是 n n n 个变量、m m m 个子句的 CNF 公式。令 S i , t S_{i,t} S i , t (相应地 S i , f S_{i,f} S i , f )为第 i i i 个变量取真(相应地取假)时被满足的子句下标的集合,它们都是 { 1 , … , m } \{1,\dots,m\} { 1 , … , m } 的子集,且这 2 n 2n 2 n 个集合之并为 { 1 , … , m } \{1,\dots,m\} { 1 , … , m } (假定每个子句非空)。再为每个变量引入一个新元素 m + i m+i m + i :
S 2 i − 1 = S i , t ∪ { m + i } , S 2 i = S i , f ∪ { m + i } , i = 1 , … , n , S_{2i-1}=S_{i,t}\cup\{m+i\},\qquad S_{2i}=S_{i,f}\cup\{m+i\},\qquad i=1,\dots,n, S 2 i − 1 = S i , t ∪ { m + i } , S 2 i = S i , f ∪ { m + i } , i = 1 , … , n , 取 K = n K=n K = n ,全集为 { 1 , … , m + n } \{1,\dots,m+n\} { 1 , … , m + n } 。变换是多项式时间的。
(⇒ \Rightarrow ⇒ )若 u u u 满足 φ \varphi φ ,则 { S 2 i − u i : i = 1 , … , n } \{S_{2i-u_i}:i=1,\dots,n\} { S 2 i − u i : i = 1 , … , n } (u i = 1 u_i=1 u i = 1 时选 S 2 i − 1 S_{2i-1} S 2 i − 1 ,否则选 S 2 i S_{2i} S 2 i )共 n n n 个集合,覆盖了每个 m + i m+i m + i ;每个子句被某个真文字满足,从而被相应的集合覆盖。
(⇐ \Leftarrow ⇐ )设至多 n n n 个集合覆盖了 { 1 , … , m + n } \{1,\dots,m+n\} { 1 , … , m + n } 。元素 m + i m+i m + i 只在 S 2 i − 1 , S 2 i S_{2i-1},S_{2i} S 2 i − 1 , S 2 i 中出现,故每个 i i i 至少选了二者之一;共至多 n n n 个集合,于是恰好选了其中之一。令 u i = 1 u_i=1 u i = 1 当且仅当 S 2 i − 1 S_{2i-1} S 2 i − 1 被选中,则所选集合恰为 { S 2 i − u i } \{S_{2i-u_i}\} { S 2 i − u i } ,它们覆盖 { 1 , … , m } \{1,\dots,m\} { 1 , … , m } ,即每个子句都被某个真文字满足。□ \square □
新元素 m + i m+i m + i 的作用是「恰选其一 」的约束:它把集合覆盖的自由选择限制为一个赋值。
3.2 顶点覆盖、独立集与团# 顶点覆盖 :给定图 G G G 与整数 K K K ,是否存在至多 K K K 个顶点,使每条边至少有一个端点在其中?
团 :给定图 G G G 与整数 K K K ,是否存在至少 K K K 个顶点构成的完全子图?
设 G = ( V , E ) G=(V,E) G = ( V , E ) ,G ˉ = ( V , E ˉ ) \bar G=(V,\bar E) G ˉ = ( V , E ˉ ) 为其补图(e ∈ E ˉ ⟺ e ∉ E e\in\bar E\iff e\notin E e ∈ E ˉ ⟺ e ∈ / E )。则
S S S 是 G G G 的独立集 ⟺ \iff ⟺ V ∖ S V\setminus S V ∖ S 是 G G G 的顶点覆盖;S S S 是 G G G 的独立集 ⟺ \iff ⟺ S S S 是 G ˉ \bar G G ˉ 的团。从而顶点覆盖与团都是 NP 完全的。
(1)S S S 是独立集 ⟺ \iff ⟺ 没有边的两个端点都在 S S S 中 ⟺ \iff ⟺ 每条边至少有一个端点在 V ∖ S V\setminus S V ∖ S 中。
(2)S S S 中任意两点在 G G G 中不相邻 ⟺ \iff ⟺ 在 G ˉ \bar G G ˉ 中相邻。
于是 ⟨ G , k ⟩ ↦ ⟨ G , n − k ⟩ \langle G,k\rangle\mapsto\langle G,n-k\rangle ⟨ G , k ⟩ ↦ ⟨ G , n − k ⟩ 是 I N D S E T ≤ p V C \mathrm{INDSET}\le_p\mathrm{VC} INDSET ≤ p VC ,⟨ G , k ⟩ ↦ ⟨ G ˉ , k ⟩ \langle G,k\rangle\mapsto\langle\bar G,k\rangle ⟨ G , k ⟩ ↦ ⟨ G ˉ , k ⟩ 是 I N D S E T ≤ p C L I Q U E \mathrm{INDSET}\le_p\mathrm{CLIQUE} INDSET ≤ p CLIQUE ,二者都是多项式时间的。两个问题显然属于 NP,由独立集的 NP 完全性即得。□ \square □
三者在计算上是等价的。另外,顶点覆盖是集合覆盖的特例:令 S v = { e ∈ E : v ∈ e } S_v=\{e\in E:v\in e\} S v = { e ∈ E : v ∈ e } ,以边集为全集,则顶点覆盖即用至多 K K K 个 S v S_v S v 覆盖 E E E 。这给出了集合覆盖 NP 难的另一个证明(V C ≤ p S E T C O V E R \mathrm{VC}\le_p\mathrm{SETCOVER} VC ≤ p SETCOVER )。
4. 数值型# 对算术问题,输入的整数以二进制 编码,多项式时间归约必须是二进制编码长度的多项式。因此构造中出现的数可以是指数大的,只要位数是多项式的。
4.1 子集和# 子集和 (SUBSET-SUM):给定自然数 w 1 , … , w n w_1,\dots,w_n w 1 , … , w n 与整数 W W W ,是否存在子集之和恰为 W W W ?例如 { 1 , 4 , 16 , 64 , 256 , 1040 , 1041 , 1093 , 1284 , 1344 } \{1,4,16,64,256,1040,1041,1093,1284,1344\} { 1 , 4 , 16 , 64 , 256 , 1040 , 1041 , 1093 , 1284 , 1344 } ,W = 3754 W=3754 W = 3754 :答案为是,1 + 16 + 64 + 256 + 1040 + 1093 + 1284 = 3754 1+16+64+256+1040+1093+1284=3754 1 + 16 + 64 + 256 + 1040 + 1093 + 1284 = 3754 。
3 S A T ≤ p S U B S E T - S U M \mathrm{3SAT}\le_p\mathrm{SUBSET\text{-}SUM} 3SAT ≤ p SUBSET - SUM ,从而子集和是 NP 完全的。
设 3SAT 实例 Φ \Phi Φ 有 n n n 个变量、k k k 个子句。构造 2 n + 2 k 2n+2k 2 n + 2 k 个十进制整数,每个有 n + k n+k n + k 位:前 n n n 位对应变量,后 k k k 位对应子句。
对每个变量 x i x_i x i ,构造两个数 t i t_i t i (代表 x i x_i x i )与 f i f_i f i (代表 x ˉ i \bar x_i x ˉ i ):二者在变量位 i i i 上为 1;t i t_i t i 在 x i x_i x i 出现的子句位上为 1,f i f_i f i 在 x ˉ i \bar x_i x ˉ i 出现的子句位上为 1;其余位为 0。 对每个子句 C j C_j C j ,构造两个填充数 ,只在子句位 j j j 上分别为 1 和 2。 目标 W W W 在每个变量位上为 1,每个子句位上为 4。 例如 C 1 = x ˉ ∨ y ∨ z C_1=\bar x\vee y\vee z C 1 = x ˉ ∨ y ∨ z ,C 2 = x ∨ y ˉ ∨ z C_2=x\vee\bar y\vee z C 2 = x ∨ y ˉ ∨ z ,C 3 = x ˉ ∨ y ˉ ∨ z ˉ C_3=\bar x\vee\bar y\vee\bar z C 3 = x ˉ ∨ y ˉ ∨ z ˉ :
x x x y y y z z z C 1 C_1 C 1 C 2 C_2 C 2 C 3 C_3 C 3 数值 x x x 1 0 0 0 1 0 100,010 x ˉ \bar x x ˉ 1 0 0 1 0 1 100,101 y y y 0 1 0 1 0 0 10,100 y ˉ \bar y y ˉ 0 1 0 0 1 1 10,011 z z z 0 0 1 1 1 0 1,110 z ˉ \bar z z ˉ 0 0 1 0 0 1 1,001 填充 0 0 0 1 0 0 100 填充 0 0 0 2 0 0 200 填充 0 0 0 0 1 0 10 填充 0 0 0 0 2 0 20 填充 0 0 0 0 0 1 1 填充 0 0 0 0 0 2 2 W W W 1 1 1 4 4 4 111,444
不进位 :每个变量位上至多两个 1;每个子句位上至多 3 个文字的 1 加上填充数 1 + 2 1+2 1 + 2 ,和至多 6 < 10 6<10 6 < 10 。故任何子集之和中各位独立相加,「和等于 W W W 」等价于「每一位都相等」。
(⇒ \Rightarrow ⇒ )设赋值满足 Φ \Phi Φ 。为真的文字选取对应的数(每个 i i i 恰选 t i , f i t_i,f_i t i , f i 之一),变量位都为 1。子句 C j C_j C j 中真文字有 s ∈ { 1 , 2 , 3 } s\in\{1,2,3\} s ∈ { 1 , 2 , 3 } 个,子句位 j j j 已得 s s s ,再从两个填充数中选出和为 4 − s ∈ { 3 , 2 , 1 } 4-s\in\{3,2,1\} 4 − s ∈ { 3 , 2 , 1 } 的那些即可。
(⇐ \Leftarrow ⇐ )设某子集之和为 W W W 。变量位为 1 迫使每个 i i i 恰选 t i , f i t_i,f_i t i , f i 之一,据此定义赋值。子句位 j j j 为 4,而填充数至多贡献 3 3 3 ,故至少有一个所选文字数在该位上为 1,即 C j C_j C j 含一个真文字。□ \square □
例:表中实例的一个解
赋值 x = 0 , y = 0 , z = 1 x=0,\ y=0,\ z=1 x = 0 , y = 0 , z = 1 满足三个子句(C 1 , C 3 C_1,C_3 C 1 , C 3 由 x ˉ \bar x x ˉ ,C 2 C_2 C 2 由 y ˉ \bar y y ˉ )。选取真文字 x ˉ , y ˉ , z \bar x,\bar y,z x ˉ , y ˉ , z 对应的数:
100,101 + 10,011 + 1,110 = 111,222 , 100{,}101+10{,}011+1{,}110=111{,}222, 100 , 101 + 10 , 011 + 1 , 110 = 111 , 222 , 三个子句位各得 2 2 2 (每个子句恰有两个真文字),再各取填充数 2 2 2 :111,222 + 200 + 20 + 2 = 111,444 = W 111{,}222+200+20+2=111{,}444=W 111 , 222 + 200 + 20 + 2 = 111 , 444 = W 。反过来,若某个子句一个真文字也没有,该位只能靠填充数凑到 1 + 2 = 3 < 4 1+2=3<4 1 + 2 = 3 < 4 ,这就是「填充数至多补到 3」的作用。
伪多项式算法与弱 NP 完全
子集和有 O ( n W ) O(nW) O ( nW ) 的动态规划:O P T ( i , w ) \mathrm{OPT}(i,w) OPT ( i , w ) 表示前 i i i 个数能否凑出 w w w 。这与 NP 完全性并不矛盾:W W W 的输入长度只有 log W \log W log W ,O ( n W ) O(nW) O ( nW ) 是输入长度的指数 ,称为伪多项式 时间。上述归约中的数有 n + k n+k n + k 位十进制数字,是指数大的。若数以一元编码,子集和便属于 P;像子集和这样只在数值很大时才困难的问题称为弱 NP 完全 ,而在数值为输入长度多项式时仍 NP 完全的问题(如 3-PARTITION)称为强 NP 完全 。
4.2 划分# 划分 (PARTITION):给定自然数 v 1 , … , v m v_1,\dots,v_m v 1 , … , v m ,能否把它们分成两组,使两组之和都等于 1 2 ∑ i v i \frac12\sum_i v_i 2 1 ∑ i v i ?S U B S E T - S U M ≤ p P A R T I T I O N \mathrm{SUBSET\text{-}SUM}\le_p\mathrm{PARTITION} SUBSET - SUM ≤ p PARTITION 。
设 W , w 1 , … , w n W,w_1,\dots,w_n W , w 1 , … , w n 为子集和实例,记 Σ = ∑ i w i \Sigma=\sum_i w_i Σ = ∑ i w i (不妨设 W ≤ Σ W\le\Sigma W ≤ Σ )。构造 m = n + 2 m=n+2 m = n + 2 个数:
v i = w i ( i ≤ n ) , v n + 1 = 2 Σ − W , v n + 2 = Σ + W . v_i=w_i\ (i\le n),\qquad v_{n+1}=2\Sigma-W,\qquad v_{n+2}=\Sigma+W. v i = w i ( i ≤ n ) , v n + 1 = 2Σ − W , v n + 2 = Σ + W . 总和为 4 Σ 4\Sigma 4Σ ,每组应为 2 Σ 2\Sigma 2Σ 。而 v n + 1 + v n + 2 = 3 Σ > 2 Σ v_{n+1}+v_{n+2}=3\Sigma>2\Sigma v n + 1 + v n + 2 = 3Σ > 2Σ ,二者必在不同组中。含 v n + 1 v_{n+1} v n + 1 的一组中其余元素之和为 2 Σ − ( 2 Σ − W ) = W 2\Sigma-(2\Sigma-W)=W 2Σ − ( 2Σ − W ) = W ,它们都是原来的 w i w_i w i ;反之,若 { w i } i ∈ A \{w_i\}_{i\in A} { w i } i ∈ A 之和为 W W W ,则 A ∪ { n + 1 } A\cup\{n+1\} A ∪ { n + 1 } 与其余元素构成一个划分。□ \square □
4.3 带释放时间的调度# 调度 (SCHEDULE):给定 n n n 个任务,任务 j j j 有处理时间 t j t_j t j 、释放时间 r j r_j r j 与截止时间 d j d_j d j 。能否在一台机器上安排所有任务,使任务 j j j 在区间 [ r j , d j ] [r_j,d_j] [ r j , d j ] 内占用一段连续的 t j t_j t j 时间?S U B S E T - S U M ≤ p S C H E D U L E \mathrm{SUBSET\text{-}SUM}\le_p\mathrm{SCHEDULE} SUBSET - SUM ≤ p SCHEDULE 。
设 W , w 1 , … , w n W,w_1,\dots,w_n W , w 1 , … , w n 为子集和实例,Σ = ∑ i w i \Sigma=\sum_i w_i Σ = ∑ i w i 。构造 n + 1 n+1 n + 1 个任务:
任务 j ∈ [ n ] j\in[n] j ∈ [ n ] :t j = w j t_j=w_j t j = w j ,r j = 0 r_j=0 r j = 0 ,d j = Σ + 1 d_j=\Sigma+1 d j = Σ + 1 ; 任务 0 0 0 :t 0 = 1 t_0=1 t 0 = 1 ,r 0 = W r_0=W r 0 = W ,d 0 = W + 1 d_0=W+1 d 0 = W + 1 。 任务 0 只能占据 [ W , W + 1 ] [W,W+1] [ W , W + 1 ] 。总处理时间为 Σ + 1 \Sigma+1 Σ + 1 ,恰等于时间窗口 [ 0 , Σ + 1 ] [0,\Sigma+1] [ 0 , Σ + 1 ] 的长度,故机器不能有任何空闲:[ 0 , W ] [0,W] [ 0 , W ] 必须被若干任务恰好填满,它们的 w j w_j w j 之和为 W W W 。反之,若 { w j } j ∈ A \{w_j\}_{j\in A} { w j } j ∈ A 之和为 W W W ,把 A A A 中的任务依次排在 [ 0 , W ] [0,W] [ 0 , W ] ,任务 0 排在 [ W , W + 1 ] [W,W+1] [ W , W + 1 ] ,其余任务排在 [ W + 1 , Σ + 1 ] [W+1,\Sigma+1] [ W + 1 , Σ + 1 ] 即可。□ \square □
Fig 3 子集和到调度的归约:任务 0 卡住 [ W , W + 1 ] [W,W+1] [ W , W + 1 ] ,机器不能空闲 与贪心 中最小化最大延迟的问题对比:没有释放时间时,按截止时间排序即为最优;加入释放时间后,问题就变成 NP 完全的。
5. 全景:NP 完全问题的等价类# 以上问题都是 NP 完全的,彼此之间都可以多项式归约。Karp(1972)列出了 21 个 NP 完全问题,包括 SAT、团、集合覆盖、顶点覆盖、哈密顿圈、背包、划分、图着色等,确立了 NP 完全性在组合优化中的普遍地位(Karp 因此获得 1985 年图灵奖)。Garey 与 Johnson 的 Computers and Intractability (1979)是 NP 完全问题的经典目录。
6. 判定与搜索# NP 是用判定问题定义的,而实际中更关心搜索问题:若解存在,把它找出来。搜索至少和判定一样难,所以若 P ≠ N P \mathrm P\ne\mathrm{NP} P = NP ,NP 完全问题的两个版本都不能在多项式时间内求解。反过来,二者其实是等价的:
设 P = N P \mathrm P=\mathrm{NP} P = NP 。则对任意 NP 语言 L L L 及其验证器 M M M ,存在多项式时间图灵机 B B B ,在输入 x ∈ L x\in L x ∈ L 上输出 x x x 的一个证书。
即证:若 P = N P \mathrm P=\mathrm{NP} P = NP ,则对任意多项式时间的 M M M 与多项式 p p p ,存在多项式时间的 B B B ,使对任意 x ∈ { 0 , 1 } n x\in\{0,1\}^n x ∈ { 0 , 1 } n ,若存在 u ∈ { 0 , 1 } p ( n ) u\in\{0,1\}^{p(n)} u ∈ { 0 , 1 } p ( n ) 使 M ( x , u ) = 1 M(x,u)=1 M ( x , u ) = 1 ,则 ∣ B ( x ) ∣ = p ( n ) |B(x)|=p(n) ∣ B ( x ) ∣ = p ( n ) 且 M ( x , B ( x ) ) = 1 M(x,B(x))=1 M ( x , B ( x )) = 1 。
SAT 的情形 :设 A A A 是判定 SAT 的多项式时间算法。在可满足的 n n n 变量公式 φ \varphi φ 上,先代入 x 1 = 0 x_1=0 x 1 = 0 ,用 A A A 判定所得公式是否可满足;若是,固定 x 1 = 0 x_1=0 x 1 = 0 ,否则固定 x 1 = 1 x_1=1 x 1 = 1 (此时它必可满足)。对 x 2 , … , x n x_2,\dots,x_n x 2 , … , x n 依次重复,最后得到满足赋值。共调用 A A A 至多 2 n + 1 2n+1 2 n + 1 次(事实上 n + 1 n+1 n + 1 次即可),外加多项式时间的代入运算。
一般情形 :Cook–Levin 定理中从 L L L 到 SAT 的归约是 Levin 归约:存在多项式时间可计算的 f f f ,不仅 x ∈ L ⟺ f ( x ) ∈ S A T x\in L\iff f(x)\in\mathrm{SAT} x ∈ L ⟺ f ( x ) ∈ SAT ,而且 f ( x ) f(x) f ( x ) 的满足赋值可以高效地映射回 x x x 的证书。于是先用上面的算法求出 f ( x ) f(x) f ( x ) 的满足赋值,再映射回去即可。□ \square □
算法实现 \begin{algorithm}
\caption{SAT-Search:用判定算法求满足赋值}
\begin{algorithmic}
\PROCEDURE{FindAssignment}{$\varphi(x_1, \dots, x_n)$}
\IF{\CALL{A}{$\varphi$} $= 0$}
\RETURN 不可满足
\ENDIF
\FOR{$i \gets 1$ \TO $n$}
\IF{\CALL{A}{$\varphi|_{x_i = 0}$} $= 1$}
\STATE $a_i \gets 0$,$\varphi \gets \varphi|_{x_i = 0}$
\ELSE
\STATE $a_i \gets 1$,$\varphi \gets \varphi|_{x_i = 1}$ \COMMENT{$\varphi$ 可满足,故此分支必可满足}
\ENDIF
\ENDFOR
\RETURN $(a_1, \dots, a_n)$
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm} 这种「固定一个变量,问剩下的是否仍有解」的性质称为自归约性 。图问题也有类似的写法:要找哈密顿圈,依次尝试删去每条边,若删去后判定算法仍回答「有哈密顿圈」就真的删掉,否则保留。最后剩下的图仍有哈密顿圈,且其中每条边都不可删,所以它就是一个哈密顿圈,共调用判定算法 m + 1 m+1 m + 1 次。同理,优化问题也可以用二分归约到判定问题,例如先二分求出最大独立集的大小 k ∗ k^* k ∗ ,再逐个尝试删去顶点、保持最大独立集大小不变,即可找出一个最大独立集。
7. coNP# 对语言 L L L ,记其补为 L ‾ = { 0 , 1 } ∗ ∖ L \overline L=\{0,1\}^*\setminus L L = { 0 , 1 } ∗ ∖ L 。定义
c o N P = { L : L ‾ ∈ N P } . \mathrm{coNP}=\{L:\overline L\in\mathrm{NP}\}. coNP = { L : L ∈ NP } . 等价地,L ∈ c o N P L\in\mathrm{coNP} L ∈ coNP 当且仅当存在多项式 p p p 与多项式时间图灵机 M M M ,使对任意 x x x ,
x ∈ L ⟺ ∀ u ∈ { 0 , 1 } p ( ∣ x ∣ ) , M ( x , u ) = 1. x\in L\iff\forall u\in\{0,1\}^{p(|x|)},\ M(x,u)=1. x ∈ L ⟺ ∀ u ∈ { 0 , 1 } p ( ∣ x ∣ ) , M ( x , u ) = 1. NP 是「存在简短的肯定 证明」,coNP 是「存在简短的否定 证明」(反例)。注意 coNP 不是 NP 的补集:二者有非空的交,P ⊆ N P ∩ c o N P \mathrm P\subseteq\mathrm{NP}\cap\mathrm{coNP} P ⊆ NP ∩ coNP (P 对取补封闭)。例如 S A T ‾ = { φ : φ is unsatisfiable } \overline{\mathrm{SAT}}=\{\varphi:\varphi\ \text{is unsatisfiable}\} SAT = { φ : φ is unsatisfiable } 属于 coNP;合数属于 NP,故素数属于 coNP(又由 Pratt 证书属于 NP)。
类似地定义 coNP 完全:属于 coNP,且 coNP 中的每个语言都可 Karp 归约到它。
T A U T O L O G Y = { φ : φ is a Boolean formula satisfied by every assignment } \mathrm{TAUTOLOGY}=\{\varphi:\varphi\ \text{is a Boolean formula satisfied by every assignment}\} TAUTOLOGY = { φ : φ is a Boolean formula satisfied by every assignment } 是 coNP 完全的。
TAUTOLOGY 显然属于 coNP:对每个赋值 u u u ,检查 φ ( u ) = 1 \varphi(u)=1 φ ( u ) = 1 。
对任意 L ∈ c o N P L\in\mathrm{coNP} L ∈ coNP ,有 L ‾ ∈ N P \overline L\in\mathrm{NP} L ∈ NP 。对 L ‾ \overline L L 应用 Cook–Levin 归约,对每个输入 x x x 得到公式 φ x \varphi_x φ x ,使 φ x \varphi_x φ x 可满足 ⟺ x ∈ L ‾ \iff x\in\overline L ⟺ x ∈ L 。于是
¬ φ x ∈ T A U T O L O G Y ⟺ φ x is unsatisfiable ⟺ x ∈ L , \neg\varphi_x\in\mathrm{TAUTOLOGY}\iff\varphi_x\ \text{is unsatisfiable}\iff x\in L, ¬ φ x ∈ TAUTOLOGY ⟺ φ x is unsatisfiable ⟺ x ∈ L , x ↦ ¬ φ x x\mapsto\neg\varphi_x x ↦ ¬ φ x 即为 L ≤ p T A U T O L O G Y L\le_p\mathrm{TAUTOLOGY} L ≤ p TAUTOLOGY 。□ \square □
这里 ¬ φ x \neg\varphi_x ¬ φ x 不再是 CNF(而是 DNF),所以 TAUTOLOGY 要对一般布尔公式定义。
若 P = N P \mathrm P=\mathrm{NP} P = NP ,则 P = N P = c o N P \mathrm P=\mathrm{NP}=\mathrm{coNP} P = NP = coNP 。
L ∈ c o N P ⟺ L ‾ ∈ N P = P ⟺ L ∈ P L\in\mathrm{coNP}\iff\overline L\in\mathrm{NP}=\mathrm P\iff L\in\mathrm P L ∈ coNP ⟺ L ∈ NP = P ⟺ L ∈ P 。□ \square □ 逆否地,证明 N P ≠ c o N P \mathrm{NP}\ne\mathrm{coNP} NP = coNP 就证明了 P ≠ N P \mathrm P\ne\mathrm{NP} P = NP 。普遍的猜想是
猜想 1 :N P ≠ c o N P \mathrm{NP}\ne\mathrm{coNP} NP = coNP ,等价于说不可满足的 CNF 公式没有简短的证明;
猜想 2 :P ≠ N P ∩ c o N P \mathrm P\ne\mathrm{NP}\cap\mathrm{coNP} P = NP ∩ coNP ,与整数分解等价的问题是这一猜想的主要候选。
若 N P ≠ c o N P \mathrm{NP}\ne\mathrm{coNP} NP = coNP ,则 N P ∩ c o N P \mathrm{NP}\cap\mathrm{coNP} NP ∩ coNP 中的语言都不是 NP 完全的。
设 L ∈ N P ∩ c o N P L\in\mathrm{NP}\cap\mathrm{coNP} L ∈ NP ∩ coNP 是 NP 完全的。对任意 L ′ ∈ N P L'\in\mathrm{NP} L ′ ∈ NP ,有 L ′ ≤ p L L'\le_p L L ′ ≤ p L ,同一个归约 f f f 也满足 x ∈ L ′ ‾ ⟺ f ( x ) ∈ L ‾ x\in\overline{L'}\iff f(x)\in\overline L x ∈ L ′ ⟺ f ( x ) ∈ L ,即 L ′ ‾ ≤ p L ‾ \overline{L'}\le_p\overline L L ′ ≤ p L 。而 L ‾ ∈ N P \overline L\in\mathrm{NP} L ∈ NP ,NP 对 Karp 归约封闭(把归约与验证器复合),故 L ′ ‾ ∈ N P \overline{L'}\in\mathrm{NP} L ′ ∈ NP ,即 L ′ ∈ c o N P L'\in\mathrm{coNP} L ′ ∈ coNP 。于是 N P ⊆ c o N P \mathrm{NP}\subseteq\mathrm{coNP} NP ⊆ coNP ;取补得 c o N P ⊆ N P \mathrm{coNP}\subseteq\mathrm{NP} coNP ⊆ NP ,从而 N P = c o N P \mathrm{NP}=\mathrm{coNP} NP = coNP ,矛盾。□ \square □ 所以整数分解(判定版本属于 N P ∩ c o N P \mathrm{NP}\cap\mathrm{coNP} NP ∩ coNP )很可能不是 NP 完全的。NP 中是否一定存在既不在 P 中、又非 NP 完全的问题?
若 P ≠ N P \mathrm P\ne\mathrm{NP} P = NP ,则存在语言 L ∈ N P ∖ P L\in\mathrm{NP}\setminus\mathrm P L ∈ NP ∖ P ,且 L L L 不是 NP 完全的。 Ladner 构造的语言是人为的;自然的候选是整数分解与图同构。在 P ≠ N P ∩ c o N P ≠ N P \mathrm P\ne\mathrm{NP}\cap\mathrm{coNP}\ne\mathrm{NP} P = NP ∩ coNP = NP 的假设下,世界图景是:P 位于 N P ∩ c o N P \mathrm{NP}\cap\mathrm{coNP} NP ∩ coNP 内部;NPC 位于 NP 的「边缘」,coNPC 位于 coNP 的「边缘」,二者都与 N P ∩ c o N P \mathrm{NP}\cap\mathrm{coNP} NP ∩ coNP 不交。
Fig 4 P、NP 与 coNP 的猜想图景 8. EXP 与 NEXP# E X P = ⋃ c ≥ 0 D T I M E ( 2 n c ) , N E X P = ⋃ c ≥ 0 N T I M E ( 2 n c ) . \mathrm{EXP}=\bigcup_{c\ge0}\mathrm{DTIME}(2^{n^c}),\qquad\mathrm{NEXP}=\bigcup_{c\ge0}\mathrm{NTIME}(2^{n^c}). EXP = c ≥ 0 ⋃ DTIME ( 2 n c ) , NEXP = c ≥ 0 ⋃ NTIME ( 2 n c ) . P ⊆ N P ⊆ E X P ⊆ N E X P \mathrm P\subseteq\mathrm{NP}\subseteq\mathrm{EXP}\subseteq\mathrm{NEXP} P ⊆ NP ⊆ EXP ⊆ NEXP ;若 E X P ≠ N E X P \mathrm{EXP}\ne\mathrm{NEXP} EXP = NEXP ,则 P ≠ N P \mathrm P\ne\mathrm{NP} P = NP 。 (1)前两个包含关系已证,最后一个因确定性机器是非确定性机器的特例。
(2)只证逆否命题:设 P = N P \mathrm P=\mathrm{NP} P = NP ,证明 E X P = N E X P \mathrm{EXP}=\mathrm{NEXP} EXP = NEXP 。设 L ∈ N T I M E ( 2 n c ) L\in\mathrm{NTIME}(2^{n^c}) L ∈ NTIME ( 2 n c ) 由 NDTM M M M 判定。
断言 :L p a d = { ⟨ x , 1 2 ∣ x ∣ c ⟩ : x ∈ L } ∈ N P L_{\mathrm{pad}}=\{\langle x,1^{2^{|x|^c}}\rangle:x\in L\}\in\mathrm{NP} L pad = {⟨ x , 1 2 ∣ x ∣ c ⟩ : x ∈ L } ∈ NP 。构造 NDTM:给定 y y y ,先检查是否存在 z z z 使 y = ⟨ z , 1 2 ∣ z ∣ c ⟩ y=\langle z,1^{2^{|z|^c}}\rangle y = ⟨ z , 1 2 ∣ z ∣ c ⟩ ,若不是则输出 0;否则运行 M ( z ) M(z) M ( z ) 并输出其结果。M ( z ) M(z) M ( z ) 运行 O ( 2 ∣ z ∣ c ) O(2^{|z|^c}) O ( 2 ∣ z ∣ c ) 步,这是 ∣ y ∣ |y| ∣ y ∣ 的线性函数,故整个机器关于 ∣ y ∣ |y| ∣ y ∣ 是多项式时间的。
于是 L p a d ∈ N P = P L_{\mathrm{pad}}\in\mathrm{NP}=\mathrm P L pad ∈ NP = P 。要判定 x ∈ L x\in L x ∈ L ,先写出填充后的串 y = ⟨ x , 1 2 ∣ x ∣ c ⟩ y=\langle x,1^{2^{|x|^c}}\rangle y = ⟨ x , 1 2 ∣ x ∣ c ⟩ (用时 O ( 2 ∣ x ∣ c ) O(2^{|x|^c}) O ( 2 ∣ x ∣ c ) ),再用 L p a d L_{\mathrm{pad}} L pad 的多项式时间算法判定 y y y ,用时 p o l y ( ∣ y ∣ ) = 2 O ( ∣ x ∣ c ) \mathrm{poly}(|y|)=2^{O(|x|^c)} poly ( ∣ y ∣ ) = 2 O ( ∣ x ∣ c ) 。故 L ∈ E X P L\in\mathrm{EXP} L ∈ EXP 。□ \square □
这一技术称为填充 (padding):人为地把输入变长,使相对于输入长度的运行时间「变小」。它说明类之间的相等 会向上传递(P = N P ⇒ E X P = N E X P \mathrm P=\mathrm{NP}\Rightarrow\mathrm{EXP}=\mathrm{NEXP} P = NP ⇒ EXP = NEXP ),从而分离 会向下传递。
9. P vs NP 的现状# NP 的哲学意义在于:识别答案的正确性往往比想出答案容易。它与数学证明紧密相关:能否在证明长度的多项式时间内找到 证明?P = N P \mathrm P=\mathrm{NP} P = NP 与 P ≠ N P \mathrm P\ne\mathrm{NP} P = NP 各自会带来什么?围绕 NP 还发展出了 PCP 定理、唯一游戏猜想(UGC)、PPAD、近似算法等方向。
P vs NP 是 Clay 数学研究所的七个千禧年大奖难题之一(其中 Poincaré 猜想已被解决)。证明 P = N P \mathrm P=\mathrm{NP} P = NP 的人(如果能给出实用的算法)大概能顺手解决其余五个,带回六张百万美元支票。复杂性理论学者普遍相信 P ≠ N P \mathrm P\ne\mathrm{NP} P = NP ,但所有尝试都失败了。主要思路有:
对角线法 :能否像构造 UC 那样,直接构造一个 NP 语言,使每个多项式时间算法都在某个输入上出错?
电路复杂性 :只需证明某个 NP 完全问题不能被较小的与、或、非门电路计算;
证明复杂性 :若能证明 TAUTOLOGY 没有简短的证明,即得 N P ≠ c o N P \mathrm{NP}\ne\mathrm{coNP} NP = coNP ,从而 P ≠ N P \mathrm P\ne\mathrm{NP} P = NP 。
新的希望包括 Mulmuley 与 Sohoni 的几何复杂性理论 ,它涉及代数几何、表示论、量子群,并需要一个类似 Riemann 假设的命题;Mulmuley 估计这一纲领需要约 100 年才能完成(如果它可行的话)。2010 年 Deolalikar 用统计物理与有限模型论宣称证明了 P ≠ N P \mathrm P\ne\mathrm{NP} P = NP ,但证明既不正确,也没有实质性地推进对问题的理解。P vs NP 至今仍是公开问题。
三重障碍
已知的几类技术被证明不足以解决 P vs NP:相对化 (Baker–Gill–Solovay 1975):存在预言机 A , B A,B A , B 使 P A = N P A \mathrm P^A=\mathrm{NP}^A P A = NP A 而 P B ≠ N P B \mathrm P^B\ne\mathrm{NP}^B P B = NP B ,而纯粹的对角线法与模拟在加入预言机后仍然成立,故不能单独解决问题;自然证明 (Razborov–Rudich 1994):在单向函数存在的假设下,一大类电路下界论证无法证明 P ≠ N P \mathrm P\ne\mathrm{NP} P = NP ;代数化 (Aaronson–Wigderson 2008)则堵住了对相对化的代数推广。
10. 小结# 归约 变量部件 子句部件 / 约束 S A T ≤ p d H A M P A T H \mathrm{SAT}\le_p\mathrm{dHAMPATH} SAT ≤ p dHAMPATH 双向链,走向即赋值 子句顶点只能从方向正确的链绕道访问 S A T ≤ p S E T C O V E R \mathrm{SAT}\le_p\mathrm{SETCOVER} SAT ≤ p SETCOVER S i , t , S i , f S_{i,t},S_{i,f} S i , t , S i , f 新元素 m + i m+i m + i 迫使恰选其一 I N D S E T ≤ p V C , C L I Q U E \mathrm{INDSET}\le_p\mathrm{VC},\mathrm{CLIQUE} INDSET ≤ p VC , CLIQUE — 取补集、取补图 3 S A T ≤ p S U B S E T - S U M \mathrm{3SAT}\le_p\mathrm{SUBSET\text{-}SUM} 3SAT ≤ p SUBSET - SUM 变量位为 1 子句位为 4,填充数补足;各位不进位 S U B S E T - S U M ≤ p P A R T I T I O N \mathrm{SUBSET\text{-}SUM}\le_p\mathrm{PARTITION} SUBSET - SUM ≤ p PARTITION — 两个大数 2 Σ − W 2\Sigma-W 2Σ − W 、Σ + W \Sigma+W Σ + W 必然分开 S U B S E T - S U M ≤ p S C H E D U L E \mathrm{SUBSET\text{-}SUM}\le_p\mathrm{SCHEDULE} SUBSET - SUM ≤ p SCHEDULE — 任务 0 卡住 [ W , W + 1 ] [W,W+1] [ W , W + 1 ] ,无空闲迫使 [ 0 , W ] [0,W] [ 0 , W ] 恰好填满
类 定义 完全问题 NP ∃ u \exists u ∃ u ,多项式时间验证SAT、3SAT、INDSET、…… coNP ∀ u \forall u ∀ u ,多项式时间验证TAUTOLOGY、S A T ‾ \overline{\mathrm{SAT}} SAT EXP / NEXP 指数时间(非)确定性 —
NP 完全问题构成一个巨大的等价类,归约在其中自由穿行;搜索与判定也被证明等价。理论告诉我们,若 P ≠ N P \mathrm P\ne\mathrm{NP} P = NP ,就不能指望对这些问题同时做到「任意实例、精确最优、多项式时间」。但实践中的实例往往有特殊结构,下一章正是利用这些结构,见拓展可解性的边界 。