P 刻画「能高效求解」的问题,NP 刻画「答案能高效验证」的问题。P 与 NP 是否相等,问的就是:验证与求解是否一样难。
1. 引入:验证比求解容易?# 独立集 :给定图 G G G 与整数 k k k ,判定 G G G 中是否存在 k k k 个两两不相邻的顶点。暴力算法枚举全部 ( n k ) \binom nk ( k n ) 个 k k k 元子集,当 k ≈ n / 2 k\approx n/2 k ≈ n /2 时是指数级的,至今不知道有多项式算法。但如果有人给出 一个 k k k 元子集 S S S ,检查它是否是独立集只需 O ( k 2 ) O(k^2) O ( k 2 ) 次查邻接矩阵。求解似乎需要在指数大的空间中搜索,而验证只需检查一个候选。
NP 正是把「存在一个能被快速检查的解」形式化。
2. NP:多项式时间可验证# 语言 L ⊆ { 0 , 1 } ∗ L\subseteq\{0,1\}^* L ⊆ { 0 , 1 } ∗ 属于 NP,若存在多项式 p : N → N p:\mathbb N\to\mathbb N p : N → N 与多项式时间图灵机 M M M (称为 L L L 的验证器 ),使对任意 x ∈ { 0 , 1 } ∗ x\in\{0,1\}^* x ∈ { 0 , 1 } ∗ ,
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 ∈ L x\in L x ∈ L 且 u u u 满足 M ( x , u ) = 1 M(x,u)=1 M ( x , u ) = 1 ,称 u u u 为 x x x 的证书 (证据 )。
定义有两点值得注意:
证书长度有界 :∣ u ∣ |u| ∣ u ∣ 是 ∣ x ∣ |x| ∣ x ∣ 的多项式,且 M M M 关于 ∣ x ∣ |x| ∣ x ∣ 多项式时间运行(等价地,关于 ∣ x ∣ + ∣ u ∣ |x|+|u| ∣ x ∣ + ∣ u ∣ 多项式时间);
只有「是」实例需要证书 :x ∈ L x\in L x ∈ L 时存在证书,x ∉ L x\notin L x ∈ / L 时任何 u u u 都被拒绝。「否」实例未必有简短的证明,这种不对称引出 coNP。
NP 不是「非多项式」
一个常见的误解是把 NP 读作 non-polynomial。恰恰相反,NP 中每个问题都「有一半是多项式的」:只要有人递上证书,就能多项式时间检查。P 中的问题全都属于 NP(第 3 节),而真正「非多项式」的问题多半不在 NP 中:例如判定「白方在一般化的 n × n n\times n n × n 国际象棋中是否必胜」是 EXP 完全的,必胜策略是一棵指数大的博弈树,没有人知道怎样用多项式长的串证明它。N 指的是后面第 5 节的非确定性。
I N D S E T = { ⟨ G , k ⟩ : ∃ S ⊆ V ( G ) , ∣ S ∣ = k , ∀ u , v ∈ S , ( u , v ) ∉ E ( G ) } ∈ N P \mathrm{INDSET}=\{\langle G,k\rangle:\exists S\subseteq V(G),\ |S|=k,\ \forall u,v\in S,\ (u,v)\notin E(G)\}\in\mathrm{NP} INDSET = {⟨ G , k ⟩ : ∃ S ⊆ V ( G ) , ∣ S ∣ = k , ∀ u , v ∈ S , ( u , v ) ∈ / E ( G )} ∈ NP 。
验证器 M M M :给定 ⟨ G , k ⟩ \langle G,k\rangle ⟨ G , k ⟩ 与串 u u u ,当且仅当 u u u 编码了 G G G 的 k k k 个顶点、且其中任意两个之间没有边时输出 1,这可在多项式时间内完成,且 ⟨ G , k ⟩ ∈ I N D S E T ⟺ ∃ u , M ( ⟨ G , k ⟩ , u ) = 1 \langle G,k\rangle\in\mathrm{INDSET}\iff\exists u,\ M(\langle G,k\rangle,u)=1 ⟨ G , k ⟩ ∈ INDSET ⟺ ∃ u , M (⟨ G , k ⟩ , u ) = 1 。证书即构成独立集的 k k k 个顶点的列表;若 G G G 有 n n n 个顶点,它可以用 k log n k\log n k log n 个比特编码,是 G G G 的表示长度的多项式。□ \square □ 以下问题都在 NP 中,证书都是「解本身」:
问题 判定 证书 已知状态 旅行商(TSP) 是否有总长 ≤ k \le k ≤ k 的哈密顿回路 回路的顶点序列 NP 完全 子集和 是否有子集之和恰为 T T T 该子集 NP 完全 线性规划 线性不等式组是否有有理解 一组解 P(椭球法、内点法) 整数规划 线性不等式组是否有整数解 一组解 NP 完全 图同构 两个邻接矩阵是否表示同一个图 顶点置换 π \pi π 未知(拟多项式) 合数 N N N 是否为合数N N N 的因子分解P(AKS) 因子 N N N 是否有素因子 p ∈ [ L , U ] p\in[L,U] p ∈ [ L , U ] 因子 p p p 未知,属于 N P ∩ c o N P \mathrm{NP}\cap\mathrm{coNP} NP ∩ coNP 连通性 s s s 与 t t t 是否连通s s s 到 t t t 的路径P(BFS)
其中连通性用一次 BFS 即可判定;线性规划属于 P 则非常不平凡:Khachiyan(1979)的椭球法给出第一个多项式算法,Karmarkar(1984)的内点法给出第一个既多项式又实用的算法;合数判定直到 2002 年才由 Agrawal–Kayal–Saxena 证明属于 P。其余问题至今不知道多项式算法,但也没有人证明它们不在 P 中。
线性规划的证书长度
线性规划的证书是一组有理解,还需说明存在长度多项式 的解:若可行域非空,则它有一个顶点,顶点是某个子方程组的唯一解,由 Cramer 法则,其分子、分母都是系数矩阵子式,位数是输入长度的多项式。整数规划同理需要论证存在小的整数解,这一点并不平凡。
3. P、NP 与 EXP# P ⊆ N P ⊆ E X P = ⋃ c > 1 D T I M E ( 2 n c ) . \mathrm P\subseteq\mathrm{NP}\subseteq\mathrm{EXP}=\bigcup_{c>1}\mathrm{DTIME}(2^{n^c}). P ⊆ NP ⊆ EXP = c > 1 ⋃ DTIME ( 2 n c ) .
(P ⊆ N P \mathrm P\subseteq\mathrm{NP} P ⊆ NP )设 L ∈ P L\in\mathrm P L ∈ P 由多项式时间图灵机 N N N 判定。取定义中的 M M M 为忽略证书、直接运行 N N N 的机器,p p p 为零多项式(u u u 为空串),即得 L ∈ N P L\in\mathrm{NP} L ∈ NP 。
(N P ⊆ E X P \mathrm{NP}\subseteq\mathrm{EXP} NP ⊆ EXP )设 L ∈ N P L\in\mathrm{NP} L ∈ NP ,M , p M,p M , p 如定义。枚举全部 2 p ( n ) 2^{p(n)} 2 p ( n ) 个可能的 u u u ,用 M M M 逐个检查,找到有效证书即接受。这需要 2 p ( n ) ⋅ p o l y ( n ) = 2 O ( p ( n ) ) 2^{p(n)}\cdot\mathrm{poly}(n)=2^{O(p(n))} 2 p ( n ) ⋅ poly ( n ) = 2 O ( p ( n )) 时间;由于存在 c > 1 c>1 c > 1 使 p ( n ) = O ( n c ) p(n)=O(n^c) p ( n ) = O ( n c ) ,该机器在 2 O ( n c ) 2^{O(n^c)} 2 O ( n c ) 时间内运行。□ \square □
算法实现 \begin{algorithm}
\caption{Brute-Force-Verify:用验证器判定 NP 语言}
\begin{algorithmic}
\PROCEDURE{Decide}{$x$}
\FORALL{$u \in \{0,1\}^{p(|x|)}$}
\COMMENT{共 $2^{p(|x|)}$ 个候选证书}
\IF{$M(x, u) = 1$}
\RETURN $1$
\ENDIF
\ENDFOR
\RETURN $0$
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm} 这正是「穷举搜索」的形式化。P \mathrm P P 与 N P \mathrm{NP} NP 是否相等,问的是:穷举搜索一般能否避免?
4. P 与 NP# 这是复杂性理论的核心公开问题,也是整个数学与科学中的重要问题。人们在直觉上普遍相信 P ≠ N P \mathrm P\ne\mathrm{NP} P = NP :
验证比发现容易 :判断一个答案(证明)是否正确,通常比想出它容易得多;
搜索似乎不可避免 :许多问题中,找到正确答案似乎必须在指数大的集合中穷举。
这个问题也是 Gödel(1956 年致 von Neumann 的信)问题的改写:是否存在多项式时间算法来寻找数学证明?「给定定理与长度上界 1 n 1^n 1 n ,判定是否存在长度 ≤ n \le n ≤ n 的证明」属于 NP(证明本身就是证书),所以若 P = N P \mathrm P=\mathrm{NP} P = NP ,数学家的创造性工作在很大程度上可以自动化。
5. 非确定性图灵机# NP 最初是用非确定性图灵机 (NDTM)定义的,NP 即 Nondeterministic Polynomial-time。
非确定性图灵机 与标准图灵机的唯一区别是它有两个转移函数 δ 0 , δ 1 \delta_0,\delta_1 δ 0 , δ 1 ,以及一个特殊的接受状态 q a c c e p t q_{\mathrm{accept}} q accept 。计算的每一步,M M M 任意选择应用 δ 0 \delta_0 δ 0 或 δ 1 \delta_1 δ 1 。
若存在某个选择序列使 M M M 在输入 x x x 上到达 q a c c e p t q_{\mathrm{accept}} q accept ,则 M ( x ) = 1 M(x)=1 M ( x ) = 1 ;若每个选择序列都使 M M M 停机而未到达 q a c c e p t q_{\mathrm{accept}} q accept ,则 M ( x ) = 0 M(x)=0 M ( x ) = 0 。 称 M M M 在 T ( n ) T(n) T ( n ) 时间内运行,若对每个输入 x x x 与每个选择序列,M M M 都在 T ( ∣ x ∣ ) T(|x|) T ( ∣ x ∣ ) 步内停机或到达 q a c c e p t q_{\mathrm{accept}} q accept 。 NDTM 不是物理上可实现的模型:它「恰好」总能猜中正确的分支。
对 T : N → N T:\mathbb N\to\mathbb N T : N → N 与 L ⊆ { 0 , 1 } ∗ L\subseteq\{0,1\}^* L ⊆ { 0 , 1 } ∗ ,称 L ∈ N T I M E ( T ( n ) ) L\in\mathrm{NTIME}(T(n)) L ∈ NTIME ( T ( n )) ,若存在常数 c > 0 c>0 c > 0 与 c T ( n ) cT(n) c T ( n ) 时间的 NDTM M M M ,使对任意 x x x ,x ∈ L ⟺ M ( x ) = 1 x\in L\iff M(x)=1 x ∈ L ⟺ M ( x ) = 1 。 N P = ⋃ c ∈ N N T I M E ( n c ) . \mathrm{NP}=\bigcup_{c\in\mathbb N}\mathrm{NTIME}(n^c). NP = c ∈ N ⋃ NTIME ( n c ) .
(⊇ \supseteq ⊇ )设 L L L 由 p ( n ) p(n) p ( n ) 时间的 NDTM N N N 判定。x ∈ L x\in L x ∈ L 当且仅当存在一个使 N N N 在 x x x 上到达 q a c c e p t q_{\mathrm{accept}} q accept 的选择序列,就用这个序列作为证书:它的长度为 p ( ∣ x ∣ ) p(|x|) p ( ∣ x ∣ ) ,确定性机器按序列逐步模拟 N N N 、检查是否进入 q a c c e p t q_{\mathrm{accept}} q accept ,可在多项式时间内验证。故 L ∈ N P L\in\mathrm{NP} L ∈ NP 。
(⊆ \subseteq ⊆ )设 L ∈ N P L\in\mathrm{NP} L ∈ NP ,验证器为 M M M ,证书长度为 p p p 。构造 NDTM N N N :在输入 x x x 上,先利用非确定性选择写下一个长为 p ( ∣ x ∣ ) p(|x|) p ( ∣ x ∣ ) 的串 u u u (令 δ 0 \delta_0 δ 0 对应写 0,δ 1 \delta_1 δ 1 对应写 1),再运行确定性验证器 M ( x , u ) M(x,u) M ( x , u ) ,若接受则进入 q a c c e p t q_{\mathrm{accept}} q accept 。N N N 进入 q a c c e p t q_{\mathrm{accept}} q accept 当且仅当 x x x 存在有效证书;它运行多项式时间,故 L ∈ N T I M E ( n c ) L\in\mathrm{NTIME}(n^c) L ∈ NTIME ( n c ) 。□ \square □
Fig 1 猜测,然后验证:NDTM 先非确定性地写下证书,再确定性地运行验证器 两种定义是「猜测,然后验证 」的两种说法:证书就是非确定性选择序列,非确定性选择就是在猜证书。
6. 归约、NP 难与 NP 完全# 独立集至少和 NP 中任何其他问题一样难:若它有多项式算法,则 NP 中所有问题都有。这一性质称为 NP 难。若 P ≠ N P \mathrm P\ne\mathrm{NP} P = NP ,一个语言是 NP 难的,便可以看作它不能在多项式时间内判定的证据。比较两个问题的难度,关键工具是归约 。
称语言 L L L 多项式时间 Karp 归约 到 L ′ L' L ′ ,记作 L ≤ p L ′ L\le_p L' L ≤ p L ′ ,若存在多项式时间可计算的函数 f : { 0 , 1 } ∗ → { 0 , 1 } ∗ f:\{0,1\}^*\to\{0,1\}^* f : { 0 , 1 } ∗ → { 0 , 1 } ∗ ,使对任意 x x x ,
x ∈ L ⟺ f ( x ) ∈ L ′ . x\in L\iff f(x)\in L'. x ∈ L ⟺ f ( x ) ∈ L ′ . 称 L ′ L' L ′ 是 NP 难 的,若对任意 L ∈ N P L\in\mathrm{NP} L ∈ NP 都有 L ≤ p L ′ L\le_p L' L ≤ p L ′ ;称 L ′ L' L ′ 是 NP 完全 的,若它是 NP 难的且 L ′ ∈ N P L'\in\mathrm{NP} L ′ ∈ NP 。
f f f 把 L L L 中的串映到 L ′ L' L ′ 中,把 L ‾ \overline L L 中的串映到 L ′ ‾ \overline{L'} L ′ 中,于是判定 L ′ L' L ′ 的多项式时间机器 M ′ M' M ′ 可以变成判定 L L L 的机器 M ( x ) = M ′ ( f ( x ) ) M(x)=M'(f(x)) M ( x ) = M ′ ( f ( x )) 。
Fig 2 Karp 归约 L ≤ p L ′ L\le_p L' L ≤ p L ′ :保持「是 / 否」的映射,与算法的复合 方向 :要证明 B B B 难,应把已知的难问题 A A A 归约到 B B B ,即 A ≤ p B A\le_p B A ≤ p B :「若能解 B B B ,就能解 A A A 」。反方向的 B ≤ p A B\le_p A B ≤ p A 只说明 B B B 不比 A A A 难,对证明 B B B 的难度毫无帮助;
两个方向都要证 :x ∈ L ⇒ f ( x ) ∈ L ′ x\in L\Rightarrow f(x)\in L' x ∈ L ⇒ f ( x ) ∈ L ′ 与 f ( x ) ∈ L ′ ⇒ x ∈ L f(x)\in L'\Rightarrow x\in L f ( x ) ∈ L ′ ⇒ x ∈ L 缺一不可,后者通常需要从 L ′ L' L ′ 的解「读回」L L L 的解。
若 L ≤ p L ′ L\le_p L' L ≤ p L ′ 且 L ′ ∈ P L'\in\mathrm P L ′ ∈ P ,则 L ∈ P L\in\mathrm P L ∈ P ; (传递性)若 L ≤ p L ′ L\le_p L' L ≤ p L ′ 且 L ′ ≤ p L ′ ′ L'\le_p L'' L ′ ≤ p L ′′ ,则 L ≤ p L ′ ′ L\le_p L'' L ≤ p L ′′ ; 若 L L L 是 NP 难的且 L ∈ P L\in\mathrm P L ∈ P ,则 P = N P \mathrm P=\mathrm{NP} P = NP ; 若 L L L 是 NP 完全的,则 L ∈ P ⟺ P = N P L\in\mathrm P\iff\mathrm P=\mathrm{NP} L ∈ P ⟺ P = NP 。 关键事实:多项式时间机器的输出长度不超过其运行时间,故 ∣ f ( x ) ∣ ≤ q ( ∣ x ∣ ) |f(x)|\le q(|x|) ∣ f ( x ) ∣ ≤ q ( ∣ x ∣ ) ,q q q 为某多项式;而多项式的复合仍是多项式。
(1)设 f f f 在 q ( n ) q(n) q ( n ) 时间内运行,L ′ L' L ′ 在 r ( n ) r(n) r ( n ) 时间内判定。计算 f ( x ) f(x) f ( x ) 再判定 f ( x ) ∈ L ′ f(x)\in L' f ( x ) ∈ L ′ ,共需 q ( n ) + r ( q ( n ) ) q(n)+r(q(n)) q ( n ) + r ( q ( n )) 时间,是多项式。
(2)设 f 1 f_1 f 1 是 L L L 到 L ′ L' L ′ 的归约,f 2 f_2 f 2 是 L ′ L' L ′ 到 L ′ ′ L'' L ′′ 的归约,则 x ↦ f 2 ( f 1 ( x ) ) x\mapsto f_2(f_1(x)) x ↦ f 2 ( f 1 ( x )) 可在多项式时间内计算,且 f 2 ( f 1 ( x ) ) ∈ L ′ ′ ⟺ f 1 ( x ) ∈ L ′ ⟺ x ∈ L f_2(f_1(x))\in L''\iff f_1(x)\in L'\iff x\in L f 2 ( f 1 ( x )) ∈ L ′′ ⟺ f 1 ( x ) ∈ L ′ ⟺ x ∈ L 。
(3)对任意 L ′ ∈ N P L'\in\mathrm{NP} L ′ ∈ NP ,由 NP 难性有 L ′ ≤ p L L'\le_p L L ′ ≤ p L ,由(1)得 L ′ ∈ P L'\in\mathrm P L ′ ∈ P ,故 N P ⊆ P \mathrm{NP}\subseteq\mathrm P NP ⊆ P ,结合 P ⊆ N P \mathrm P\subseteq\mathrm{NP} P ⊆ NP 即得。
(4)⇒ \Rightarrow ⇒ 即(3);⇐ \Leftarrow ⇐ :L ∈ N P = P L\in\mathrm{NP}=\mathrm P L ∈ NP = P 。□ \square □
由传递性,一旦有了一个 NP 完全问题 L 0 L_0 L 0 ,证明新问题 L ∈ N P L\in\mathrm{NP} L ∈ NP 是 NP 完全的,只需给出 L 0 ≤ p L L_0\le_p L L 0 ≤ p L ,而不必再面对 NP 中的全部语言。另一方面,归约也可以反过来用来证明「属于 NP」:
若 L ≤ p L ′ L\le_p L' L ≤ p L ′ 且 L ′ ∈ N P L'\in\mathrm{NP} L ′ ∈ NP ,则 L ∈ N P L\in\mathrm{NP} L ∈ NP 。
设 f f f 是归约,∣ f ( x ) ∣ ≤ q ( ∣ x ∣ ) |f(x)|\le q(|x|) ∣ f ( x ) ∣ ≤ q ( ∣ x ∣ ) ;L ′ L' L ′ 的验证器为 M ′ M' M ′ ,证书长 p ′ p' p ′ 。令 L L L 的验证器在 ( x , u ) (x,u) ( x , u ) 上先算出 f ( x ) f(x) f ( x ) ,再输出 M ′ ( f ( x ) , u ) M'(f(x),u) M ′ ( f ( x ) , u ) 。证书长度 p ′ ( q ( ∣ x ∣ ) ) p'(q(|x|)) p ′ ( q ( ∣ x ∣ )) 与运行时间都是 ∣ x ∣ |x| ∣ x ∣ 的多项式,且 x ∈ L ⟺ f ( x ) ∈ L ′ ⟺ ∃ u , M ′ ( f ( x ) , u ) = 1 x\in L\iff f(x)\in L'\iff\exists u,\ M'(f(x),u)=1 x ∈ L ⟺ f ( x ) ∈ L ′ ⟺ ∃ u , M ′ ( f ( x ) , u ) = 1 。□ \square □ 这个引理后面讨论 coNP 时会用到。下面用一个具体的归约演示「两个方向都要证」。
哈密顿圈归约到旅行商 :哈密顿圈问题 HAMCYCLE 问无向图 G G G 是否有经过每个顶点恰好一次的圈。证明 H A M C Y C L E ≤ p T S P \mathrm{HAMCYCLE}\le_p\mathrm{TSP} HAMCYCLE ≤ p TSP 。
设 G = ( V , E ) G=(V,E) G = ( V , E ) ,∣ V ∣ = n |V|=n ∣ V ∣ = n 。在同一顶点集上建完全图,令 d ( u , v ) = 1 d(u,v)=1 d ( u , v ) = 1 (( u , v ) ∈ E (u,v)\in E ( u , v ) ∈ E )或 2 2 2 (否则),取阈值 k = n k=n k = n 。构造只需 O ( n 2 ) O(n^2) O ( n 2 ) 时间。
(⇒ \Rightarrow ⇒ )G G G 的哈密顿圈是一条由 n n n 条权为 1 1 1 的边组成的回路,总长 n ≤ k n\le k n ≤ k 。
(⇐ \Leftarrow ⇐ )任何回路都有 n n n 条边,每条权至少为 1 1 1 。若总长 ≤ n \le n ≤ n ,则每条边的权都是 1 1 1 ,即都是 G G G 的边,这条回路就是 G G G 的哈密顿圈。□ \square □
这个归约里的权都是 1 1 1 或 2 2 2 ,满足三角不等式,所以即使限制在度量空间中,TSP 仍然困难。把非边的权改成 ρ n + 1 \rho n+1 ρ n + 1 ,还能得到更强的结论:G G G 有哈密顿圈时最优回路长 n n n ,否则任何回路都 > ρ n >\rho n > ρ n ,所以对一般(不满足三角不等式的)TSP,若 P ≠ N P \mathrm P\neq\mathrm{NP} P = NP ,任何多项式算法都不可能保证得到 ρ \rho ρ 倍以内的近似解。归约不仅比较「能否精确求解」,稍加设计还能刻画「能否近似」。
剩下的问题是:第一个 NP 完全问题从哪里来?
Cook 归约
更宽松的 Cook 归约 (Turing 归约)允许在多项式时间内多次调用 L ′ L' L ′ 的判定「预言机」,并对答案做任意后处理,例如取反。在 Cook 归约下 S A T \mathrm{SAT} SAT 与其补 S A T ‾ \overline{\mathrm{SAT}} SAT 等价,NP 难与 coNP 难便无法区分;坚持使用 Karp 归约,才能区分 NP 完全与 coNP 完全。
7. NP 完全问题存在吗# T M S A T = { ⟨ ⌞ M ⌟ , x , 1 n , 1 t ⟩ : ∃ u ∈ { 0 , 1 } n such that M outputs 1 on ⟨ x , u ⟩ within t steps } \mathrm{TMSAT}=\{\langle\llcorner M\lrcorner,x,1^n,1^t\rangle:\exists u\in\{0,1\}^n\ \text{such that}\ M\ \text{outputs}\ 1\ \text{on}\ \langle x,u\rangle\ \text{within}\ t\ \text{steps}\} TMSAT = {⟨ └ M ┘ , x , 1 n , 1 t ⟩ : ∃ u ∈ { 0 , 1 } n such that M outputs 1 on ⟨ x , u ⟩ within t steps } 是 NP 完全的。
(T M S A T ∈ N P \mathrm{TMSAT}\in\mathrm{NP} TMSAT ∈ NP )证书为 u u u ,验证器用通用图灵机模拟 M M M 在 ⟨ x , u ⟩ \langle x,u\rangle ⟨ x , u ⟩ 上运行 t t t 步,时间为 p o l y ( ∣ ⌞ M ⌟ ∣ , t ) \mathrm{poly}(|\llcorner M\lrcorner|,t) poly ( ∣ └ M ┘ ∣ , t ) 。由于 n n n 与 t t t 以一元形式 1 n , 1 t 1^n,1^t 1 n , 1 t 给出,这是输入长度的多项式。
(NP 难)设 L ∈ N P L\in\mathrm{NP} L ∈ NP ,验证器 M M M 在 q ( m ) q(m) q ( m ) 时间内运行,证书长度为 p ( ∣ x ∣ ) p(|x|) p ( ∣ x ∣ ) 。令
f ( x ) = ⟨ ⌞ M ⌟ , x , 1 p ( ∣ x ∣ ) , 1 q ( ∣ x ∣ + p ( ∣ x ∣ ) ) ⟩ , f(x)=\left\langle\llcorner M\lrcorner,\ x,\ 1^{p(|x|)},\ 1^{q(|x|+p(|x|))}\right\rangle, f ( x ) = ⟨ └ M ┘ , x , 1 p ( ∣ x ∣ ) , 1 q ( ∣ x ∣ + p ( ∣ x ∣ )) ⟩ , 它可在多项式时间内计算,且由 NP 的定义,x ∈ L ⟺ f ( x ) ∈ T M S A T x\in L\iff f(x)\in\mathrm{TMSAT} x ∈ L ⟺ f ( x ) ∈ TMSAT 。□ \square □
证明几乎就是 NP 定义的改写,一元编码 1 n , 1 t 1^n,1^t 1 n , 1 t 是为了让「模拟 t t t 步」是输入长度的多项式。但 TMSAT 并不实用:它的定义与图灵机这一概念紧密纠缠,要把它归约到图、公式、数等组合问题并不方便。第一个「自然」的 NP 完全问题是 SAT,见Cook–Levin 定理 。
8. 习题# PRIMES ∈ \in ∈ NP :设 P R I M E S = { n : n is prime } \mathrm{PRIMES}=\{n:n\ \text{is prime}\} PRIMES = { n : n is prime } (n n n 以二进制给出)。已知 n n n 为素数,当且仅当存在 a ∈ { 2 , … , n − 1 } a\in\{2,\dots,n-1\} a ∈ { 2 , … , n − 1 } ,使
a n − 1 ≡ 1 ( m o d n ) and a ( n − 1 ) / q ≢ 1 ( m o d n ) for every prime q ∣ n − 1. a^{n-1}\equiv1\pmod n\qquad\text{and}\qquad a^{(n-1)/q}\not\equiv1\pmod n\ \ \text{for every prime}\ q\mid n-1. a n − 1 ≡ 1 ( mod n ) and a ( n − 1 ) / q ≡ 1 ( mod n ) for every prime q ∣ n − 1. 证明 P R I M E S ∈ N P \mathrm{PRIMES}\in\mathrm{NP} PRIMES ∈ NP 。
直接以 a a a 作证书不够:验证者还需要 n − 1 n-1 n − 1 的素因子,且要确认它们确实是素数。于是递归地定义 Pratt 证书 C ( n ) C(n) C ( n ) :C ( 2 ) C(2) C ( 2 ) 为空;n > 2 n>2 n > 2 时,C ( n ) C(n) C ( n ) 由 a a a 、n − 1 n-1 n − 1 的分解 n − 1 = q 1 q 2 ⋯ q r n-1=q_1q_2\cdots q_r n − 1 = q 1 q 2 ⋯ q r (素因子按重数列出),以及每个 C ( q i ) C(q_i) C ( q i ) 组成。
验证 :检查 ∏ q i = n − 1 \prod q_i=n-1 ∏ q i = n − 1 ;用反复平方在 O ( log 3 n ) O(\log^3 n) O ( log 3 n ) 时间内计算 a n − 1 a^{n-1} a n − 1 与各 a ( n − 1 ) / q i m o d n a^{(n-1)/q_i}\bmod n a ( n − 1 ) / q i mod n ;再递归验证每个 C ( q i ) C(q_i) C ( q i ) 。
长度 :设 N ( p ) N(p) N ( p ) 为 C ( p ) C(p) C ( p ) 中出现的素数个数(递归树的结点数),断言 N ( p ) ≤ 2 log 2 p N(p)\le2\log_2 p N ( p ) ≤ 2 log 2 p 。N ( 2 ) = 1 ≤ 2 N(2)=1\le2 N ( 2 ) = 1 ≤ 2 ;奇素数 p p p 的 p − 1 p-1 p − 1 中至少有一个因子 2,对它用 N ( 2 ) = 1 N(2)=1 N ( 2 ) = 1 ,其余因子用归纳假设:
N ( p ) ≤ 1 + N ( 2 ) + ∑ i ≥ 2 2 log 2 q i = 2 + 2 ( log 2 ( p − 1 ) − 1 ) < 2 log 2 p , N(p)\le1+N(2)+\sum_{i\ge2}2\log_2 q_i=2+2\left(\log_2(p-1)-1\right)<2\log_2 p, N ( p ) ≤ 1 + N ( 2 ) + i ≥ 2 ∑ 2 log 2 q i = 2 + 2 ( log 2 ( p − 1 ) − 1 ) < 2 log 2 p , 其中 q 1 = 2 q_1=2 q 1 = 2 ,q 2 , … , q r q_2,\dots,q_r q 2 , … , q r 是 p − 1 p-1 p − 1 其余的素因子,它们的积为 ( p − 1 ) / 2 (p-1)/2 ( p − 1 ) /2 。
每个结点存一个不超过 n n n 的素数与一个底数,各 O ( log n ) O(\log n) O ( log n ) 位,故 ∣ C ( n ) ∣ = O ( log 2 n ) |C(n)|=O(\log^2 n) ∣ C ( n ) ∣ = O ( log 2 n ) ,验证总时间也是 log n \log n log n 的多项式。□ \square □
例:23 23 23 的 Pratt 证书
22 = 2 ⋅ 11 22=2\cdot11 22 = 2 ⋅ 11 ,取 a = 5 a=5 a = 5 :5 22 ≡ 1 5^{22}\equiv1 5 22 ≡ 1 ,5 22 / 2 = 5 11 ≡ 22 ≢ 1 5^{22/2}=5^{11}\equiv22\not\equiv1 5 22/2 = 5 11 ≡ 22 ≡ 1 ,5 22 / 11 = 5 2 ≡ 2 ≢ 1 ( m o d 23 ) 5^{22/11}=5^2\equiv2\not\equiv1\pmod{23} 5 22/11 = 5 2 ≡ 2 ≡ 1 ( mod 23 ) 。注意 a = 2 a=2 a = 2 不行:2 11 = 2048 = 89 ⋅ 23 + 1 2^{11}=2048=89\cdot23+1 2 11 = 2048 = 89 ⋅ 23 + 1 ,2 2 2 的阶只有 11 11 11 。证书必须给出一个阶恰为 n − 1 n-1 n − 1 的元(原根),而素数的原根总是存在的。
递归地,11 11 11 :10 = 2 ⋅ 5 10=2\cdot5 10 = 2 ⋅ 5 ,a = 2 a=2 a = 2 ,2 10 ≡ 1 2^{10}\equiv1 2 10 ≡ 1 ,2 5 ≡ 10 2^5\equiv10 2 5 ≡ 10 ,2 2 ≡ 4 ( m o d 11 ) 2^2\equiv4\pmod{11} 2 2 ≡ 4 ( mod 11 ) ;5 5 5 :4 = 2 ⋅ 2 4=2\cdot2 4 = 2 ⋅ 2 ,a = 2 a=2 a = 2 ,2 4 ≡ 1 2^4\equiv1 2 4 ≡ 1 ,2 2 ≡ 4 ( m o d 5 ) 2^2\equiv4\pmod5 2 2 ≡ 4 ( mod 5 ) 。证书树为
23 ( a = 5 ) → { 2 , 11 ( a = 2 ) → { 2 , 5 ( a = 2 ) → { 2 , 2 } } } , 23\ (a=5)\ \to\ \{2,\ 11\ (a=2)\ \to\ \{2,\ 5\ (a=2)\ \to\ \{2,2\}\}\}, 23 ( a = 5 ) → { 2 , 11 ( a = 2 ) → { 2 , 5 ( a = 2 ) → { 2 , 2 }}} , 共 N ( 23 ) = 7 N(23)=7 N ( 23 ) = 7 个结点,不超过 2 log 2 23 ≈ 9.05 2\log_2 23\approx9.05 2 log 2 23 ≈ 9.05 。
HALT 是 NP 难的 :设 H A L T = { ⟨ ⌞ M ⌟ , x ⟩ : M halts on x } \mathrm{HALT}=\{\langle\llcorner M\lrcorner,x\rangle:M\ \text{halts on}\ x\} HALT = {⟨ └ M ┘ , x ⟩ : M halts on x } 。证明 HALT 是 NP 难的。它是 NP 完全的吗?
(NP 难)只需给出 S A T ≤ p H A L T \mathrm{SAT}\le_p\mathrm{HALT} SAT ≤ p HALT (SAT 是 NP 完全的,再由传递性)。对 CNF 公式 φ \varphi φ ,令 M φ M_\varphi M φ 为如下机器:依次枚举全部赋值,若找到满足 φ \varphi φ 的赋值则停机;全部枚举完仍未找到,则进入死循环。f ( φ ) = ⟨ ⌞ M φ ⌟ , ε ⟩ f(\varphi)=\langle\llcorner M_\varphi\lrcorner,\varepsilon\rangle f ( φ ) = ⟨ └ M φ ┘ , ε ⟩ 可在多项式时间内写出(机器的描述只需「硬编码」φ \varphi φ ),且 φ ∈ S A T ⟺ M φ \varphi\in\mathrm{SAT}\iff M_\varphi φ ∈ SAT ⟺ M φ 停机。
(不是 NP 完全的)NP 中的语言都可以在指数时间内判定,而 HALT 不可判定,故 H A L T ∉ N P \mathrm{HALT}\notin\mathrm{NP} HALT ∈ / NP 。□ \square □
这说明 NP 难的问题可以远比 NP 难:NP 难只是「下界」,NP 完全才把问题的难度恰好钉在 NP 这一层。
9. 小结# 概念 定义 要点 NP x ∈ L ⟺ ∃ u , ∣ u ∣ ≤ p ( ∣ x ∣ ) , M ( x , u ) = 1 x\in L\iff\exists u,\ \lvert u\rvert\le p(\lvert x\rvert),\ M(x,u)=1 x ∈ L ⟺ ∃ u , ∣ u ∣ ≤ p (∣ x ∣) , M ( x , u ) = 1 多项式长度的证书 + 多项式时间验证 NTIME NDTM 在 c T ( n ) cT(n) c T ( n ) 时间内判定 N P = ⋃ c N T I M E ( n c ) \mathrm{NP}=\bigcup_c\mathrm{NTIME}(n^c) NP = ⋃ c NTIME ( n c ) :猜测证书再验证包含关系 P ⊆ N P ⊆ E X P \mathrm P\subseteq\mathrm{NP}\subseteq\mathrm{EXP} P ⊆ NP ⊆ EXP 穷举证书;P = ? N P \mathrm P\overset?=\mathrm{NP} P = ? NP 即穷举能否避免 Karp 归约 x ∈ L ⟺ f ( x ) ∈ L ′ x\in L\iff f(x)\in L' x ∈ L ⟺ f ( x ) ∈ L ′ 传递;方向是「已知难问题 ≤ p \le_p ≤ p 新问题」 NP 完全 NP 难且属于 NP 一个 NPC 问题属于 P ⟺ P = N P \iff\mathrm P=\mathrm{NP} ⟺ P = NP TMSAT 定义的改写 NPC 存在,但不自然
NP 完全问题构成一个等价类:它们要么全都在 P 中,要么全都不在。下一章用 Cook–Levin 定理给出第一个自然的 NP 完全问题 SAT,此后的 NP 完全性证明都从它出发。