有了 SAT、3SAT 与独立集,证明一个新问题 XX 是 NP 完全的就有了固定的模板:先说明 X∈NPX\in\mathrm{NP},再把某个已知的 NP 完全问题归约到 XX。难点全在归约的设计:用部件模拟变量与子句,再用约束迫使部件的局部选择拼成一个全局一致的解。

1. 引入:归约的模板

已知 YY 是 NP 完全的,要证明 XX 是 NP 完全的。

第一步,X∈NPX\in\mathrm{NP}:指出证书,说明它长度多项式、可在多项式时间内验证。这一步通常是平凡的,但不能省略;

第二步,Y≤pXY\le_p X:给出多项式时间变换 ff,并证明 y∈Y⇒f(y)∈Xy\in Y\Rightarrow f(y)\in X(由 YY 的解构造 XX 的解)与 f(y)∈X⇒y∈Yf(y)\in X\Rightarrow y\in Y(由 XX 的解读回 YY 的解)。

本章的归约关系如下,箭头 A→BA\to B 表示 A≤pBA\le_p B:

Fig 1 本章的归约关系
Fig 1 本章的归约关系

按问题的结构,可以粗分为序列型(哈密顿路)、覆盖与打包型(集合覆盖、顶点覆盖、独立集、团)与数值型(子集和、划分、调度)三类。

2. 序列型:有向哈密顿路

有向图中的有向哈密顿路是恰好经过每个顶点一次的有向路径。dHAMPATH\mathrm{dHAMPATH} 为全体含有向哈密顿路的有向图构成的语言。
dHAMPATH 是 NP 完全的。

dHAMPATH 显然属于 NP(证书是顶点序列)。下面给出 SAT≤pdHAMPATH\mathrm{SAT}\le_p\mathrm{dHAMPATH}。

设 φ\varphi 是 nn 个变量、mm 个子句的 CNF 公式。构造有向图 GG,顶点包括:

  • 每个子句 CC 对应一个顶点 vCv_C,共 mm 个;
  • 起点 vstartv_{\mathrm{start}} 与终点 vendv_{\mathrm{end}};
  • 每个变量 uju_j 对应一条由 4m4m 个顶点组成的链 v1,…,v4mv_1,\dots,v_{4m},相邻的 vi,vi+1v_i,v_{i+1} 之间有双向边。

边包括:

  • vstartv_{\mathrm{start}} 到第 1 条链的两个端点;第 jj 条链的两个端点到第 j+1j+1 条链的两个端点(j∈[n−1]j\in[n-1]);第 nn 条链的两个端点到 vendv_{\mathrm{end}};
  • 对第 ii 个子句 CC 与其中出现的变量 uju_j,在第 jj 条链上取专属于 CC 的一对相邻顶点 v4i−2,v4i−1v_{4i-2},v_{4i-1}(不同子句的「插口」互不相邻,中间隔有缓冲顶点):若 CC 含 uju_j,加边 v4i−2→vC→v4i−1v_{4i-2}\to v_C\to v_{4i-1};若 CC 含 uˉj\bar u_j,则方向相反,加边 v4i−1→vC→v4i−2v_{4i-1}\to v_C\to v_{4i-2}。

于是从左到右走一条链表示 uj=1u_j=1,从右到左表示 uj=0u_j=0;子句顶点只能从「方向正确」的链上绕道访问。构造显然是多项式时间的。

(⇒\Rightarrow)设 uu 是满足赋值。从 vstartv_{\mathrm{start}} 出发依次走完各条链,最后到达 vendv_{\mathrm{end}}:uj=1u_j=1 时从左到右走第 jj 条链,uj=0u_j=0 时从右到左。每个子句 CC 至少有一个真文字,在该文字对应的链上,走到 CC 的插口时绕道 vCv_C 再回到链上即可。这样每个子句顶点恰被访问一次,得到哈密顿路。

(⇐\Leftarrow)设 PP 是哈密顿路。vstartv_{\mathrm{start}} 没有入边,vendv_{\mathrm{end}} 没有出边,故 PP 从 vstartv_{\mathrm{start}} 开始、在 vendv_{\mathrm{end}} 结束。关键观察:若 PP 走了链上的边 v→vCv\to v_C,则下一步必须走 vC→wv_C\to w,其中 ww 是 vv 在该插口中的相邻顶点;否则 PP 此后访问 ww 时会被「困住」:ww 的邻居(链上两侧的点与 vCv_C)都已访问过,ww 只能作为终点,与终点是 vendv_{\mathrm{end}} 矛盾。因此把子句顶点的绕道去掉后,PP 依次完整地走过每条链,且每条链要么从左到右、要么从右到左。令 PP 从左到右走第 jj 条链时 uj=1u_j=1,否则 uj=0u_j=0。PP 经过每个 vCv_C,而它只能从方向与某个文字一致的链上绕道,该文字在 uu 下为真,故 uu 满足 φ\varphi。□\square

Fig 2 $\varphi=(u_1\vee u_2)\wedge(\bar u_1\vee\bar u_2)$ 的构造与赋值 $u_1=1,\ u_2=0$ 对应的哈密顿路
Fig 2 φ=(u1∨u2)∧(uˉ1∨uˉ2)\varphi=(u_1\vee u_2)\wedge(\bar u_1\vee\bar u_2) 的构造与赋值 u1=1, u2=0u_1=1,\ u_2=0 对应的哈密顿路

部件的分工很清楚:链是变量部件,只有两种走法;绕道是子句部件,只在方向正确时可用;链与链的首尾相接保证每个变量恰好被「赋值」一次。

从 dHAMPATH 出发,哈密顿问题的各种变体都能用很小的改动得到:

有向哈密顿圈:在上面的构造里加一条边 vend→vstartv_{\mathrm{end}}\to v_{\mathrm{start}}。vstartv_{\mathrm{start}} 原本没有入边,所以任何哈密顿圈都必须经过这条新边,去掉它就是一条从 vstartv_{\mathrm{start}} 到 vendv_{\mathrm{end}} 的哈密顿路;反之亦然。故 dHAMCYCLE 是 NP 完全的。

无向哈密顿圈:把有向图的每个顶点 vv 拆成三个顶点 vin−vmid−voutv_{\mathrm{in}}-v_{\mathrm{mid}}-v_{\mathrm{out}},每条有向边 u→vu\to v 改成无向边 uout−vinu_{\mathrm{out}}-v_{\mathrm{in}}。vmidv_{\mathrm{mid}} 的度数为 2,哈密顿圈必须连续经过 vin,vmid,voutv_{\mathrm{in}},v_{\mathrm{mid}},v_{\mathrm{out}};而 voutv_{\mathrm{out}} 只与 vmidv_{\mathrm{mid}} 及各 winw_{\mathrm{in}} 相邻,沿圈的一个方向看,各个三元组都按 in →\to mid →\to out 的顺序经过,三元组之间的边都是某条 uout−vinu_{\mathrm{out}}-v_{\mathrm{in}},对应原图的有向边。故两个图同时有或没有哈密顿圈。

旅行商:再用上一章的 HAMCYCLE≤pTSP\mathrm{HAMCYCLE}\le_p\mathrm{TSP}。

拆点的技巧值得记住:用一个度数为 2 的中间点「钩住」两个端点,就把方向信息编码进了无向图。

3. 覆盖与打包型

3.1 集合覆盖

集合覆盖:给定有限集族 S1,…,SmS_1,\dots,S_m 与整数 KK,判定是否存在至多 KK 个集合覆盖 ⋃i=1mSi\bigcup_{i=1}^m S_i,即存在下标 i1,…,iKi_1,\dots,i_K 使 ⋃j=1KSij=⋃i=1mSi\bigcup_{j=1}^K S_{i_j}=\bigcup_{i=1}^m S_i。
集合覆盖是 NP 完全的。

集合覆盖显然属于 NP。下面给出 SAT≤pSETCOVER\mathrm{SAT}\le_p\mathrm{SETCOVER}。

设 φ\varphi 是 nn 个变量、mm 个子句的 CNF 公式。令 Si,tS_{i,t}(相应地 Si,fS_{i,f})为第 ii 个变量取真(相应地取假)时被满足的子句下标的集合,它们都是 {1,…,m}\{1,\dots,m\} 的子集,且这 2n2n 个集合之并为 {1,…,m}\{1,\dots,m\}(假定每个子句非空)。再为每个变量引入一个新元素 m+im+i:

S2i−1=Si,t∪{m+i},S2i=Si,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,

取 K=nK=n,全集为 {1,…,m+n}\{1,\dots,m+n\}。变换是多项式时间的。

(⇒\Rightarrow)若 uu 满足 φ\varphi,则 {S2i−ui:i=1,…,n}\{S_{2i-u_i}:i=1,\dots,n\}(ui=1u_i=1 时选 S2i−1S_{2i-1},否则选 S2iS_{2i})共 nn 个集合,覆盖了每个 m+im+i;每个子句被某个真文字满足,从而被相应的集合覆盖。

(⇐\Leftarrow)设至多 nn 个集合覆盖了 {1,…,m+n}\{1,\dots,m+n\}。元素 m+im+i 只在 S2i−1,S2iS_{2i-1},S_{2i} 中出现,故每个 ii 至少选了二者之一;共至多 nn 个集合,于是恰好选了其中之一。令 ui=1u_i=1 当且仅当 S2i−1S_{2i-1} 被选中,则所选集合恰为 {S2i−ui}\{S_{2i-u_i}\},它们覆盖 {1,…,m}\{1,\dots,m\},即每个子句都被某个真文字满足。□\square

新元素 m+im+i 的作用是「恰选其一」的约束:它把集合覆盖的自由选择限制为一个赋值。

3.2 顶点覆盖、独立集与团

顶点覆盖:给定图 GG 与整数 KK,是否存在至多 KK 个顶点,使每条边至少有一个端点在其中?

团:给定图 GG 与整数 KK,是否存在至少 KK 个顶点构成的完全子图?

设 G=(V,E)G=(V,E),Gˉ=(V,Eˉ)\bar G=(V,\bar E) 为其补图(e∈Eˉ  ⟺  e∉Ee\in\bar E\iff e\notin E)。则

  1. SS 是 GG 的独立集   ⟺  \iff V∖SV\setminus S 是 GG 的顶点覆盖;
  2. SS 是 GG 的独立集   ⟺  \iff SS 是 Gˉ\bar G 的团。

从而顶点覆盖与团都是 NP 完全的。

(1)SS 是独立集   ⟺  \iff 没有边的两个端点都在 SS 中   ⟺  \iff 每条边至少有一个端点在 V∖SV\setminus S 中。

(2)SS 中任意两点在 GG 中不相邻   ⟺  \iff 在 Gˉ\bar G 中相邻。

于是 ⟨G,k⟩↦⟨G,n−k⟩\langle G,k\rangle\mapsto\langle G,n-k\rangle 是 INDSET≤pVC\mathrm{INDSET}\le_p\mathrm{VC},⟨G,k⟩↦⟨Gˉ,k⟩\langle G,k\rangle\mapsto\langle\bar G,k\rangle 是 INDSET≤pCLIQUE\mathrm{INDSET}\le_p\mathrm{CLIQUE},二者都是多项式时间的。两个问题显然属于 NP,由独立集的 NP 完全性即得。□\square

三者在计算上是等价的。另外,顶点覆盖是集合覆盖的特例:令 Sv={e∈E:v∈e}S_v=\{e\in E:v\in e\},以边集为全集,则顶点覆盖即用至多 KK 个 SvS_v 覆盖 EE。这给出了集合覆盖 NP 难的另一个证明(VC≤pSETCOVER\mathrm{VC}\le_p\mathrm{SETCOVER})。

4. 数值型

对算术问题,输入的整数以二进制编码,多项式时间归约必须是二进制编码长度的多项式。因此构造中出现的数可以是指数大的,只要位数是多项式的。

4.1 子集和

子集和(SUBSET-SUM):给定自然数 w1,…,wnw_1,\dots,w_n 与整数 WW,是否存在子集之和恰为 WW?

例如 {1,4,16,64,256,1040,1041,1093,1284,1344}\{1,4,16,64,256,1040,1041,1093,1284,1344\},W=3754W=3754:答案为是,1+16+64+256+1040+1093+1284=37541+16+64+256+1040+1093+1284=3754。

3SAT≤pSUBSET-SUM\mathrm{3SAT}\le_p\mathrm{SUBSET\text{-}SUM},从而子集和是 NP 完全的。

设 3SAT 实例 Φ\Phi 有 nn 个变量、kk 个子句。构造 2n+2k2n+2k 个十进制整数,每个有 n+kn+k 位:前 nn 位对应变量,后 kk 位对应子句。

  • 对每个变量 xix_i,构造两个数 tit_i(代表 xix_i)与 fif_i(代表 xˉi\bar x_i):二者在变量位 ii 上为 1;tit_i 在 xix_i 出现的子句位上为 1,fif_i 在 xˉi\bar x_i 出现的子句位上为 1;其余位为 0。
  • 对每个子句 CjC_j,构造两个填充数,只在子句位 jj 上分别为 1 和 2。
  • 目标 WW 在每个变量位上为 1,每个子句位上为 4。

例如 C1=xˉ∨y∨zC_1=\bar x\vee y\vee z,C2=x∨yˉ∨zC_2=x\vee\bar y\vee z,C3=xˉ∨yˉ∨zˉC_3=\bar x\vee\bar y\vee\bar z:

xxyyzzC1C_1C2C_2C3C_3数值
xx100010100,010
xˉ\bar x100101100,101
yy01010010,100
yˉ\bar y01001110,011
zz0011101,110
zˉ\bar z0010011,001
填充000100100
填充000200200
填充00001010
填充00002020
填充0000011
填充0000022
WW111444111,444

不进位:每个变量位上至多两个 1;每个子句位上至多 3 个文字的 1 加上填充数 1+21+2,和至多 6<106<10。故任何子集之和中各位独立相加,「和等于 WW」等价于「每一位都相等」。

(⇒\Rightarrow)设赋值满足 Φ\Phi。为真的文字选取对应的数(每个 ii 恰选 ti,fit_i,f_i 之一),变量位都为 1。子句 CjC_j 中真文字有 s∈{1,2,3}s\in\{1,2,3\} 个,子句位 jj 已得 ss,再从两个填充数中选出和为 4−s∈{3,2,1}4-s\in\{3,2,1\} 的那些即可。

(⇐\Leftarrow)设某子集之和为 WW。变量位为 1 迫使每个 ii 恰选 ti,fit_i,f_i 之一,据此定义赋值。子句位 jj 为 4,而填充数至多贡献 33,故至少有一个所选文字数在该位上为 1,即 CjC_j 含一个真文字。□\square

例:表中实例的一个解

赋值 x=0, y=0, z=1x=0,\ y=0,\ z=1 满足三个子句(C1,C3C_1,C_3 由 xˉ\bar x,C2C_2 由 yˉ\bar y)。选取真文字 xˉ,yˉ,z\bar x,\bar y,z 对应的数:

100,101+10,011+1,110=111,222,100{,}101+10{,}011+1{,}110=111{,}222,

三个子句位各得 22(每个子句恰有两个真文字),再各取填充数 22:111,222+200+20+2=111,444=W111{,}222+200+20+2=111{,}444=W。反过来,若某个子句一个真文字也没有,该位只能靠填充数凑到 1+2=3<41+2=3<4,这就是「填充数至多补到 3」的作用。

伪多项式算法与弱 NP 完全

子集和有 O(nW)O(nW) 的动态规划:OPT(i,w)\mathrm{OPT}(i,w) 表示前 ii 个数能否凑出 ww。这与 NP 完全性并不矛盾:WW 的输入长度只有 log⁡W\log W,O(nW)O(nW) 是输入长度的指数,称为伪多项式时间。上述归约中的数有 n+kn+k 位十进制数字,是指数大的。若数以一元编码,子集和便属于 P;像子集和这样只在数值很大时才困难的问题称为弱 NP 完全,而在数值为输入长度多项式时仍 NP 完全的问题(如 3-PARTITION)称为强 NP 完全。

4.2 划分

划分(PARTITION):给定自然数 v1,…,vmv_1,\dots,v_m,能否把它们分成两组,使两组之和都等于 12∑ivi\frac12\sum_i v_i?
SUBSET-SUM≤pPARTITION\mathrm{SUBSET\text{-}SUM}\le_p\mathrm{PARTITION}。

设 W,w1,…,wnW,w_1,\dots,w_n 为子集和实例,记 Σ=∑iwi\Sigma=\sum_i w_i(不妨设 W≤ΣW\le\Sigma)。构造 m=n+2m=n+2 个数:

vi=wi (i≤n),vn+1=2Σ−W,vn+2=Σ+W.v_i=w_i\ (i\le n),\qquad v_{n+1}=2\Sigma-W,\qquad v_{n+2}=\Sigma+W.

总和为 4Σ4\Sigma,每组应为 2Σ2\Sigma。而 vn+1+vn+2=3Σ>2Σv_{n+1}+v_{n+2}=3\Sigma>2\Sigma,二者必在不同组中。含 vn+1v_{n+1} 的一组中其余元素之和为 2Σ−(2Σ−W)=W2\Sigma-(2\Sigma-W)=W,它们都是原来的 wiw_i;反之,若 {wi}i∈A\{w_i\}_{i\in A} 之和为 WW,则 A∪{n+1}A\cup\{n+1\} 与其余元素构成一个划分。□\square

4.3 带释放时间的调度

调度(SCHEDULE):给定 nn 个任务,任务 jj 有处理时间 tjt_j、释放时间 rjr_j 与截止时间 djd_j。能否在一台机器上安排所有任务,使任务 jj 在区间 [rj,dj][r_j,d_j] 内占用一段连续的 tjt_j 时间?
SUBSET-SUM≤pSCHEDULE\mathrm{SUBSET\text{-}SUM}\le_p\mathrm{SCHEDULE}。

设 W,w1,…,wnW,w_1,\dots,w_n 为子集和实例,Σ=∑iwi\Sigma=\sum_i w_i。构造 n+1n+1 个任务:

  • 任务 j∈[n]j\in[n]:tj=wjt_j=w_j,rj=0r_j=0,dj=Σ+1d_j=\Sigma+1;
  • 任务 00:t0=1t_0=1,r0=Wr_0=W,d0=W+1d_0=W+1。

任务 0 只能占据 [W,W+1][W,W+1]。总处理时间为 Σ+1\Sigma+1,恰等于时间窗口 [0,Σ+1][0,\Sigma+1] 的长度,故机器不能有任何空闲:[0,W][0,W] 必须被若干任务恰好填满,它们的 wjw_j 之和为 WW。反之,若 {wj}j∈A\{w_j\}_{j\in A} 之和为 WW,把 AA 中的任务依次排在 [0,W][0,W],任务 0 排在 [W,W+1][W,W+1],其余任务排在 [W+1,Σ+1][W+1,\Sigma+1] 即可。□\square

Fig 3 子集和到调度的归约:任务 0 卡住 $[W,W+1]$,机器不能空闲
Fig 3 子集和到调度的归约:任务 0 卡住 [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≠NP\mathrm P\ne\mathrm{NP},NP 完全问题的两个版本都不能在多项式时间内求解。反过来,二者其实是等价的:

设 P=NP\mathrm P=\mathrm{NP}。则对任意 NP 语言 LL 及其验证器 MM,存在多项式时间图灵机 BB,在输入 x∈Lx\in L 上输出 xx 的一个证书。

即证:若 P=NP\mathrm P=\mathrm{NP},则对任意多项式时间的 MM 与多项式 pp,存在多项式时间的 BB,使对任意 x∈{0,1}nx\in\{0,1\}^n,若存在 u∈{0,1}p(n)u\in\{0,1\}^{p(n)} 使 M(x,u)=1M(x,u)=1,则 ∣B(x)∣=p(n)|B(x)|=p(n) 且 M(x,B(x))=1M(x,B(x))=1。

SAT 的情形:设 AA 是判定 SAT 的多项式时间算法。在可满足的 nn 变量公式 φ\varphi 上,先代入 x1=0x_1=0,用 AA 判定所得公式是否可满足;若是,固定 x1=0x_1=0,否则固定 x1=1x_1=1(此时它必可满足)。对 x2,…,xnx_2,\dots,x_n 依次重复,最后得到满足赋值。共调用 AA 至多 2n+12n+1 次(事实上 n+1n+1 次即可),外加多项式时间的代入运算。

一般情形:Cook–Levin 定理中从 LL 到 SAT 的归约是 Levin 归约:存在多项式时间可计算的 ff,不仅 x∈L  ⟺  f(x)∈SATx\in L\iff f(x)\in\mathrm{SAT},而且 f(x)f(x) 的满足赋值可以高效地映射回 xx 的证书。于是先用上面的算法求出 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+1m+1 次。同理,优化问题也可以用二分归约到判定问题,例如先二分求出最大独立集的大小 k∗k^*,再逐个尝试删去顶点、保持最大独立集大小不变,即可找出一个最大独立集。

7. coNP

对语言 LL,记其补为 L‾={0,1}∗∖L\overline L=\{0,1\}^*\setminus L。定义

coNP={L:L‾∈NP}.\mathrm{coNP}=\{L:\overline L\in\mathrm{NP}\}.

等价地,L∈coNPL\in\mathrm{coNP} 当且仅当存在多项式 pp 与多项式时间图灵机 MM,使对任意 xx,

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.

NP 是「存在简短的肯定证明」,coNP 是「存在简短的否定证明」(反例)。注意 coNP 不是 NP 的补集:二者有非空的交,P⊆NP∩coNP\mathrm P\subseteq\mathrm{NP}\cap\mathrm{coNP}(P 对取补封闭)。例如 SAT‾={φ:φ is unsatisfiable}\overline{\mathrm{SAT}}=\{\varphi:\varphi\ \text{is unsatisfiable}\} 属于 coNP;合数属于 NP,故素数属于 coNP(又由 Pratt 证书属于 NP)。

类似地定义 coNP 完全:属于 coNP,且 coNP 中的每个语言都可 Karp 归约到它。

TAUTOLOGY={φ:φ is a Boolean formula satisfied by every assignment}\mathrm{TAUTOLOGY}=\{\varphi:\varphi\ \text{is a Boolean formula satisfied by every assignment}\} 是 coNP 完全的。

TAUTOLOGY 显然属于 coNP:对每个赋值 uu,检查 φ(u)=1\varphi(u)=1。

对任意 L∈coNPL\in\mathrm{coNP},有 L‾∈NP\overline L\in\mathrm{NP}。对 L‾\overline L 应用 Cook–Levin 归约,对每个输入 xx 得到公式 φx\varphi_x,使 φx\varphi_x 可满足   ⟺  x∈L‾\iff x\in\overline L。于是

¬φx∈TAUTOLOGY  ⟺  φx is unsatisfiable  ⟺  x∈L,\neg\varphi_x\in\mathrm{TAUTOLOGY}\iff\varphi_x\ \text{is unsatisfiable}\iff x\in L,

x↦¬φxx\mapsto\neg\varphi_x 即为 L≤pTAUTOLOGYL\le_p\mathrm{TAUTOLOGY}。□\square

这里 ¬φx\neg\varphi_x 不再是 CNF(而是 DNF),所以 TAUTOLOGY 要对一般布尔公式定义。

若 P=NP\mathrm P=\mathrm{NP},则 P=NP=coNP\mathrm P=\mathrm{NP}=\mathrm{coNP}。
L∈coNP  ⟺  L‾∈NP=P  ⟺  L∈PL\in\mathrm{coNP}\iff\overline L\in\mathrm{NP}=\mathrm P\iff L\in\mathrm P。□\square

逆否地,证明 NP≠coNP\mathrm{NP}\ne\mathrm{coNP} 就证明了 P≠NP\mathrm P\ne\mathrm{NP}。普遍的猜想是

猜想 1:NP≠coNP\mathrm{NP}\ne\mathrm{coNP},等价于说不可满足的 CNF 公式没有简短的证明;

猜想 2:P≠NP∩coNP\mathrm P\ne\mathrm{NP}\cap\mathrm{coNP},与整数分解等价的问题是这一猜想的主要候选。

若 NP≠coNP\mathrm{NP}\ne\mathrm{coNP},则 NP∩coNP\mathrm{NP}\cap\mathrm{coNP} 中的语言都不是 NP 完全的。
设 L∈NP∩coNPL\in\mathrm{NP}\cap\mathrm{coNP} 是 NP 完全的。对任意 L′∈NPL'\in\mathrm{NP},有 L′≤pLL'\le_p L,同一个归约 ff 也满足 x∈L′‾  ⟺  f(x)∈L‾x\in\overline{L'}\iff f(x)\in\overline L,即 L′‾≤pL‾\overline{L'}\le_p\overline L。而 L‾∈NP\overline L\in\mathrm{NP},NP 对 Karp 归约封闭(把归约与验证器复合),故 L′‾∈NP\overline{L'}\in\mathrm{NP},即 L′∈coNPL'\in\mathrm{coNP}。于是 NP⊆coNP\mathrm{NP}\subseteq\mathrm{coNP};取补得 coNP⊆NP\mathrm{coNP}\subseteq\mathrm{NP},从而 NP=coNP\mathrm{NP}=\mathrm{coNP},矛盾。□\square

所以整数分解(判定版本属于 NP∩coNP\mathrm{NP}\cap\mathrm{coNP})很可能不是 NP 完全的。NP 中是否一定存在既不在 P 中、又非 NP 完全的问题?

若 P≠NP\mathrm P\ne\mathrm{NP},则存在语言 L∈NP∖PL\in\mathrm{NP}\setminus\mathrm P,且 LL 不是 NP 完全的。

Ladner 构造的语言是人为的;自然的候选是整数分解与图同构。在 P≠NP∩coNP≠NP\mathrm P\ne\mathrm{NP}\cap\mathrm{coNP}\ne\mathrm{NP} 的假设下,世界图景是:P 位于 NP∩coNP\mathrm{NP}\cap\mathrm{coNP} 内部;NPC 位于 NP 的「边缘」,coNPC 位于 coNP 的「边缘」,二者都与 NP∩coNP\mathrm{NP}\cap\mathrm{coNP} 不交。

Fig 4 P、NP 与 coNP 的猜想图景
Fig 4 P、NP 与 coNP 的猜想图景

8. EXP 与 NEXP

EXP=⋃c≥0DTIME(2nc),NEXP=⋃c≥0NTIME(2nc).\mathrm{EXP}=\bigcup_{c\ge0}\mathrm{DTIME}(2^{n^c}),\qquad\mathrm{NEXP}=\bigcup_{c\ge0}\mathrm{NTIME}(2^{n^c}).
  1. P⊆NP⊆EXP⊆NEXP\mathrm P\subseteq\mathrm{NP}\subseteq\mathrm{EXP}\subseteq\mathrm{NEXP};
  2. 若 EXP≠NEXP\mathrm{EXP}\ne\mathrm{NEXP},则 P≠NP\mathrm P\ne\mathrm{NP}。

(1)前两个包含关系已证,最后一个因确定性机器是非确定性机器的特例。

(2)只证逆否命题:设 P=NP\mathrm P=\mathrm{NP},证明 EXP=NEXP\mathrm{EXP}=\mathrm{NEXP}。设 L∈NTIME(2nc)L\in\mathrm{NTIME}(2^{n^c}) 由 NDTM MM 判定。

断言:Lpad={⟨x,12∣x∣c⟩:x∈L}∈NPL_{\mathrm{pad}}=\{\langle x,1^{2^{|x|^c}}\rangle:x\in L\}\in\mathrm{NP}。构造 NDTM:给定 yy,先检查是否存在 zz 使 y=⟨z,12∣z∣c⟩y=\langle z,1^{2^{|z|^c}}\rangle,若不是则输出 0;否则运行 M(z)M(z) 并输出其结果。M(z)M(z) 运行 O(2∣z∣c)O(2^{|z|^c}) 步,这是 ∣y∣|y| 的线性函数,故整个机器关于 ∣y∣|y| 是多项式时间的。

于是 Lpad∈NP=PL_{\mathrm{pad}}\in\mathrm{NP}=\mathrm P。要判定 x∈Lx\in L,先写出填充后的串 y=⟨x,12∣x∣c⟩y=\langle x,1^{2^{|x|^c}}\rangle(用时 O(2∣x∣c)O(2^{|x|^c})),再用 LpadL_{\mathrm{pad}} 的多项式时间算法判定 yy,用时 poly(∣y∣)=2O(∣x∣c)\mathrm{poly}(|y|)=2^{O(|x|^c)}。故 L∈EXPL\in\mathrm{EXP}。□\square

这一技术称为填充(padding):人为地把输入变长,使相对于输入长度的运行时间「变小」。它说明类之间的相等会向上传递(P=NP⇒EXP=NEXP\mathrm P=\mathrm{NP}\Rightarrow\mathrm{EXP}=\mathrm{NEXP}),从而分离会向下传递。

9. P vs NP 的现状

NP 的哲学意义在于:识别答案的正确性往往比想出答案容易。它与数学证明紧密相关:能否在证明长度的多项式时间内找到证明?P=NP\mathrm P=\mathrm{NP} 与 P≠NP\mathrm P\ne\mathrm{NP} 各自会带来什么?围绕 NP 还发展出了 PCP 定理、唯一游戏猜想(UGC)、PPAD、近似算法等方向。

P vs NP 是 Clay 数学研究所的七个千禧年大奖难题之一(其中 Poincaré 猜想已被解决)。证明 P=NP\mathrm P=\mathrm{NP} 的人(如果能给出实用的算法)大概能顺手解决其余五个,带回六张百万美元支票。复杂性理论学者普遍相信 P≠NP\mathrm P\ne\mathrm{NP},但所有尝试都失败了。主要思路有:

对角线法:能否像构造 UC 那样,直接构造一个 NP 语言,使每个多项式时间算法都在某个输入上出错?

电路复杂性:只需证明某个 NP 完全问题不能被较小的与、或、非门电路计算;

证明复杂性:若能证明 TAUTOLOGY 没有简短的证明,即得 NP≠coNP\mathrm{NP}\ne\mathrm{coNP},从而 P≠NP\mathrm P\ne\mathrm{NP}。

新的希望包括 Mulmuley 与 Sohoni 的几何复杂性理论,它涉及代数几何、表示论、量子群,并需要一个类似 Riemann 假设的命题;Mulmuley 估计这一纲领需要约 100 年才能完成(如果它可行的话)。2010 年 Deolalikar 用统计物理与有限模型论宣称证明了 P≠NP\mathrm P\ne\mathrm{NP},但证明既不正确,也没有实质性地推进对问题的理解。P vs NP 至今仍是公开问题。

三重障碍

已知的几类技术被证明不足以解决 P vs NP:相对化(Baker–Gill–Solovay 1975):存在预言机 A,BA,B 使 PA=NPA\mathrm P^A=\mathrm{NP}^A 而 PB≠NPB\mathrm P^B\ne\mathrm{NP}^B,而纯粹的对角线法与模拟在加入预言机后仍然成立,故不能单独解决问题;自然证明(Razborov–Rudich 1994):在单向函数存在的假设下,一大类电路下界论证无法证明 P≠NP\mathrm P\ne\mathrm{NP};代数化(Aaronson–Wigderson 2008)则堵住了对相对化的代数推广。

10. 小结

归约变量部件子句部件 / 约束
SAT≤pdHAMPATH\mathrm{SAT}\le_p\mathrm{dHAMPATH}双向链,走向即赋值子句顶点只能从方向正确的链绕道访问
SAT≤pSETCOVER\mathrm{SAT}\le_p\mathrm{SETCOVER}Si,t,Si,fS_{i,t},S_{i,f}新元素 m+im+i 迫使恰选其一
INDSET≤pVC,CLIQUE\mathrm{INDSET}\le_p\mathrm{VC},\mathrm{CLIQUE}—取补集、取补图
3SAT≤pSUBSET-SUM\mathrm{3SAT}\le_p\mathrm{SUBSET\text{-}SUM}变量位为 1子句位为 4,填充数补足;各位不进位
SUBSET-SUM≤pPARTITION\mathrm{SUBSET\text{-}SUM}\le_p\mathrm{PARTITION}—两个大数 2Σ−W2\Sigma-W、Σ+W\Sigma+W 必然分开
SUBSET-SUM≤pSCHEDULE\mathrm{SUBSET\text{-}SUM}\le_p\mathrm{SCHEDULE}—任务 0 卡住 [W,W+1][W,W+1],无空闲迫使 [0,W][0,W] 恰好填满
类定义完全问题
NP∃u\exists u,多项式时间验证SAT、3SAT、INDSET、……
coNP∀u\forall u,多项式时间验证TAUTOLOGY、SAT‾\overline{\mathrm{SAT}}
EXP / NEXP指数时间(非)确定性—

NP 完全问题构成一个巨大的等价类,归约在其中自由穿行;搜索与判定也被证明等价。理论告诉我们,若 P≠NP\mathrm P\ne\mathrm{NP},就不能指望对这些问题同时做到「任意实例、精确最优、多项式时间」。但实践中的实例往往有特殊结构,下一章正是利用这些结构,见拓展可解性的边界。