09 · NP完全

← 返回课程目录
本文目录

本文最后更新于 2026年11月5日 晚上

北京大学信息科学技术学院
算法设计与分析(2026春)的课程笔记

第九章:NP完全

和第八章比起来,这一章的抽象程度有过之而无不及,前半段是无数个抽象的定义,后半段则是有限个更抽象的证明,让我们慢慢欣赏~

P类与NP类

易解问题与难解问题

先给出两个函数多项式相关的概念:
设ff,gg都为N→NN \rightarrow N的函数,若∃多项式p,q\exists 多项式p,q,使得对于所有的n∈Nn \in N,都有f(n)≤p(n)f(n) \leq p(n)且g(n)≤q(n)g(n) \leq q(n),则称ff和gg是多项式相关的
例如nlognnlogn和n2n^2,n2+2n+5n^2+2n+5和n10n^{10}是多项式相关
lognlogn和nn,n5n^5和2n2^n则不是多项式相关

接下来我们假设问题为Π\Pi,实例为II,用算法AA求解II时,首先要把II编码成二进制字符串作为AA的输入,我们称II的二进制编码长度为II的规模,记作∣I∣|I|
(对于编码有一些说明,编码时不能故意多使用冗余字符,编码不能采用一进制等等)
如果存在函数f:N→Nf:N \rightarrow N,使得对于任意规模为nn的实例II,AA对II的运算在f(n)f(n)步内停止,则AA的时间复杂度为f(n)f(n)
于是有了一些定义~

多项式时间算法: 以多项式为时间复杂度.
易解的问题: 有多项式时间算法
难解的问题: 不存在多项式时间算法

先前我们已经学过了排序、最小生成树、单源最短路径等问题的多项式时间算法,所以他们都是易解问题
现在也已经证明了一些难解问题,有的是完全没法解,有的是有解但无法在多项式时间内解出
但难办的是还有一些问题,既找不到多项式时间算法,又无法证明它们是难解的,如哈密顿回路、货郎、背包问题,下面我们重点讨论的就是这些问题

判定问题

判定问题是指答案只有是或否的问题
形式化来说,判定问题Π\Pi可以定义为有序对<DΠ,YΠ><D_\Pi,Y_\Pi>,其中DΠD_\Pi为Π\Pi所有实例组成的集合,YΠ⊆DΠY_\Pi \subseteq D_\Pi 由所有答案为Yes的实例组成

例如哈密顿回路(HC):任给无向图G,问G中是否存在HC(一个经过每个顶点恰好一次的回路),可以定义为<DHC,YHC><D_{HC},Y_{HC}>,其中DHCD_{HC}为所有无向图组成的集合,YHCY_{HC}为所有存在HC的无向图组成的集合
显然,如果搜索HC是易解的,那么判定HC也是易解的,反之亦然

货郎问题(TSP):任给nn个城市,城市ii与jj之间正整数距离为d(i,j)d(i,j),1≤i,j≤n1 \le i,j \le n,以及正整数DD,问是否存在一条每一个城市恰好经过一次且长度不超过DD的巡回路线,也即是否存在1,2,...,n1,2,...,n的排列σ\sigma,使得Σi=1nd(σ(i),σ(i+1))≤D\Sigma_{i=1}^{n} d(\sigma(i),\sigma(i+1)) \leq D(其中σ(n+1)=σ(1)\sigma(n+1)=\sigma(1))
同理,搜索TSP需要给出一条最短的巡回路线,如果搜索TSP易解,那么判定也是易解,所以TSP的组合优化问题不会比判定TSP问题容易

一般地说,组合优化问题Π∗\Pi^{\ast}由三部分组成:

  • 实例集DΠ∗D_{\Pi^{\ast}}
  • 对每一个实例I∈DΠ∗I \in D_{\Pi^{\ast}},有一个非空有穷集合S(I)S(I),它的元素称为II的可行解
  • 对每一个可行解s∈S(I)s \in S(I),有一个正整数c(s)c(s),称为ss的值

当Π∗\Pi^{\ast}为最小化问题时,若s∗∈S(I)s^{\ast} \in S(I),使得对于所有s∈S(I)s \in S(I),c(s∗)<c(s)c(s^{\ast})<c(s)
则称s∗s^{\ast}为II的最优解,c(s∗)c(s^{\ast})为II的最优值,记作OPT(I)OPT(I)
(最大化问题同理,感觉这段就是用极为形式化的语言说了一些废话)

Π∗\Pi^{\ast}对应的判定问题Π=<DΠ,YΠ>\Pi=<D_\Pi,Y_\Pi>则定义如下:
DΠ=[(I,K)∣I∈DΠ∗,K∈Z∗]D_{\Pi}=[(I,K)|I \in D_{\Pi^{\ast}}, K \in Z^{\ast}]
当Π∗\Pi^{\ast}为最小化问题时,YΠ=[(I,K)∣OPT(I)≤K]Y_{\Pi}=[(I,K)|OPT(I) \le K]
最大化同理,不等号反向即可

NP类

所有多项式时间可解的判定问题组成的问题类称作 P类
(这里的重点在于必须是判定问题,组合优化问题不属于 P类!)

对于一个判定问题Π=<DΠ,YΠ>\Pi=<D_\Pi,Y_\Pi>,如果存在两个输入变量的多项式时间算法AA和多项式pp,使得对于任意实例I∈DΠI \in D_\Pi
I∈YΠ  ⟺  ∃t,∣t∣≤p(∣I∣),且A对输入I,t输出YesI \in Y_\Pi \iff \exists t,|t| \le p(|I|),且A对输入I,t输出Yes
则称Π\Pi为多项式时间可验证的,AA为Π\Pi的多项式时间验证算法
当I∈YΠI \in Y_\Pi时,称tt为I∈YΠI \in Y_\Pi的证据

所有多项式时间可验证的判定问题组成的问题类称作 NP类

我们来看,对于HC问题,可以设计如下算法:
任意给出无向图GG,猜想所有顶点的某个排列,验证该排列是否构成一条HC,若是则回答Yes,否则回答No
当GG为哈密顿图时,总能猜对一个排列;否则算法就永远回答No
猜想一个排列并检查其是否构成HC可以在多项式时间内完成,故$HC \in NP $

再比如,0-1背包问题:
任给nn件物品和一个背包,物品ii的重量为wiw_i,价值viv_i,1≤i≤n1 \le i \le n,背包重量限制BB,目标价值KK,其中wi,vi,B,Kw_i,v_i,B,K均为正整数,问是否能在背包中装下总价值不少于KK且总重量不超过BB的物品
即是否存在子集T⊆[1,2,...,n]T \subseteq [1,2,...,n]使得Σi∈Twi≤B\Sigma_{i \in T}w_i \le B且Σi∈Tvi≥K\Sigma_{i \in T}v_i \ge K
显然我们能够多项式时间内任意猜想[1,2,...,n][1,2,...,n]的一个子集,并检查其是否满足上述两个不等式,故0-1背包也是NP问题

类似地,最长公共子序列也是NP问题
不难证明,P⊆NPP \subseteq NP
现在的问题是P=NPP=NP吗?

多项式时间变化与NP完全

多项式时间变换

由于对于许多NP问题始终找不到多项式时间算法,但也无法证明就是难解的
我们只能另辟蹊径,如果NP中有难解,那么NP中最难的必为难解
这就牵扯到了比较问题之间的难度

设判定问题Π1=<D1,Y1>\Pi_1=<D_1,Y_1>,Π2=<D2,Y2>\Pi_2=<D_2,Y_2>,若函数f:D1→D2f:D_1 \rightarrow D_2满足:

  • ff多项式时间可计算
  • 对于所有I∈D1I\in D_1,I∈Y1  ⟺  f(I)∈Y2I \in Y_1 \iff f(I) \in Y_2

则称ff为Π1\Pi_1到Π2\Pi_2的多项式时间变换
如果存在Π1\Pi_1到Π2\Pi_2的多项式时间变换,则称Π1\Pi_1可多项式时间变换到Π2\Pi_2,记作Π1≤pΠ2\Pi_1 \le_p \Pi_2

例如:HC≤pTSPHC \le_p TSP
规定HCHC到TSPTSP的变换ff,对于HCHC任意实例II为无向图G=<V,E>G=<V,E>,TSPTSP对应实例f(I)f(I)为城市集VV,任意两个不同的城市u,vu,v之间距离
d(u,v)=1,if(u,v)∈E;else,d(u,v)=2d(u,v)=1,if (u,v) \in E;else,d(u,v)=2
界限D=∣V∣D=|V|
显然ff是多项式可计算的,f(I)f(I)中每个城市恰好经过一次的巡回路线有∣V∣|V|条边,每条边长度为1或2,故巡回路线长度≥D\ge D
刚好等于D时,每条边长度均为1,刚好等价于存在哈密顿回路,从而得证

又比如:最大生成树 ≤p\le_p 最小生成树
这里定义最小生成树:任给连通无向带权图G=<V,E,W>G=<V,E,W>,权WW、界限BB为正整数,问是否存在权不超过BB的生成树
最大生成树则是把界限改为DD,问是否存在权不小于DD的生成树

任给最大生成树实例II:连通无向带权图G=<V,E,W>G=<V,E,W>,界限DD
最小生成树对应实例f(I)f(I):G′=<V,E,W′>G'=<V,E,W'>,B=(n−1)M−DB=(n-1)M-D
其中n=∣V∣n=|V|,M=max[W(e)∣e∈E]+1M=max[W(e)|e \in E]+1,W′(e)=M−W(e)W'(e)=M-W(e)
假设存在GG生成树TT,Σe∈TW(e)≥D\Sigma_{e \in T}W(e) \ge D,则有
Σe∈TW′(e)=(n−1)M−Σe∈TW(e)≤B\Sigma_{e \in T}W'(e)=(n-1)M-\Sigma_{e \in T}W(e) \le B
反之亦然同理,并且ff显然在多项式时间内可计算,得证
下面是一个变换实例

接下来是关于≤p\le_p的各种性质,限于篇幅这里就只列举而不详细证明了
传递性:Π1≤pΠ2\Pi_1 \le_p \Pi_2,Π2≤pΠ3\Pi_2 \le_p \Pi_3,则Π1≤pΠ3\Pi_1 \le_p \Pi_3
Π1≤pΠ2\Pi_1 \le_p \Pi_2,则Π2∈P→Π1∈P\Pi_2 \in P \rightarrow \Pi_1 \in P,Π1\Pi_1难解 →\rightarrow Π2\Pi_2难解

由此可见,≤p\le_p提供了比较判定问题之间难度的一种方法,这也类似于上一章最后提到的归约

NP完全性及其性质

如果对于所有Π′∈NP\Pi' \in NP,Π′≤pΠ\Pi' \le_p \Pi,则称Π\Pi为NP难的
如果Π\Pi为NP难的且Π∈NP\Pi \in NP,则称其为NP完全的
由此可见,NP完全问题是NP中最难的问题

于是可以推出,如果存在NP难问题Π∈P\Pi \in P,则P=NPP=NP
大部分人相信P=NPP=NP不成立,所以NP完全性很可能是一个问题难解(不属于P)的证据

由≤p\le_p的难度比较,若Π′\Pi'为NP难,Π′≤pΠ\Pi' \le_p \Pi,那么Π\Pi显然也是NP难
如果同时还有Π,Π′∈NP\Pi,\Pi' \in NP,那么Π\Pi就是NP完全的
于是我们得到了证明NP完全非常重要的办法:

  • 证明Π∈NP\Pi \in NP
  • 找到Π′\Pi'为NP完全,且Π′≤pΠ\Pi' \le_p \Pi

后面的叙述中我们会把NP完全简称为NPC(NP Complete)

第一个NPC问题:Cook-levin定理

在ai引论中我们学习过命题逻辑,合取范式析取范式等,例如:
F1=(¬x1∧x2∧¬x3)→(x1∧¬x2)F_1=(\lnot x_1 \land x_2 \land \lnot x_3) \rightarrow (x_1 \land \lnot x_2)
F2=(x1∨x2)∧(¬x1∨x2∨x3)∧¬x2F_2=(x_1 \lor x_2) \land (\lnot x_1 \lor x_2 \lor x_3)\land \lnot x_2
F3=(x1∨¬x2∨x3)∧(¬x1∨¬x2∨x3)∧x2∧¬x3F_3=(x_1 \lor \lnot x_2 \lor x_3)\land(\lnot x_1 \lor \lnot x_2 \lor x_3)\land x_2 \land \lnot x_3
这里F1F_1是合式公式,但不是合取范式,F2,F3F_2,F_3都是合取范式
合取范式括号之间用∧\land连接,析取范式则用∨\lor

给定每个变元的真假值称为变元的赋值,如果赋值tt使得FF为真,则称tt为FF的成真赋值,如果FF存在成真赋值,称FF为可满足的
例如令t(x1)=t(x3)=1,t(x2)=0t(x_1)=t(x_3)=1,t(x_2)=0,可知tt为F1,F2F_1,F_2的成真赋值,故F1,F2F_1,F_2都是可满足的,tt不为F3F_3成真赋值,事实上F3F_3本身就不可满足,找不到解

SAT问题:任给一个合取范式,问它是否是可满足的
Cook-levin定理:SAT是NPC问题,证明过难从略

几个NPC问题

接下来我们会从第一个NPC:SAT问题开始,利用多项式时间变换证明别的NPC,关系如图所示

MAX-SAT和3SAT

设判定问题Π=<D,Y>\Pi=<D,Y>,Π′=<D′,Y′>\Pi'=<D',Y'>,如果D′⊆DD' \subseteq D,Y′=D′∩YY'=D'\cap Y,那么Π′\Pi'实际上是Π\Pi的特殊情况,称作Π\Pi的子问题
例如HC的一个子问题是:给定一个平面图G,问G是否为哈密顿图

接下来我们看MAX-SAT:任给关于x1,x2,...,xnx_1,x_2,...,x_n的简单析取范式C1,C2,...,CmC_1,C_2,...,C_m,问是否存在关于x1,x2,...,xnx_1,x_2,...,x_n的赋值,使得C1,C2,...,CmC_1,C_2,...,C_m中至少KK个为真
当K=mK=m时,MAX-SAT就变为了SAT,所以SAT是MAX-SAT的子问题

显然一般情况总会难于特殊情况,如果子问题NP难,那么原问题显然更是NP难
于是我们来证明:MAX-SAT是NPC
显然MAX-SAT$\in $NP,任意猜想一个赋值验证即可
SAT ≤p\le_p MAXSAT也是非常容易证明的,从而MAX-SAT是NPC的

下面考虑SAT的一个子问题:3SAT
合取范式中每个简单析取范式恰好三个文字,称为3元合取范式
3SAT:任给一个3元合取范式,问其是否是可满足的
于是我们来证明:3SAT是NPC
由于3SAT为SAT特殊情况,故3SAT$\in $NP

接下来要证明SAT≤p\le_p 3SAT
任给一个合取范式FF,要构造对应3元合取范式F′=f(F)F'=f(F),使得FF可满足  ⟺  \iffF′F'可满足
设F=∧1≤j≤mCjF=\land_{1 \le j \le m}C_j,CjC_j为简单析取范式
对应F′=∧1≤j≤mFj′F'=\land_{1 \le j \le m}F'_j,其中Fj′F'_j对应CjC_j,为3元合取范式,并且CjC_j可满足  ⟺  \iff Fj′F'_j可满足
下面我们分情况讨论构造Fj′F'_j

看上去十分高深,说穿了就是凑数法,如果CjC_j变元少于3个就补上,多于3个就把它平摊,最后用奇妙的办法让赋值结果一样即可
显然该构造可以在多项式时间内完成,故3SAT是NPC得证

这里用到的方法叫做局部替换法,因为此处两个问题的结构非常相似

顶点覆盖、团和独立集

设无向图G=<V,E>G=<V,E>,V′⊆VV' \subseteq V
如果GG每一条边都至少有一个顶点在V′V'中,称V′V'为GG的一个顶点覆盖
如果对于任意u,v∈V′,u≠vu,v \in V',u \neq v都有(u,v)∈E(u,v) \in E,则称V′V'为GG的一个团
如果对于任意u,v∈V′u,v \in V'都有(u,v)∉E(u,v) \notin E,则称V′V'为GG的一个独立集

引理:下列命题等价

  • V′V'是GG顶点覆盖
  • V−V′V-V'是GG独立集
  • V−V′V-V'是补图Gˉ=<V,Eˉ>\bar{G}=<V,\bar{E}>的团

下面我们考虑这样的三个问题:

  • 顶点覆盖(VC):正整数K≤∣V∣K \le |V|,问GG是否存在顶点数不超过KK的顶点覆盖
  • 团:正整数J≤∣V∣J \le |V|,问GG是否存在顶点数不少于JJ的团
  • 独立集:正整数J≤∣V∣J \le |V|,问GG是否存在顶点数不少于JJ的独立集

显然,这三个问题都属于NP,并且根据引理,很容易将这三个问题通过多项式时间互相变换,所以只需证明其中一个NPC,即可得到另外两个NPC
下面我们证明:VC是NPC问题

首先不难证明VC∈\inNP,任意猜想一个顶点集合验证即可
下面我们证明3SAT≤p\le_pVC
ppt中的证明实在过于晦涩难懂,我们这里稍加简化
3SAT中每个变元xix_i做成两个点xix_i和xiˉ\bar{x_i},中间连一条边
顶点覆盖必须在这两个点之中选一个,这相当于给xix_i赋值

3SAT每个子句都只有三个变元可以做成一个三角形,那么顶点覆盖必须在这个三角形中选两个点,剩下没选的那个点对应的文字,就是子句中为真的那个,最终整个图需要n+2mn+2m个顶点,其中nn为变量数,mm为子句数,这样3SAT有解  ⟺  \iff这个图有大小恰好为n+2mn+2m的顶点覆盖

由于3SAT是NPC,所以VC也是NPC
这里采用的方法称为构件设计法

其他常见NPC问题(了解即可)

有向哈密顿回路:任给有向图,问其中是否存在哈密顿回路
恰好覆盖:是否能用一些彼此不交的子集恰好拼出某个集合
子集和:给定正整数集合,问其是否存在子集,子集之和刚好为某个给定正整数
装箱:知道nn件物品各自重量,共有KK个箱子,每只箱子重量上限不超过BB,问是否能用KK个箱子装完所有物品
双机调度问题:前面几章有提到过,大概就是两台一样的机器和完全没有先后顺序要求的nn项作业,问是否能在ddl之前合理分配作业让两台机器做,从而完成所有作业
整数线性规划:Am×nA_{m\times n}整数矩阵,bm×1b_{m \times 1}向量,问是否存在xn×1x_{n \times 1}向量,且xx的每一维都是正整数,使得Ax≥bAx \ge b

具体证明方法如下,不再一一讨论

从判定问题到优化问题:Turing归约

设π1,π2\pi_1,\pi_2为搜索问题或优化问题,AA是利用解π2\pi_2的”假想子程序“ss来解π1\pi_1的算法
只要s,As,A都是多项式时间的,那么我们称
算法AA是从π1\pi_1到π2\pi_2多项式时间的Turing归约
这时也称π1\pi_1Turing归约到π2\pi_2,记作π1∝Tπ2\pi_1 \propto_T \pi_2
本质上相当于只要你多项式时间能解出π2\pi_2,那多项式时间之内π1\pi_1也迎刃而解
显然,多项式变换是特殊的Turing归约

设π\pi是搜索问题,如果存在NPC问题π′\pi',π′∝Tπ\pi' \propto_T \pi,则称π\pi为NP-hard
这意味着从多项式可计算角度来说,π\pi至少和NPC问题一样难
许多NPC对应的优化问题都是NP-hard
反之也有许多优化问题可以Turing归约到对应判定问题,称作NP-easy
NP-hard+NP-easy称为NP等价

例如货郎问题的优化问题(给出一条最短的巡回路线)是NP等价的
首先它是NP-hard,这个十分显然,下面我们证明它是NP-easy(能用判定问题黑箱解决)
解法:

  • 用二分法猜一个最短长度B*(介于最小可能和最大可能之间)
  • 每次调用判定问题的黑箱,问“有没有长度不超过B的路线?”
  • 根据答案缩小范围,最后找到B*
  • 再一步步构造出具体路线(比如先选第一个城市,再试第二个…)

同样可以证明六个基本NPC问题对应的优化问题都是NP-等价的

笔者按:终于更完了这一章……头晕脑胀ing,NP这些抽象概念和抽象证明实在是害人不浅,但是这些没学好的话第十章也不方便更新,凑合着写完了长篇大论,日后想必还需要多多复习

NP完全
https://yjyxfcy.github.io/2026/05/26/sf2/
作者
Yjy
发布于
2026年5月26日
更新于
2026年11月5日
许可协议