1
第 8章 NP完全性理论
2
8.1 计算模型
8.1.1 随机存取机 RAM
8.1.2 随机存取存储程序机 RASP
8.1.3 RAM模型的变形与简化
8.1.4 图灵机
8.1.5 图灵机模型与 RAM模型的关系
8.1.6 问题变换与计算复杂性归约
3
8.1.1 随机存取机 RAM
1,RAM的结构
4
8.1.1 随机存取机 RAM
2,RAM程序一个 RAM程序定义了从输入带到输出带的一个映射。可以对这种映射关系作 2种不同的解释。
解释一：把 RAM程序看成是计算一个函数若一个 RAM程序 P总是从输入带前 n个方格中读入 n个整数
x1,x2,…,xn,并且在输出带的第一个方格上输出一个整数 y
后停机，那么就说程序 P计算了函数 f(x1,x2,…,xn)=y
解释二：把 RAM程序当作一个语言接受器。
将字符串 S=a1a2… an放在输入带上。在输入带的第一个方格中放入符号 a1,第二个方格中放入符号 a2,…,第 n个方格中放入符号 an。 然后在第 n+1个方格中放入 0，作为输入串的结束标志符。如果一个 RAM程序 P读了字符串 S及结束标志符 0后，在输出带的第一格输出一个 1并停机，就说程序 P接受字符串 S。
5
8.1.1 随机存取机 RAM
3,RAM程序的耗费标准标准一：均匀耗费标准在均匀耗费标准下，每条 RAM指令需要一个单位时间；每个寄存器占用一个单位空间。以后除特别注明,RAM程序的复杂性将按照均匀耗费标准衡量。
标准二：对数耗费标准对数耗费标准是基于这样的假定，即执行一条指令的耗费与以二进制表示的指令的操作数长度成比例。在 RAM计算模型下，
假定一个寄存器可存放一个任意大小的整数。因此若设 l(i)是整数 i所占的二进制位数，则
0
0
1
||l o g)(
i
iiil
6
8.1.2 随机存取存储程序机 RASP
1,RASP的结构
RASP的整体结构类似于 RAM,所不同的是 RASP的程序是存储在寄存器中的。每条 RASP指令占据 2个连续的寄存器。第一个寄存器存放操作码的编码，第二个寄存器存放地址。 RASP指令用整数进行编码。
2,RASP程序的复杂性不管是在均匀耗费标准下，还是在对数耗费标准下,RAM
程序和 RASP程序的复杂性只差一个常数因子。在一个计算模型下 T(n)时间内完成的输入 -输出映射可在另一个计算模型下模拟，并在 kT(n)时间内完成。其中 k是一个常数因子。空间复杂性的情况也是类似的。
7
8.1.3 RAM模型的变形与简化
1,实随机存取机 RRAM
在 RRAM模型下，一个存储单元可以存放一个实数。下列的各运算为基本运算且每个运算只耗费单位时间。
(1)算术运算 +，－，×，／。
(2)2个实数间的比较 (<,≤,=,≠,≥,>)。
(3)间接寻址 (整数地址 )。
(4)常见函数的计算，如三角函数，指数函数，
对数函数等。
优点：能够方便处理实数；
适合于用 FORTRAN,PASCAL等高级语言写的算法。
8
8.1.3 RAM模型的变形与简化
2,直线式程序对于许多问题，所设计的 RAM程序中的转移指令仅用于重复一组指令，而且重复的次数与问题的输入规模 n成比例。在这种情况下，可以用重复地写出相同指令组的方法来消除程序中的循环。
由此，对每一个固定的 n得到一个无循环的直线式程序。
经过对 RAM模型的简化，得到直线式程序的指令系统如下：
x←y+z
x←y -z
x←y*z
x←y/z
x←i
其中 x,y和 z是符号地址 (或变量 )，而 i是常数。
每条指令耗费一个单位时间。
9
8.1.3 RAM模型的变形与简化
3,位式计算直线式程序计算模型显然是基于均匀耗费标准的。在对数耗费标准下，使用另一个 RAM的简化计算模型，称之为位式计算
(Bitwise Computation)模型。
除了下列 2点外，该计算模型与直线式程序计算模型基本相同：
(1)假设所有变量取值 0或 1，即为位变量。
(2)所用的运算是逻辑运算而不是算术运算。
用 ∧ 代表与,∨ 代表或,?代表异或,?代表非。
在位式计算模型下，每个逻辑运算指令耗费一个单位时间。
10
8.1.3 RAM模型的变形与简化
4,位向量运算 (Bit Vector Operations)
若在直线式程序计算模型中，假设所有变量均为位向量，而且所用的运算均为位操作指令，则得到位向量运算计算模型。
例如，要表示一个有 100个顶点的图中从顶点 v到其余各顶点间有没有边相连，可以用 100位的一个位向量表示。若顶点 v到顶点 vj之间有边相连，则该位向量的第 j位为 1，否则为 0。
缺点,所需的机器字长要远大于其他模型。
11
8.1.3 RAM模型的变形与简化
5,判定树判定树是一棵二叉树。它的每个内结点表示一个形如 x∶y 的比较。指向该结点左儿子的边相应于 x≤y,标号为 ≤ 。指向该结点右儿子的边相应于 x>y,标号为 >。每一次比较耗费一个单位时间。下图是对 a,b,c三个数进行排序的一棵判定树。
在判定树模型下，
算法的时间复杂性可用判定树的高度衡量。最大的比较次数是从根到叶的最长路径的长度。
12
8.1.3 RAM模型的变形与简化
6,代数计算树 ACT
以 x=(x1,x2,…,xn)为输入的一棵代数计算树 T是一棵二叉树，且：
(1)每个叶结点表示一个输出结果 YES或 NO。
(2)每个单儿子内部结点 (简单结点 )v表示下列形式运算指令：
op 或 op 或其中,和 分别是结点 v在树 T中的祖先结点 v1和 v2处得到的结果值，或是 x的分量； op∈{+,－，×,/}； c是一个常数。
(3)每个有 2个儿子的内部结点 (分支结点 )v,表示下列形式的测试指令：
>0或 ≥0 或 =0
其中,是结点 v在树 T中的祖先结点 v1处得到的结果值，或是
x的分量。
1vv ff? 2vf cfv? 1vf 1vv ff?
1vf 2vf
1vf 1vf 1vf
1vf
13
8.1.3 RAM模型的变形与简化
7,代数判定树 ADT(Algebraic Decision Tree)
在代数计算树 T中，若将所有的简单结点都压缩到其最近的子孙分支结点处，并将简单结点处的计算在压缩后的分支结点处同时完成，则计算结果可看作是输入 x的一个代数函数 fv(x)。
由此引出另一个称为代数判定树的计算模型。
代数判定树 T是一棵二叉树，且
(1)每个叶结点表示输出结果 YES或 NO。
(2)每个内部结点 v表示一个形如 fv(x1,x2,…,xn)∶0 的比较。其中,x=( x1,x2,…,xn)是输入,fv是一个代数函数。
14
8.1.4 图灵机
1,多带图灵机
15
8.1.4 图灵机
1,多带图灵机根据有限状态控制器的当前状态及每个读写头读到的带符号，
图灵机的一个计算步可实现下面 3个操作之一或全部。
(1)改变有限状态控制器中的状态。
(2)清除当前读写头下的方格中原有带符号并写上新的带符号。
(3)独立地将任何一个或所有读写头，向左移动一个方格 (L)或向右移动一个方格 (R)或停在当前单元不动 (S)。
k带图灵机可形式化地描述为一个 7元组 (Q,T,I,δ,b,q0，
qf),其中,
(1)Q是有限个状态的集合。 (2)T是有限个带符号的集合。
(3)I是输入符号的集合,I?T。 (4)b是惟一的空白符,b∈T -I。
(5)q0是初始状态 。 (6)qf是终止 (或接受 )状态 。
(7)δ 是移动函数。它是从 Q?Tk的某一子集映射到 Q? (T?{L,R，
S})k的函数。
16
8.1.4 图灵机
1,多带图灵机图灵机 M的时间复杂性 T(n)是它处理所有长度为 n的输入所需的最大计算步数。如果对某个长度为 n的输入，图灵机不停机，
T(n)对这个 n值无定义。
图灵机的空间复杂性 S(n)是它处理所有长度为 n的输入时，
在 k条带上所使用过的方格数的总和。如果某个读写头无限地向右移动而不停机,S(n)也无定义。
与 RAM模型类似，图灵机既可作为语言接受器，也可作为计算函数的装置。
17
8.1.5 图灵机模型与 RAM模型的关系图灵机模型与 RAM模型的关系是指同一问题在这 2种不同计算模型下的复杂性之间的关系。
定理 8-3 对于问题 P的任何长度为 n的输入，设求解问题 P
的算法 A在 k带图灵机模型 TM下的时间复杂性为,那么，算法 A在 RAM模型下的时间复杂性为 。
)(nT
))(( 2 nTO
定理 8-4 对于问题 P的任何长度为 n的输入，设求解问题 P
的算法 A在 RAM模型下，不含有乘法和除法指令，且按对数耗费标准其时间复杂性为,那么，算法 A在 k带图灵机模型 TM下的时间复杂性为 。
)(nT
))(( 2 nTO
18
8.1.6 问题变换与计算复杂性归约具体地说,假设有 2个问题 A和 B,将 问题 A变换为问题 B是指：
(1)将问题 A的输入变换为问题 B的适当输入 。
(2)解出问题 B。
(3)把问题 B的输出变换为问题 A的正确解 。
若用 O(τ(n)) 时间能完成上述变换的第 (1)步和第 (3)步,则称问题 A是 τ(n) 时间可变换到问题 B,且简记为 A∝ τ(n) B。 其中的 n通常为问题 A的规模 (大小 )。
当 τ(n) 为 n的多项式时，称问题 A可在多项式时间内变换为问题 B。
特别地，当 τ(n) 为 n的线性函数时，称问题 A可线性地变换为问题 B。
通过问题变换的技巧，可以将 2个不同问题的计算复杂性联系在一起。这样就可以将一个问题的计算复杂性归结为另一个问题的计算复杂性，从而实现问题的计算复杂性归约。
19
8.1.6 问题变换与计算复杂性归约命题 1(计算时间下界归约 )：若已知问题 A的计算时间下界为 T(n),且问题 A是 τ(n) 可变换到问题 B,即 A∝ τ(n) B,则
T(n)-O(τ(n)) 为问题 B的一个计算时间下界。
命题 2(计算时间上界归约 )：若已知问题 B的计算时间上界为 T(n),且问题 A是 τ(n) 可变换到问题 B,即 A∝ τ(n) B,则
T(n)+O(τ(n)) 是问题 A的一个计算时间上界。
问题的变换与问题的计算复杂性归约的关系,
在命题 1和命题 2中，当 τ(n)=o(T(n)) 时，问题 A的下界归约为问题 B的下界，问题 B的上界归约为问题 A的上界。
20
8.1.6 问题变换与计算复杂性归约通过问题变换获得问题的计算时间下界的例子,
(1)判别函数问题：给定 n个实数,计算其判别函数 。
nxxx,...,,21
ji ji xx )(
元素惟一性问题可以在 O(1)时间内变换为判别函数问题。
任何一个计算判别函数的算法，计算出判别函数值后，再作一次测试，判断其值是否为 0，即可得到元素惟一性问题的解。由命题 1即知，元素惟一性问题的计算时间下界 也是判别函数问题的一个计算时间下界。
)lo g( nn?
(2)最接近点对问题：给定平面上 n个点，找出这 n个点中距离最近的 2个点。
在元素惟一性问题中，将每一个实数,1≤ i≤n,变换为平面上的点 (,0),1≤ i≤n,则元素惟一性问题可以在线性时间内变换为最接近点对问题。
ix
ix
21
8.2 P类与 NP类问题
8.2.1 非确定性图灵机
8.2.2 P类与 NP类语言
8.2.3 多项式时间验证
22
8.2.1 非确定性图灵机非确定性图灵机 （ NDTM ）,一个 k带的非确定性图灵机 M是一个 7元组,(Q,T,I,δ,b,q0,qf)。 与确定性图灵机不同的是非确定性图灵机允许移动函数 δ 具有不确定性,即对于 Q?Tk中的每一个值 (q;x1,x2,…,xk),当它属于 δ 的定义域时,Q?(T?{L，
R,S})k中有惟一的一个 子集 δ(q;x 1,x2,…,xk)与之对应。可以在
δ(q;x 1,x2,…,xk)中随意选定一个值作为它的函数值。
在图灵机计算模型中，移动函数 δ 是单值的,即对于 Q?Tk中的每一个值，当它属于 δ 的定义域时,Q?(T?{L,R,S})k中只有惟一的值与之对应，称这种图灵机为 确定性图灵机,简记为
DTM(Deterministic Turing Machine)。
23
8.2.2 P类与 NP类语言
P类和 NP类语言的定义：
P={L|L是一个能在 多项式时间内 被一台 DTM所接受的语言 }
NP={L|L是一个能在 多项式时间 内被一台 NDTM所接受的语言 }
由于一台确定性图灵机可看作是非确定性图灵机的特例，所以可在多项式时间内被确定性图灵机接受的语言也可在多项式时间内被非确定性图灵机接受。故 P? NP。
24
8.2.2 P类与 NP类语言
NP类语言举例 —— 无向图的团问题 。
该问题的输入是一个有 n个顶点的无向图 G=(V,E)和一个整数 k。 要求判定图 G是否包含一个 k顶点的 完全子图 (团 )，即判定是否存在 V’?V,|V’|=k,且对于所有的
u,v∈V ’,有 (u,v)∈E 。
若用邻接矩阵表示图 G,用二进制串表示整数 k,则团问题的一个实例可以用长度为 的二进位串表示。因此，团问题可表示为语言：
CLIQUE={w#v|w,v∈{0,1}*,以 w为邻接矩阵的图 G有一个 k顶点的团，其中 v是 k的二进制表示。 }
1lo g2 kn
25
8.2.2 P类与 NP类语言接受该语言 CLIQUE的 非确定性算法,用非确定性选择指令选出包含 k个顶点的候选顶点子集 V,然后确定性地检查该子集是否是团问题的一个解。算法分为 3个阶段：
算法的第一阶段将输入串 w#v分解，并计算出 n=,以及用 v表示的整数 k。 若输入不具有形式 w#v或 |w|不是一个平方数就拒绝该输入。显而易见，第一阶段可 在时间内完成。
||w
)( 2nO
在算法的第二阶段中，非确定性地选择 V的一个 k元子集 V’?V。
算法的第三阶段是确定性地检查 V’的团性质。若 V’是一个团则接受输入，否则拒绝输入。这显然可以在 时间内完成。
因此，整个算法的时间复杂性为 。
)( 4nO
)( 4nO
非确定性算法在多项式时间内接受语言 CLIQUE,故 CLIQUE∈NP 。
26
8.2.3 多项式时间验证
VP={L|L∈∩*,∩ 为一有限字符集，存在一个多项式 p和一个多项式时间验证算法 A(X,Y)使得对任意 X∈∩*,X∈L 当且仅当存在 Y∈∩*,|Y|≤p(|X|) 且 A(X,Y)=1}。
多项式时间可验证语言类 VP可定义为：
定理 8-5,VP=NP。（ 证明见书本）
例如 (哈密顿回路问题 )：一个无向图 G含有哈密顿回路吗?
无向图 G的哈密顿回路是通过 G的每个顶点恰好一次的简单回路 。
可用语言 HAM-CYCLE 定义该问题如下：
HAM-CYCLE={G|G含有哈密顿回路 }
27
8.3 NP完全问题
8.3.1 多项式时间变换
8.3.2 Cook定理
28
8.3.1 多项式时间变换定义,语言 L是 NP完全的当且仅当
(1)L∈NP ；
(2)对于所有 L’∈NP 有 L’ ∝ p L。
如果有一个语言 L满足上述性质 (2)，但不一定满足性质 (1)，
则称该语言是 NP难 的。所有 NP完全语言构成的语言类称为 NP完全语言类,记为 NPC。
设,是 2个语言。所谓语言 能在多项式时间内变换为语言 (简记为 ∝ p )是指存在映身 f:,
且 f满足：
(1)有一个计算 f的多项式时间确定性图灵机；
(2)对于所有 x∈,x∈,当且仅当 f(x)∈ 。
*11L *22L 1L
2L 1
L
2L
*2*1
1L 2L*1?
29
8.3.1 多项式时间变换定理 8-6：设 L是 NP完全的，则
(1)L∈P 当且仅当 P＝ NP；
(2)若 L∝ p,且 ∈ NP,则 是 NP完全的。
1L 1L 1L
定理 8-6的 (2)可用来证明问题的 NP完全性。但前提是：
要有第一个 NP完全问题 L。
30
8.3.2 Cook定理定理 8-7(Cook定理 ),布尔表达式的可满足性问题 SAT是 NP完全的。
证明,SAT的一个实例是 k个布尔变量,…,的 m个布尔表达式,…,若存在各布尔变量 (1≤ i≤k) 的 0,1赋值，使每个布尔表达式 (1≤ i≤m) 都取值 1，则称布尔表达式 …
是可满足的。
1x kx
1A mA ix
1A 2A mAiA
SAT∈NP 是很明显的 。 对于任给的布尔变量,…,的 0，
1赋值,容易在多项式时间内验证相应的 … 的取值是否为 1。 因此,SAT∈NP 。
现在只要证明对任意的 L∈NP 有 L∝ pSAT即可 。
（ 详细证明见书本 P307～ 310）
1x kx
1A 2A mA
31
8.4 一些典型的 NP完全问题部分 NP完全问题树
32
8.4.1 合取范式的可满足性问题
（ CNF-SAT）
要证明 CNF-SAT∈NPC,只要证明在 Cook定理中定义的布尔表达式 A,…,G或者已是合取范式，或者有的虽然不是合取范式，
但可以用布尔代数中的变换方法将它们化成合取范式，而且合取范式的长度与原表达式的长度只差一个常数因子。
问题描述,给定一个合取范式 α,判定它是否可满足。
如果一个布尔表达式是一些因子和之积，则称之为合取范式，简称 CNF(Conjunctive Normal Form)。 这里的因子是变量或 。例如,就是一个合取范式，而 就不是合取范式。
x
x ))()(( 3213221 xxxxxxx
321 xxx?
33
8.4.2 3元合取范式的可满足性问题
（ 3-SAT）
证明思路：
3-SAT∈NP 是显而易见的。为了证明 3-SAT∈NPC,
只要证明 CNF-SAT∝ p 3-SAT,即合取范式的可满足性问题可在多项式时间内变换为 3-SAT。
问题描述,给定一个 3元 合取范式 α,判定它是否可满足。
34
8.4.3 团问题 CLIQUE
证明思路：
已经知道 CLIQUE∈NP 。 通过 3-SAT∝ pCLIQUE来证明 CLIQUE是 NP难的，从而证明团问题是 NP完全的。
问题描述,给定一个无向图 G=(V,E)和一个正整数 k,判定图 G是否包含一个 k团，即是否存在,V’?V，
|V’|=k,且对任意 u,w∈V ’有 (u,w)∈E 。
35
8.4.4 顶点覆盖问题
（ VERTEX-COVER）
证明思路：
首先,VERTEX-COVER∈NP 。 因为对于给定的图 G和正整数 k
以及一个,证书,V’,验证 |V’|=k,然后对每条边 (u,v)∈E,
检查是否有 u∈V ’或 v∈V ’,显然可在多项式时间内完成。
其次，通过 CLIQUE∝ pVERTEX-COVER来证明顶点覆盖问题是 NP难的。
问题描述,给定一个无向图 G=(V,E)和一个正整数 k,判定是否存在 V’?V,|V’|=k,使得对于任意 (u,v)∈E 有 u∈V ’或
v∈V ’。 如果存在这样的 V’,就称 V’为图 G的一个大小为 k顶点覆盖。
36
8.4.5 子集和问题
（ SUBSET-SUM）
问题描述,给定整数集合 S和一个整数 t,判定是否存在 S
的一个子集 S’?S,使得 S’中整数的和为 t。 例如，若 S={1,4，
16,64,256,1040,1041,1093,1284,1344}且 t=3754,则子集 S’={1,16,64,256,1040,1093,1284}是一个解。
证明思路：
首先，对于子集和问题的一个实例 <S,t>,给定一个,证书,S’,要验证 t= 是否成立，显然可在多项式时间内完成。因此,SUBSET-SUM∈NP ；
其次，证明 VERTEX-COVER∝ pSUBSET-SUM。
'Si i
37
8.4.6 哈密顿回路问题
（ HAM-CYCLE）
证明思路：
首先，已知哈密顿回路问题是一个 NP类问题。
其次，通过证明 3-SAT∝ pHAM-CYCLE，
得出,HAM-CYCLE∈NPC 。
问题描述,给定无向图 G=(V,E),判定其是否含有一哈密顿回路。
38
8.4.7 旅行售货员问题 TSP
首先，给定 TSP的一个实例 (G,c,k),和一个由 n个顶点组成的顶点序列。验证算法要验证这 n个顶点组成的序列是图 G
的一条回路，且经过每个顶点一次。另外，将每条边的费用加起来，并验证所得的和不超过 k。 这个过程显然可在多项式时间内完成，即 TSP∈NP 。
其次，旅行售货员问题与哈密顿回路问题有着密切的联系。
哈密顿回路问题可在多项式时间内变换为旅行售货员问题。即
HAM-CYCLE∝ pTSP。 从而，旅行售货员问题是 NP难的。
因此,TSP∈NPC 。
问题描述,给定一个无向完全图 G=(V,E)及定义在 V?V上的一个费用函数 c和一个整数 k,判定 G是否存在经过 V中各顶点恰好一次的回路，使得该回路的费用不超过 k。
第 8章 NP完全性理论
2
8.1 计算模型
8.1.1 随机存取机 RAM
8.1.2 随机存取存储程序机 RASP
8.1.3 RAM模型的变形与简化
8.1.4 图灵机
8.1.5 图灵机模型与 RAM模型的关系
8.1.6 问题变换与计算复杂性归约
3
8.1.1 随机存取机 RAM
1,RAM的结构
4
8.1.1 随机存取机 RAM
2,RAM程序一个 RAM程序定义了从输入带到输出带的一个映射。可以对这种映射关系作 2种不同的解释。
解释一：把 RAM程序看成是计算一个函数若一个 RAM程序 P总是从输入带前 n个方格中读入 n个整数
x1,x2,…,xn,并且在输出带的第一个方格上输出一个整数 y
后停机，那么就说程序 P计算了函数 f(x1,x2,…,xn)=y
解释二：把 RAM程序当作一个语言接受器。
将字符串 S=a1a2… an放在输入带上。在输入带的第一个方格中放入符号 a1,第二个方格中放入符号 a2,…,第 n个方格中放入符号 an。 然后在第 n+1个方格中放入 0，作为输入串的结束标志符。如果一个 RAM程序 P读了字符串 S及结束标志符 0后，在输出带的第一格输出一个 1并停机，就说程序 P接受字符串 S。
5
8.1.1 随机存取机 RAM
3,RAM程序的耗费标准标准一：均匀耗费标准在均匀耗费标准下，每条 RAM指令需要一个单位时间；每个寄存器占用一个单位空间。以后除特别注明,RAM程序的复杂性将按照均匀耗费标准衡量。
标准二：对数耗费标准对数耗费标准是基于这样的假定，即执行一条指令的耗费与以二进制表示的指令的操作数长度成比例。在 RAM计算模型下，
假定一个寄存器可存放一个任意大小的整数。因此若设 l(i)是整数 i所占的二进制位数，则
0
0
1
||l o g)(
i
iiil
6
8.1.2 随机存取存储程序机 RASP
1,RASP的结构
RASP的整体结构类似于 RAM,所不同的是 RASP的程序是存储在寄存器中的。每条 RASP指令占据 2个连续的寄存器。第一个寄存器存放操作码的编码，第二个寄存器存放地址。 RASP指令用整数进行编码。
2,RASP程序的复杂性不管是在均匀耗费标准下，还是在对数耗费标准下,RAM
程序和 RASP程序的复杂性只差一个常数因子。在一个计算模型下 T(n)时间内完成的输入 -输出映射可在另一个计算模型下模拟，并在 kT(n)时间内完成。其中 k是一个常数因子。空间复杂性的情况也是类似的。
7
8.1.3 RAM模型的变形与简化
1,实随机存取机 RRAM
在 RRAM模型下，一个存储单元可以存放一个实数。下列的各运算为基本运算且每个运算只耗费单位时间。
(1)算术运算 +，－，×，／。
(2)2个实数间的比较 (<,≤,=,≠,≥,>)。
(3)间接寻址 (整数地址 )。
(4)常见函数的计算，如三角函数，指数函数，
对数函数等。
优点：能够方便处理实数；
适合于用 FORTRAN,PASCAL等高级语言写的算法。
8
8.1.3 RAM模型的变形与简化
2,直线式程序对于许多问题，所设计的 RAM程序中的转移指令仅用于重复一组指令，而且重复的次数与问题的输入规模 n成比例。在这种情况下，可以用重复地写出相同指令组的方法来消除程序中的循环。
由此，对每一个固定的 n得到一个无循环的直线式程序。
经过对 RAM模型的简化，得到直线式程序的指令系统如下：
x←y+z
x←y -z
x←y*z
x←y/z
x←i
其中 x,y和 z是符号地址 (或变量 )，而 i是常数。
每条指令耗费一个单位时间。
9
8.1.3 RAM模型的变形与简化
3,位式计算直线式程序计算模型显然是基于均匀耗费标准的。在对数耗费标准下，使用另一个 RAM的简化计算模型，称之为位式计算
(Bitwise Computation)模型。
除了下列 2点外，该计算模型与直线式程序计算模型基本相同：
(1)假设所有变量取值 0或 1，即为位变量。
(2)所用的运算是逻辑运算而不是算术运算。
用 ∧ 代表与,∨ 代表或,?代表异或,?代表非。
在位式计算模型下，每个逻辑运算指令耗费一个单位时间。
10
8.1.3 RAM模型的变形与简化
4,位向量运算 (Bit Vector Operations)
若在直线式程序计算模型中，假设所有变量均为位向量，而且所用的运算均为位操作指令，则得到位向量运算计算模型。
例如，要表示一个有 100个顶点的图中从顶点 v到其余各顶点间有没有边相连，可以用 100位的一个位向量表示。若顶点 v到顶点 vj之间有边相连，则该位向量的第 j位为 1，否则为 0。
缺点,所需的机器字长要远大于其他模型。
11
8.1.3 RAM模型的变形与简化
5,判定树判定树是一棵二叉树。它的每个内结点表示一个形如 x∶y 的比较。指向该结点左儿子的边相应于 x≤y,标号为 ≤ 。指向该结点右儿子的边相应于 x>y,标号为 >。每一次比较耗费一个单位时间。下图是对 a,b,c三个数进行排序的一棵判定树。
在判定树模型下，
算法的时间复杂性可用判定树的高度衡量。最大的比较次数是从根到叶的最长路径的长度。
12
8.1.3 RAM模型的变形与简化
6,代数计算树 ACT
以 x=(x1,x2,…,xn)为输入的一棵代数计算树 T是一棵二叉树，且：
(1)每个叶结点表示一个输出结果 YES或 NO。
(2)每个单儿子内部结点 (简单结点 )v表示下列形式运算指令：
op 或 op 或其中,和 分别是结点 v在树 T中的祖先结点 v1和 v2处得到的结果值，或是 x的分量； op∈{+,－，×,/}； c是一个常数。
(3)每个有 2个儿子的内部结点 (分支结点 )v,表示下列形式的测试指令：
>0或 ≥0 或 =0
其中,是结点 v在树 T中的祖先结点 v1处得到的结果值，或是
x的分量。
1vv ff? 2vf cfv? 1vf 1vv ff?
1vf 2vf
1vf 1vf 1vf
1vf
13
8.1.3 RAM模型的变形与简化
7,代数判定树 ADT(Algebraic Decision Tree)
在代数计算树 T中，若将所有的简单结点都压缩到其最近的子孙分支结点处，并将简单结点处的计算在压缩后的分支结点处同时完成，则计算结果可看作是输入 x的一个代数函数 fv(x)。
由此引出另一个称为代数判定树的计算模型。
代数判定树 T是一棵二叉树，且
(1)每个叶结点表示输出结果 YES或 NO。
(2)每个内部结点 v表示一个形如 fv(x1,x2,…,xn)∶0 的比较。其中,x=( x1,x2,…,xn)是输入,fv是一个代数函数。
14
8.1.4 图灵机
1,多带图灵机
15
8.1.4 图灵机
1,多带图灵机根据有限状态控制器的当前状态及每个读写头读到的带符号，
图灵机的一个计算步可实现下面 3个操作之一或全部。
(1)改变有限状态控制器中的状态。
(2)清除当前读写头下的方格中原有带符号并写上新的带符号。
(3)独立地将任何一个或所有读写头，向左移动一个方格 (L)或向右移动一个方格 (R)或停在当前单元不动 (S)。
k带图灵机可形式化地描述为一个 7元组 (Q,T,I,δ,b,q0，
qf),其中,
(1)Q是有限个状态的集合。 (2)T是有限个带符号的集合。
(3)I是输入符号的集合,I?T。 (4)b是惟一的空白符,b∈T -I。
(5)q0是初始状态 。 (6)qf是终止 (或接受 )状态 。
(7)δ 是移动函数。它是从 Q?Tk的某一子集映射到 Q? (T?{L,R，
S})k的函数。
16
8.1.4 图灵机
1,多带图灵机图灵机 M的时间复杂性 T(n)是它处理所有长度为 n的输入所需的最大计算步数。如果对某个长度为 n的输入，图灵机不停机，
T(n)对这个 n值无定义。
图灵机的空间复杂性 S(n)是它处理所有长度为 n的输入时，
在 k条带上所使用过的方格数的总和。如果某个读写头无限地向右移动而不停机,S(n)也无定义。
与 RAM模型类似，图灵机既可作为语言接受器，也可作为计算函数的装置。
17
8.1.5 图灵机模型与 RAM模型的关系图灵机模型与 RAM模型的关系是指同一问题在这 2种不同计算模型下的复杂性之间的关系。
定理 8-3 对于问题 P的任何长度为 n的输入，设求解问题 P
的算法 A在 k带图灵机模型 TM下的时间复杂性为,那么，算法 A在 RAM模型下的时间复杂性为 。
)(nT
))(( 2 nTO
定理 8-4 对于问题 P的任何长度为 n的输入，设求解问题 P
的算法 A在 RAM模型下，不含有乘法和除法指令，且按对数耗费标准其时间复杂性为,那么，算法 A在 k带图灵机模型 TM下的时间复杂性为 。
)(nT
))(( 2 nTO
18
8.1.6 问题变换与计算复杂性归约具体地说,假设有 2个问题 A和 B,将 问题 A变换为问题 B是指：
(1)将问题 A的输入变换为问题 B的适当输入 。
(2)解出问题 B。
(3)把问题 B的输出变换为问题 A的正确解 。
若用 O(τ(n)) 时间能完成上述变换的第 (1)步和第 (3)步,则称问题 A是 τ(n) 时间可变换到问题 B,且简记为 A∝ τ(n) B。 其中的 n通常为问题 A的规模 (大小 )。
当 τ(n) 为 n的多项式时，称问题 A可在多项式时间内变换为问题 B。
特别地，当 τ(n) 为 n的线性函数时，称问题 A可线性地变换为问题 B。
通过问题变换的技巧，可以将 2个不同问题的计算复杂性联系在一起。这样就可以将一个问题的计算复杂性归结为另一个问题的计算复杂性，从而实现问题的计算复杂性归约。
19
8.1.6 问题变换与计算复杂性归约命题 1(计算时间下界归约 )：若已知问题 A的计算时间下界为 T(n),且问题 A是 τ(n) 可变换到问题 B,即 A∝ τ(n) B,则
T(n)-O(τ(n)) 为问题 B的一个计算时间下界。
命题 2(计算时间上界归约 )：若已知问题 B的计算时间上界为 T(n),且问题 A是 τ(n) 可变换到问题 B,即 A∝ τ(n) B,则
T(n)+O(τ(n)) 是问题 A的一个计算时间上界。
问题的变换与问题的计算复杂性归约的关系,
在命题 1和命题 2中，当 τ(n)=o(T(n)) 时，问题 A的下界归约为问题 B的下界，问题 B的上界归约为问题 A的上界。
20
8.1.6 问题变换与计算复杂性归约通过问题变换获得问题的计算时间下界的例子,
(1)判别函数问题：给定 n个实数,计算其判别函数 。
nxxx,...,,21
ji ji xx )(
元素惟一性问题可以在 O(1)时间内变换为判别函数问题。
任何一个计算判别函数的算法，计算出判别函数值后，再作一次测试，判断其值是否为 0，即可得到元素惟一性问题的解。由命题 1即知，元素惟一性问题的计算时间下界 也是判别函数问题的一个计算时间下界。
)lo g( nn?
(2)最接近点对问题：给定平面上 n个点，找出这 n个点中距离最近的 2个点。
在元素惟一性问题中，将每一个实数,1≤ i≤n,变换为平面上的点 (,0),1≤ i≤n,则元素惟一性问题可以在线性时间内变换为最接近点对问题。
ix
ix
21
8.2 P类与 NP类问题
8.2.1 非确定性图灵机
8.2.2 P类与 NP类语言
8.2.3 多项式时间验证
22
8.2.1 非确定性图灵机非确定性图灵机 （ NDTM ）,一个 k带的非确定性图灵机 M是一个 7元组,(Q,T,I,δ,b,q0,qf)。 与确定性图灵机不同的是非确定性图灵机允许移动函数 δ 具有不确定性,即对于 Q?Tk中的每一个值 (q;x1,x2,…,xk),当它属于 δ 的定义域时,Q?(T?{L，
R,S})k中有惟一的一个 子集 δ(q;x 1,x2,…,xk)与之对应。可以在
δ(q;x 1,x2,…,xk)中随意选定一个值作为它的函数值。
在图灵机计算模型中，移动函数 δ 是单值的,即对于 Q?Tk中的每一个值，当它属于 δ 的定义域时,Q?(T?{L,R,S})k中只有惟一的值与之对应，称这种图灵机为 确定性图灵机,简记为
DTM(Deterministic Turing Machine)。
23
8.2.2 P类与 NP类语言
P类和 NP类语言的定义：
P={L|L是一个能在 多项式时间内 被一台 DTM所接受的语言 }
NP={L|L是一个能在 多项式时间 内被一台 NDTM所接受的语言 }
由于一台确定性图灵机可看作是非确定性图灵机的特例，所以可在多项式时间内被确定性图灵机接受的语言也可在多项式时间内被非确定性图灵机接受。故 P? NP。
24
8.2.2 P类与 NP类语言
NP类语言举例 —— 无向图的团问题 。
该问题的输入是一个有 n个顶点的无向图 G=(V,E)和一个整数 k。 要求判定图 G是否包含一个 k顶点的 完全子图 (团 )，即判定是否存在 V’?V,|V’|=k,且对于所有的
u,v∈V ’,有 (u,v)∈E 。
若用邻接矩阵表示图 G,用二进制串表示整数 k,则团问题的一个实例可以用长度为 的二进位串表示。因此，团问题可表示为语言：
CLIQUE={w#v|w,v∈{0,1}*,以 w为邻接矩阵的图 G有一个 k顶点的团，其中 v是 k的二进制表示。 }
1lo g2 kn
25
8.2.2 P类与 NP类语言接受该语言 CLIQUE的 非确定性算法,用非确定性选择指令选出包含 k个顶点的候选顶点子集 V,然后确定性地检查该子集是否是团问题的一个解。算法分为 3个阶段：
算法的第一阶段将输入串 w#v分解，并计算出 n=,以及用 v表示的整数 k。 若输入不具有形式 w#v或 |w|不是一个平方数就拒绝该输入。显而易见，第一阶段可 在时间内完成。
||w
)( 2nO
在算法的第二阶段中，非确定性地选择 V的一个 k元子集 V’?V。
算法的第三阶段是确定性地检查 V’的团性质。若 V’是一个团则接受输入，否则拒绝输入。这显然可以在 时间内完成。
因此，整个算法的时间复杂性为 。
)( 4nO
)( 4nO
非确定性算法在多项式时间内接受语言 CLIQUE,故 CLIQUE∈NP 。
26
8.2.3 多项式时间验证
VP={L|L∈∩*,∩ 为一有限字符集，存在一个多项式 p和一个多项式时间验证算法 A(X,Y)使得对任意 X∈∩*,X∈L 当且仅当存在 Y∈∩*,|Y|≤p(|X|) 且 A(X,Y)=1}。
多项式时间可验证语言类 VP可定义为：
定理 8-5,VP=NP。（ 证明见书本）
例如 (哈密顿回路问题 )：一个无向图 G含有哈密顿回路吗?
无向图 G的哈密顿回路是通过 G的每个顶点恰好一次的简单回路 。
可用语言 HAM-CYCLE 定义该问题如下：
HAM-CYCLE={G|G含有哈密顿回路 }
27
8.3 NP完全问题
8.3.1 多项式时间变换
8.3.2 Cook定理
28
8.3.1 多项式时间变换定义,语言 L是 NP完全的当且仅当
(1)L∈NP ；
(2)对于所有 L’∈NP 有 L’ ∝ p L。
如果有一个语言 L满足上述性质 (2)，但不一定满足性质 (1)，
则称该语言是 NP难 的。所有 NP完全语言构成的语言类称为 NP完全语言类,记为 NPC。
设,是 2个语言。所谓语言 能在多项式时间内变换为语言 (简记为 ∝ p )是指存在映身 f:,
且 f满足：
(1)有一个计算 f的多项式时间确定性图灵机；
(2)对于所有 x∈,x∈,当且仅当 f(x)∈ 。
*11L *22L 1L
2L 1
L
2L
*2*1
1L 2L*1?
29
8.3.1 多项式时间变换定理 8-6：设 L是 NP完全的，则
(1)L∈P 当且仅当 P＝ NP；
(2)若 L∝ p,且 ∈ NP,则 是 NP完全的。
1L 1L 1L
定理 8-6的 (2)可用来证明问题的 NP完全性。但前提是：
要有第一个 NP完全问题 L。
30
8.3.2 Cook定理定理 8-7(Cook定理 ),布尔表达式的可满足性问题 SAT是 NP完全的。
证明,SAT的一个实例是 k个布尔变量,…,的 m个布尔表达式,…,若存在各布尔变量 (1≤ i≤k) 的 0,1赋值，使每个布尔表达式 (1≤ i≤m) 都取值 1，则称布尔表达式 …
是可满足的。
1x kx
1A mA ix
1A 2A mAiA
SAT∈NP 是很明显的 。 对于任给的布尔变量,…,的 0，
1赋值,容易在多项式时间内验证相应的 … 的取值是否为 1。 因此,SAT∈NP 。
现在只要证明对任意的 L∈NP 有 L∝ pSAT即可 。
（ 详细证明见书本 P307～ 310）
1x kx
1A 2A mA
31
8.4 一些典型的 NP完全问题部分 NP完全问题树
32
8.4.1 合取范式的可满足性问题
（ CNF-SAT）
要证明 CNF-SAT∈NPC,只要证明在 Cook定理中定义的布尔表达式 A,…,G或者已是合取范式，或者有的虽然不是合取范式，
但可以用布尔代数中的变换方法将它们化成合取范式，而且合取范式的长度与原表达式的长度只差一个常数因子。
问题描述,给定一个合取范式 α,判定它是否可满足。
如果一个布尔表达式是一些因子和之积，则称之为合取范式，简称 CNF(Conjunctive Normal Form)。 这里的因子是变量或 。例如,就是一个合取范式，而 就不是合取范式。
x
x ))()(( 3213221 xxxxxxx
321 xxx?
33
8.4.2 3元合取范式的可满足性问题
（ 3-SAT）
证明思路：
3-SAT∈NP 是显而易见的。为了证明 3-SAT∈NPC,
只要证明 CNF-SAT∝ p 3-SAT,即合取范式的可满足性问题可在多项式时间内变换为 3-SAT。
问题描述,给定一个 3元 合取范式 α,判定它是否可满足。
34
8.4.3 团问题 CLIQUE
证明思路：
已经知道 CLIQUE∈NP 。 通过 3-SAT∝ pCLIQUE来证明 CLIQUE是 NP难的，从而证明团问题是 NP完全的。
问题描述,给定一个无向图 G=(V,E)和一个正整数 k,判定图 G是否包含一个 k团，即是否存在,V’?V，
|V’|=k,且对任意 u,w∈V ’有 (u,w)∈E 。
35
8.4.4 顶点覆盖问题
（ VERTEX-COVER）
证明思路：
首先,VERTEX-COVER∈NP 。 因为对于给定的图 G和正整数 k
以及一个,证书,V’,验证 |V’|=k,然后对每条边 (u,v)∈E,
检查是否有 u∈V ’或 v∈V ’,显然可在多项式时间内完成。
其次，通过 CLIQUE∝ pVERTEX-COVER来证明顶点覆盖问题是 NP难的。
问题描述,给定一个无向图 G=(V,E)和一个正整数 k,判定是否存在 V’?V,|V’|=k,使得对于任意 (u,v)∈E 有 u∈V ’或
v∈V ’。 如果存在这样的 V’,就称 V’为图 G的一个大小为 k顶点覆盖。
36
8.4.5 子集和问题
（ SUBSET-SUM）
问题描述,给定整数集合 S和一个整数 t,判定是否存在 S
的一个子集 S’?S,使得 S’中整数的和为 t。 例如，若 S={1,4，
16,64,256,1040,1041,1093,1284,1344}且 t=3754,则子集 S’={1,16,64,256,1040,1093,1284}是一个解。
证明思路：
首先，对于子集和问题的一个实例 <S,t>,给定一个,证书,S’,要验证 t= 是否成立，显然可在多项式时间内完成。因此,SUBSET-SUM∈NP ；
其次，证明 VERTEX-COVER∝ pSUBSET-SUM。
'Si i
37
8.4.6 哈密顿回路问题
（ HAM-CYCLE）
证明思路：
首先，已知哈密顿回路问题是一个 NP类问题。
其次，通过证明 3-SAT∝ pHAM-CYCLE，
得出,HAM-CYCLE∈NPC 。
问题描述,给定无向图 G=(V,E),判定其是否含有一哈密顿回路。
38
8.4.7 旅行售货员问题 TSP
首先，给定 TSP的一个实例 (G,c,k),和一个由 n个顶点组成的顶点序列。验证算法要验证这 n个顶点组成的序列是图 G
的一条回路，且经过每个顶点一次。另外，将每条边的费用加起来，并验证所得的和不超过 k。 这个过程显然可在多项式时间内完成，即 TSP∈NP 。
其次，旅行售货员问题与哈密顿回路问题有着密切的联系。
哈密顿回路问题可在多项式时间内变换为旅行售货员问题。即
HAM-CYCLE∝ pTSP。 从而，旅行售货员问题是 NP难的。
因此,TSP∈NPC 。
问题描述,给定一个无向完全图 G=(V,E)及定义在 V?V上的一个费用函数 c和一个整数 k,判定 G是否存在经过 V中各顶点恰好一次的回路，使得该回路的费用不超过 k。
