P 刻画「能高效求解」的问题,NP 刻画「答案能高效验证」的问题。P 与 NP 是否相等,问的就是:验证与求解是否一样难。

1. 引入:验证比求解容易?

独立集:给定图 GG 与整数 kk,判定 GG 中是否存在 kk 个两两不相邻的顶点。

暴力算法枚举全部 (nk)\binom nk 个 kk 元子集,当 k≈n/2k\approx n/2 时是指数级的,至今不知道有多项式算法。但如果有人给出一个 kk 元子集 SS,检查它是否是独立集只需 O(k2)O(k^2) 次查邻接矩阵。求解似乎需要在指数大的空间中搜索,而验证只需检查一个候选。

NP 正是把「存在一个能被快速检查的解」形式化。

2. NP:多项式时间可验证

语言 L⊆{0,1}∗L\subseteq\{0,1\}^* 属于 NP,若存在多项式 p:N→Np:\mathbb N\to\mathbb N 与多项式时间图灵机 MM(称为 LL 的验证器),使对任意 x∈{0,1}∗x\in\{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∈Lx\in L 且 uu 满足 M(x,u)=1M(x,u)=1,称 uu 为 xx 的证书(证据)。

定义有两点值得注意:

证书长度有界:∣u∣|u| 是 ∣x∣|x| 的多项式,且 MM 关于 ∣x∣|x| 多项式时间运行(等价地,关于 ∣x∣+∣u∣|x|+|u| 多项式时间);

只有「是」实例需要证书:x∈Lx\in L 时存在证书,x∉Lx\notin L 时任何 uu 都被拒绝。「否」实例未必有简短的证明,这种不对称引出 coNP。

NP 不是「非多项式」

一个常见的误解是把 NP 读作 non-polynomial。恰恰相反,NP 中每个问题都「有一半是多项式的」:只要有人递上证书,就能多项式时间检查。P 中的问题全都属于 NP(第 3 节),而真正「非多项式」的问题多半不在 NP 中:例如判定「白方在一般化的 n×nn\times n 国际象棋中是否必胜」是 EXP 完全的,必胜策略是一棵指数大的博弈树,没有人知道怎样用多项式长的串证明它。N 指的是后面第 5 节的非确定性。

INDSET={⟨G,k⟩:∃S⊆V(G), ∣S∣=k, ∀u,v∈S, (u,v)∉E(G)}∈NP\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}。
验证器 MM:给定 ⟨G,k⟩\langle G,k\rangle 与串 uu,当且仅当 uu 编码了 GG 的 kk 个顶点、且其中任意两个之间没有边时输出 1,这可在多项式时间内完成,且 ⟨G,k⟩∈INDSET  ⟺  ∃u, M(⟨G,k⟩,u)=1\langle G,k\rangle\in\mathrm{INDSET}\iff\exists u,\ M(\langle G,k\rangle,u)=1。证书即构成独立集的 kk 个顶点的列表;若 GG 有 nn 个顶点,它可以用 klog⁡nk\log n 个比特编码,是 GG 的表示长度的多项式。□\square

以下问题都在 NP 中,证书都是「解本身」:

问题判定证书已知状态
旅行商(TSP)是否有总长 ≤k\le k 的哈密顿回路回路的顶点序列NP 完全
子集和是否有子集之和恰为 TT该子集NP 完全
线性规划线性不等式组是否有有理解一组解P(椭球法、内点法)
整数规划线性不等式组是否有整数解一组解NP 完全
图同构两个邻接矩阵是否表示同一个图顶点置换 π\pi未知(拟多项式)
合数NN 是否为合数NN 的因子分解P(AKS)
因子NN 是否有素因子 p∈[L,U]p\in[L,U]因子 pp未知,属于 NP∩coNP\mathrm{NP}\cap\mathrm{coNP}
连通性ss 与 tt 是否连通ss 到 tt 的路径P(BFS)

其中连通性用一次 BFS 即可判定;线性规划属于 P 则非常不平凡:Khachiyan(1979)的椭球法给出第一个多项式算法,Karmarkar(1984)的内点法给出第一个既多项式又实用的算法;合数判定直到 2002 年才由 Agrawal–Kayal–Saxena 证明属于 P。其余问题至今不知道多项式算法,但也没有人证明它们不在 P 中。

线性规划的证书长度

线性规划的证书是一组有理解,还需说明存在长度多项式的解:若可行域非空,则它有一个顶点,顶点是某个子方程组的唯一解,由 Cramer 法则,其分子、分母都是系数矩阵子式,位数是输入长度的多项式。整数规划同理需要论证存在小的整数解,这一点并不平凡。

3. P、NP 与 EXP

P⊆NP⊆EXP=⋃c>1DTIME(2nc).\mathrm P\subseteq\mathrm{NP}\subseteq\mathrm{EXP}=\bigcup_{c>1}\mathrm{DTIME}(2^{n^c}).

(P⊆NP\mathrm P\subseteq\mathrm{NP})设 L∈PL\in\mathrm P 由多项式时间图灵机 NN 判定。取定义中的 MM 为忽略证书、直接运行 NN 的机器,pp 为零多项式(uu 为空串),即得 L∈NPL\in\mathrm{NP}。

(NP⊆EXP\mathrm{NP}\subseteq\mathrm{EXP})设 L∈NPL\in\mathrm{NP},M,pM,p 如定义。枚举全部 2p(n)2^{p(n)} 个可能的 uu,用 MM 逐个检查,找到有效证书即接受。这需要 2p(n)⋅poly(n)=2O(p(n))2^{p(n)}\cdot\mathrm{poly}(n)=2^{O(p(n))} 时间;由于存在 c>1c>1 使 p(n)=O(nc)p(n)=O(n^c),该机器在 2O(nc)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 与 NP\mathrm{NP} 是否相等,问的是:穷举搜索一般能否避免?

4. P 与 NP

这是复杂性理论的核心公开问题,也是整个数学与科学中的重要问题。人们在直觉上普遍相信 P≠NP\mathrm P\ne\mathrm{NP}:

验证比发现容易:判断一个答案(证明)是否正确,通常比想出它容易得多;

搜索似乎不可避免:许多问题中,找到正确答案似乎必须在指数大的集合中穷举。

这个问题也是 Gödel(1956 年致 von Neumann 的信)问题的改写:是否存在多项式时间算法来寻找数学证明?「给定定理与长度上界 1n1^n,判定是否存在长度 ≤n\le n 的证明」属于 NP(证明本身就是证书),所以若 P=NP\mathrm P=\mathrm{NP},数学家的创造性工作在很大程度上可以自动化。

5. 非确定性图灵机

NP 最初是用非确定性图灵机(NDTM)定义的,NP 即 Nondeterministic Polynomial-time。

非确定性图灵机与标准图灵机的唯一区别是它有两个转移函数 δ0,δ1\delta_0,\delta_1,以及一个特殊的接受状态 qacceptq_{\mathrm{accept}}。计算的每一步,MM 任意选择应用 δ0\delta_0 或 δ1\delta_1。

  • 若存在某个选择序列使 MM 在输入 xx 上到达 qacceptq_{\mathrm{accept}},则 M(x)=1M(x)=1;若每个选择序列都使 MM 停机而未到达 qacceptq_{\mathrm{accept}},则 M(x)=0M(x)=0。
  • 称 MM 在 T(n)T(n) 时间内运行,若对每个输入 xx 与每个选择序列,MM 都在 T(∣x∣)T(|x|) 步内停机或到达 qacceptq_{\mathrm{accept}}。

NDTM 不是物理上可实现的模型:它「恰好」总能猜中正确的分支。

对 T:N→NT:\mathbb N\to\mathbb N 与 L⊆{0,1}∗L\subseteq\{0,1\}^*,称 L∈NTIME(T(n))L\in\mathrm{NTIME}(T(n)),若存在常数 c>0c>0 与 cT(n)cT(n) 时间的 NDTM MM,使对任意 xx,x∈L  ⟺  M(x)=1x\in L\iff M(x)=1。
NP=⋃c∈NNTIME(nc).\mathrm{NP}=\bigcup_{c\in\mathbb N}\mathrm{NTIME}(n^c).

(⊇\supseteq)设 LL 由 p(n)p(n) 时间的 NDTM NN 判定。x∈Lx\in L 当且仅当存在一个使 NN 在 xx 上到达 qacceptq_{\mathrm{accept}} 的选择序列,就用这个序列作为证书:它的长度为 p(∣x∣)p(|x|),确定性机器按序列逐步模拟 NN、检查是否进入 qacceptq_{\mathrm{accept}},可在多项式时间内验证。故 L∈NPL\in\mathrm{NP}。

(⊆\subseteq)设 L∈NPL\in\mathrm{NP},验证器为 MM,证书长度为 pp。构造 NDTM NN:在输入 xx 上,先利用非确定性选择写下一个长为 p(∣x∣)p(|x|) 的串 uu(令 δ0\delta_0 对应写 0,δ1\delta_1 对应写 1),再运行确定性验证器 M(x,u)M(x,u),若接受则进入 qacceptq_{\mathrm{accept}}。NN 进入 qacceptq_{\mathrm{accept}} 当且仅当 xx 存在有效证书;它运行多项式时间,故 L∈NTIME(nc)L\in\mathrm{NTIME}(n^c)。□\square

Fig 1 猜测,然后验证:NDTM 先非确定性地写下证书,再确定性地运行验证器
Fig 1 猜测,然后验证:NDTM 先非确定性地写下证书,再确定性地运行验证器

两种定义是「猜测,然后验证」的两种说法:证书就是非确定性选择序列,非确定性选择就是在猜证书。

6. 归约、NP 难与 NP 完全

独立集至少和 NP 中任何其他问题一样难:若它有多项式算法,则 NP 中所有问题都有。这一性质称为 NP 难。若 P≠NP\mathrm P\ne\mathrm{NP},一个语言是 NP 难的,便可以看作它不能在多项式时间内判定的证据。比较两个问题的难度,关键工具是归约。

称语言 LL 多项式时间 Karp 归约到 L′L',记作 L≤pL′L\le_p L',若存在多项式时间可计算的函数 f:{0,1}∗→{0,1}∗f:\{0,1\}^*\to\{0,1\}^*,使对任意 xx,

x∈L  ⟺  f(x)∈L′.x\in L\iff f(x)\in L'.

称 L′L' 是 NP 难的,若对任意 L∈NPL\in\mathrm{NP} 都有 L≤pL′L\le_p L';称 L′L' 是 NP 完全的,若它是 NP 难的且 L′∈NPL'\in\mathrm{NP}。

ff 把 LL 中的串映到 L′L' 中,把 L‾\overline L 中的串映到 L′‾\overline{L'} 中,于是判定 L′L' 的多项式时间机器 M′M' 可以变成判定 LL 的机器 M(x)=M′(f(x))M(x)=M'(f(x))。

Fig 2 Karp 归约 $L\le_p L'$:保持「是 / 否」的映射,与算法的复合
Fig 2 Karp 归约 L≤pL′L\le_p L':保持「是 / 否」的映射,与算法的复合

方向:要证明 BB 难,应把已知的难问题 AA 归约到 BB,即 A≤pBA\le_p B:「若能解 BB,就能解 AA」。反方向的 B≤pAB\le_p A 只说明 BB 不比 AA 难,对证明 BB 的难度毫无帮助;

两个方向都要证:x∈L⇒f(x)∈L′x\in L\Rightarrow f(x)\in L' 与 f(x)∈L′⇒x∈Lf(x)\in L'\Rightarrow x\in L 缺一不可,后者通常需要从 L′L' 的解「读回」LL 的解。

  1. 若 L≤pL′L\le_p L' 且 L′∈PL'\in\mathrm P,则 L∈PL\in\mathrm P;
  2. (传递性)若 L≤pL′L\le_p L' 且 L′≤pL′′L'\le_p L'',则 L≤pL′′L\le_p L'';
  3. 若 LL 是 NP 难的且 L∈PL\in\mathrm P,则 P=NP\mathrm P=\mathrm{NP};
  4. 若 LL 是 NP 完全的,则 L∈P  ⟺  P=NPL\in\mathrm P\iff\mathrm P=\mathrm{NP}。

关键事实:多项式时间机器的输出长度不超过其运行时间,故 ∣f(x)∣≤q(∣x∣)|f(x)|\le q(|x|),qq 为某多项式;而多项式的复合仍是多项式。

(1)设 ff 在 q(n)q(n) 时间内运行,L′L' 在 r(n)r(n) 时间内判定。计算 f(x)f(x) 再判定 f(x)∈L′f(x)\in L',共需 q(n)+r(q(n))q(n)+r(q(n)) 时间,是多项式。

(2)设 f1f_1 是 LL 到 L′L' 的归约,f2f_2 是 L′L' 到 L′′L'' 的归约,则 x↦f2(f1(x))x\mapsto f_2(f_1(x)) 可在多项式时间内计算,且 f2(f1(x))∈L′′  ⟺  f1(x)∈L′  ⟺  x∈Lf_2(f_1(x))\in L''\iff f_1(x)\in L'\iff x\in L。

(3)对任意 L′∈NPL'\in\mathrm{NP},由 NP 难性有 L′≤pLL'\le_p L,由(1)得 L′∈PL'\in\mathrm P,故 NP⊆P\mathrm{NP}\subseteq\mathrm P,结合 P⊆NP\mathrm P\subseteq\mathrm{NP} 即得。

(4)⇒\Rightarrow 即(3);⇐\Leftarrow:L∈NP=PL\in\mathrm{NP}=\mathrm P。□\square

由传递性,一旦有了一个 NP 完全问题 L0L_0,证明新问题 L∈NPL\in\mathrm{NP} 是 NP 完全的,只需给出 L0≤pLL_0\le_p L,而不必再面对 NP 中的全部语言。另一方面,归约也可以反过来用来证明「属于 NP」:

若 L≤pL′L\le_p L' 且 L′∈NPL'\in\mathrm{NP},则 L∈NPL\in\mathrm{NP}。
设 ff 是归约,∣f(x)∣≤q(∣x∣)|f(x)|\le q(|x|);L′L' 的验证器为 M′M',证书长 p′p'。令 LL 的验证器在 (x,u)(x,u) 上先算出 f(x)f(x),再输出 M′(f(x),u)M'(f(x),u)。证书长度 p′(q(∣x∣))p'(q(|x|)) 与运行时间都是 ∣x∣|x| 的多项式,且 x∈L  ⟺  f(x)∈L′  ⟺  ∃u, M′(f(x),u)=1x\in L\iff f(x)\in L'\iff\exists u,\ M'(f(x),u)=1。□\square

这个引理后面讨论 coNP 时会用到。下面用一个具体的归约演示「两个方向都要证」。

哈密顿圈归约到旅行商:哈密顿圈问题 HAMCYCLE 问无向图 GG 是否有经过每个顶点恰好一次的圈。证明 HAMCYCLE≤pTSP\mathrm{HAMCYCLE}\le_p\mathrm{TSP}。

设 G=(V,E)G=(V,E),∣V∣=n|V|=n。在同一顶点集上建完全图,令 d(u,v)=1d(u,v)=1((u,v)∈E(u,v)\in E)或 22(否则),取阈值 k=nk=n。构造只需 O(n2)O(n^2) 时间。

(⇒\Rightarrow)GG 的哈密顿圈是一条由 nn 条权为 11 的边组成的回路,总长 n≤kn\le k。

(⇐\Leftarrow)任何回路都有 nn 条边,每条权至少为 11。若总长 ≤n\le n,则每条边的权都是 11,即都是 GG 的边,这条回路就是 GG 的哈密顿圈。□\square

这个归约里的权都是 11 或 22,满足三角不等式,所以即使限制在度量空间中,TSP 仍然困难。把非边的权改成 ρn+1\rho n+1,还能得到更强的结论:GG 有哈密顿圈时最优回路长 nn,否则任何回路都 >ρn>\rho n,所以对一般(不满足三角不等式的)TSP,若 P≠NP\mathrm P\neq\mathrm{NP},任何多项式算法都不可能保证得到 ρ\rho 倍以内的近似解。归约不仅比较「能否精确求解」,稍加设计还能刻画「能否近似」。

剩下的问题是:第一个 NP 完全问题从哪里来?

Cook 归约

更宽松的 Cook 归约(Turing 归约)允许在多项式时间内多次调用 L′L' 的判定「预言机」,并对答案做任意后处理,例如取反。在 Cook 归约下 SAT\mathrm{SAT} 与其补 SAT‾\overline{\mathrm{SAT}} 等价,NP 难与 coNP 难便无法区分;坚持使用 Karp 归约,才能区分 NP 完全与 coNP 完全。

7. NP 完全问题存在吗

TMSAT={⟨⌞M⌟,x,1n,1t⟩:∃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}\}

是 NP 完全的。

(TMSAT∈NP\mathrm{TMSAT}\in\mathrm{NP})证书为 uu,验证器用通用图灵机模拟 MM 在 ⟨x,u⟩\langle x,u\rangle 上运行 tt 步,时间为 poly(∣⌞M⌟∣,t)\mathrm{poly}(|\llcorner M\lrcorner|,t)。由于 nn 与 tt 以一元形式 1n,1t1^n,1^t 给出,这是输入长度的多项式。

(NP 难)设 L∈NPL\in\mathrm{NP},验证器 MM 在 q(m)q(m) 时间内运行,证书长度为 p(∣x∣)p(|x|)。令

f(x)=⟨⌞M⌟, x, 1p(∣x∣), 1q(∣x∣+p(∣x∣))⟩,f(x)=\left\langle\llcorner M\lrcorner,\ x,\ 1^{p(|x|)},\ 1^{q(|x|+p(|x|))}\right\rangle,

它可在多项式时间内计算,且由 NP 的定义,x∈L  ⟺  f(x)∈TMSATx\in L\iff f(x)\in\mathrm{TMSAT}。□\square

证明几乎就是 NP 定义的改写,一元编码 1n,1t1^n,1^t 是为了让「模拟 tt 步」是输入长度的多项式。但 TMSAT 并不实用:它的定义与图灵机这一概念紧密纠缠,要把它归约到图、公式、数等组合问题并不方便。第一个「自然」的 NP 完全问题是 SAT,见Cook–Levin 定理。

8. 习题

PRIMES ∈\in NP:设 PRIMES={n:n is prime}\mathrm{PRIMES}=\{n:n\ \text{is prime}\}(nn 以二进制给出)。已知 nn 为素数,当且仅当存在 a∈{2,…,n−1}a\in\{2,\dots,n-1\},使

an−1≡1(modn)anda(n−1)/q≢1(modn)  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.

证明 PRIMES∈NP\mathrm{PRIMES}\in\mathrm{NP}。

直接以 aa 作证书不够:验证者还需要 n−1n-1 的素因子,且要确认它们确实是素数。于是递归地定义 Pratt 证书 C(n)C(n):C(2)C(2) 为空;n>2n>2 时,C(n)C(n) 由 aa、n−1n-1 的分解 n−1=q1q2⋯qrn-1=q_1q_2\cdots q_r(素因子按重数列出),以及每个 C(qi)C(q_i) 组成。

验证:检查 ∏qi=n−1\prod q_i=n-1;用反复平方在 O(log⁡3n)O(\log^3 n) 时间内计算 an−1a^{n-1} 与各 a(n−1)/qi mod na^{(n-1)/q_i}\bmod n;再递归验证每个 C(qi)C(q_i)。

长度:设 N(p)N(p) 为 C(p)C(p) 中出现的素数个数(递归树的结点数),断言 N(p)≤2log⁡2pN(p)\le2\log_2 p。N(2)=1≤2N(2)=1\le2;奇素数 pp 的 p−1p-1 中至少有一个因子 2,对它用 N(2)=1N(2)=1,其余因子用归纳假设:

N(p)≤1+N(2)+∑i≥22log⁡2qi=2+2(log⁡2(p−1)−1)<2log⁡2p,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,

其中 q1=2q_1=2,q2,…,qrq_2,\dots,q_r 是 p−1p-1 其余的素因子,它们的积为 (p−1)/2(p-1)/2。 每个结点存一个不超过 nn 的素数与一个底数,各 O(log⁡n)O(\log n) 位,故 ∣C(n)∣=O(log⁡2n)|C(n)|=O(\log^2 n),验证总时间也是 log⁡n\log n 的多项式。□\square

例:2323 的 Pratt 证书

22=2⋅1122=2\cdot11,取 a=5a=5:522≡15^{22}\equiv1,522/2=511≡22≢15^{22/2}=5^{11}\equiv22\not\equiv1,522/11=52≡2≢1(mod23)5^{22/11}=5^2\equiv2\not\equiv1\pmod{23}。注意 a=2a=2 不行:211=2048=89⋅23+12^{11}=2048=89\cdot23+1,22 的阶只有 1111。证书必须给出一个阶恰为 n−1n-1 的元(原根),而素数的原根总是存在的。

递归地,1111:10=2⋅510=2\cdot5,a=2a=2,210≡12^{10}\equiv1,25≡102^5\equiv10,22≡4(mod11)2^2\equiv4\pmod{11};55:4=2⋅24=2\cdot2,a=2a=2,24≡12^4\equiv1,22≡4(mod5)2^2\equiv4\pmod5。证书树为

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\}\}\},

共 N(23)=7N(23)=7 个结点,不超过 2log⁡223≈9.052\log_2 23\approx9.05。

HALT 是 NP 难的:设 HALT={⟨⌞M⌟,x⟩:M halts on x}\mathrm{HALT}=\{\langle\llcorner M\lrcorner,x\rangle:M\ \text{halts on}\ x\}。证明 HALT 是 NP 难的。它是 NP 完全的吗?

(NP 难)只需给出 SAT≤pHALT\mathrm{SAT}\le_p\mathrm{HALT}(SAT 是 NP 完全的,再由传递性)。对 CNF 公式 φ\varphi,令 MφM_\varphi 为如下机器:依次枚举全部赋值,若找到满足 φ\varphi 的赋值则停机;全部枚举完仍未找到,则进入死循环。f(φ)=⟨⌞Mφ⌟,ε⟩f(\varphi)=\langle\llcorner M_\varphi\lrcorner,\varepsilon\rangle 可在多项式时间内写出(机器的描述只需「硬编码」φ\varphi),且 φ∈SAT  ⟺  Mφ\varphi\in\mathrm{SAT}\iff M_\varphi 停机。

(不是 NP 完全的)NP 中的语言都可以在指数时间内判定,而 HALT 不可判定,故 HALT∉NP\mathrm{HALT}\notin\mathrm{NP}。□\square

这说明 NP 难的问题可以远比 NP 难:NP 难只是「下界」,NP 完全才把问题的难度恰好钉在 NP 这一层。

9. 小结

概念定义要点
NPx∈L  ⟺  ∃u, ∣u∣≤p(∣x∣), M(x,u)=1x\in L\iff\exists u,\ \lvert u\rvert\le p(\lvert x\rvert),\ M(x,u)=1多项式长度的证书 + 多项式时间验证
NTIMENDTM 在 cT(n)cT(n) 时间内判定NP=⋃cNTIME(nc)\mathrm{NP}=\bigcup_c\mathrm{NTIME}(n^c):猜测证书再验证
包含关系P⊆NP⊆EXP\mathrm P\subseteq\mathrm{NP}\subseteq\mathrm{EXP}穷举证书;P=?NP\mathrm P\overset?=\mathrm{NP} 即穷举能否避免
Karp 归约x∈L  ⟺  f(x)∈L′x\in L\iff f(x)\in L'传递;方向是「已知难问题 ≤p\le_p 新问题」
NP 完全NP 难且属于 NP一个 NPC 问题属于 P   ⟺  P=NP\iff\mathrm P=\mathrm{NP}
TMSAT定义的改写NPC 存在,但不自然

NP 完全问题构成一个等价类:它们要么全都在 P 中,要么全都不在。下一章用 Cook–Levin 定理给出第一个自然的 NP 完全问题 SAT,此后的 NP 完全性证明都从它出发。