2010-5-14 计算机算法设计与分析 1
第八章
NP完全性理论
2010-5-14 计算机算法设计与分析 2
随机存取机 RAM的构造
累加器指令
计数器 程序存储部件
内存储器
r0
r1
r2
…
只读输入带…
… 只写输出带
2010-5-14 计算机算法设计与分析 3
随机存取机 RAM的指令集
操作码 操作数 指令含义
⑴ LOAD =i / i / *i 取操作数入累加器
⑵ STORE i / *i 将累加器中数存入内存
⑶ ADD =i / i / *i 加法运算
⑷ SUB =i / i / *i 减法运算
⑸ MULT =i / i / *i 乘法运算
⑹ DIV =i / i / *i 除法运算
⑺ READ i / *i 读入
⑻ WRITE =i / i / *i 输出
⑼ JUMP 标号 无条件转移到标号语句
⑽ JGTZ 标号 正转移到标号语句
⑾ JZERO 标号 零转移到标号语句
⑿ HALT 停机
2010-5-14 计算机算法设计与分析 4
RAM机的复杂性标准
? 均匀耗费标准
? 对数耗费标准
每条 RAM指令需要一个单位时间，每个寄存器
占用一个单位空间。
RAM指令的执行时间与操作数的长度的对数成
比例，一个寄存器可放一个任意大小的整数。
? 若每个操作数不超过一个机器字，则用均匀耗
费标准是合理的，否则适用对数耗费标准。
2010-5-14 计算机算法设计与分析 5
随机存取存储程序机 RASP
? RASP与 RAM的区别在于 (1)RASP的程序存储
在内存并且可以修改自身； (2)RASP不允许间
接寻址，它通过修改指令模拟间接寻址。
? RASP的指令集见 P-238的表 8-6。
? RASP更加接近冯 ·诺伊曼体系结构。
? 无论是采用均匀耗费标准还是对数耗费标准，
在相差一个常数因子的意义下,RAM与 RASP
是等价的。
2010-5-14 计算机算法设计与分析 6
RAM的变形与简化
? (1)实随机存取机 RRAM；
? (2)直线式程序；
? (3)位式计算；
? (4)位向量计算；
? (5)判定数；
? (6)代数计算树 ACT；
? (7)代数判定树。
2010-5-14 计算机算法设计与分析 7
图林机的构造
? 图林机 (Turing Machine)是英国数学家 Turing在
1936年提出的计算模型，被认为是当今计算机
的理论模型。下面是图林机 (TM)原型的构造：
…… 输入带
有限
控制器
磁头 输入带被视为右无穷，并被划分为一个个
单元用于存放符号 (带符号 )。
有限控制器由有限个状态构成 。
磁头可左右移动，读写带符号。
2010-5-14 计算机算法设计与分析 8
TM的数学描述
? Q是有限状态的集合；
? T是有限个带符号的集合；
? I ? T,是输入符号的集合；
? δ,Q× T→Q × T× {L,R}为转移函数；
? b是唯一的空白符,b∈ T – I；
? q0和 qf分别为初始状态和终止状态。
M = (Q,T,I,δ,b,q0,qf )
其中：
2010-5-14 计算机算法设计与分析 9
图林机的变形
? 多道图林机 (输入带上有多个道 )。
? 双向图林机 (输入带被视为左右均是无穷的 )。
? 多带图林机 (具有多条输入带 )。
? 多头图林机 (具有多个磁头 )。
? 多维图林机 (输入带是多维的 )。
? 不确定的图林机 (有限控制器是不确定的 )。
不确定的图林机类似于不确定的自动机，即
δ,Q× T→ ρ(Q× T× {L,R})
将图林机是原型称为确定的，记为 DTM； 而
将不确定的图林机记为 NDTM，
? 已经证明各类变形图林机在可计算的能力上等
价于原型图林机。但是在复杂性是有区别的。
2010-5-14 计算机算法设计与分析 10
通用图林机
? 不失一般性，任何图林机的 T = {0,1}；
? δ,Q× T→Q × T× {L,R}的每个动作由五个部
分构成 (五字诀 ),δ含有有限个五字诀。
? 于是，任一图林机都可写成一个二进制编码。
? 所以任一图林机可用一个三带图林机来模拟。
? 这个三带图林机就被称为通用图林机。
输入带
编码带
工作带
有限
控制器 code1#code2#…#code n
qi
通用图林机将某个图林机 Mi的编码存储在编码
带上；工作带上初始时为初始状态 q0； 然后依
据状态及现行扫描的符号选择并执行编码。
2010-5-14 计算机算法设计与分析 11
用 RAM模拟 TM
? 定理 8-3：设算法 A,对于任何长度为 n的输入，
在图林机 TM下的时间复杂性为 T(n),则 A在
RAM下的时间复杂性为 O(T2(n))。
? 证明：每个寄存器放输入带一个单元的内容，
这样 RAM就可以模拟 TM的工作。
? 均匀耗费标准下，模拟 TM一个动作,RAM需
常数时间。 A在 RAM下时间复杂性为 O(T(n))。
? 对数耗费标准下,RAM模拟 TM的时间复杂性
为 O(T(n)logT(n)) =O(T2(n))。 。
2010-5-14 计算机算法设计与分析 12
用 TM模拟 RAM
? 定理 8-4：设算法 A,对于任何长度为 n的输入，
按对数耗费标准在 RAM下的时间复杂性为 T(n)，
则 A在 TM下的时间复杂性为 O(T2(n))。
? 证明：用一个五带 TM模拟 RAM的工作，
其中：
带 1用 <地址,内容 >的形式存放寄存器；
带 2存放累加器内容；带 3作为暂存工作带；
带 4和带 5作为输入带和输出带；
用 TM的状态对应 RAM的一步程序。
? TM模拟 RAM除乘 /除法外的指令的时间为常数，
查找寄存器的时间为 n,整个时间为 O(T2(n))。
? 对 RAM的乘除法,TM用加减法模拟的耗费不
会超过乘除法耗费的平方。
2010-5-14 计算机算法设计与分析 13
TM模型与 RAM模型的关系
? 定理 8-5：在对数耗费标准下，对于同一个算法，
采用 RAM模型和 TM模型的时间复杂性是多项
式相关的。对空间复杂性亦如此。
? 注意在均匀耗费标准下这个关系不成立。 TM
模拟 RAM的时间复杂性可能是指数的关系。
? 因为 TM模型比较原始，所以在大多数情况下
采用 RAM模型。
? 若算法在 RAM模型下的复杂性为多项式，则也
就认为其在 TM模型下的复杂性为多项式。
2010-5-14 计算机算法设计与分析 14
可计算性问题的层次
? 若某问题存在求解的算法，则称其为可计算的；
若不存在算法但是存在求解的过程，则称其为
半可计算的；若连过程也不存在，则称其为完
全不可计算的。
完全不可计算 半可计算
可计算
? 可计算的问题的集合称为递归集；半可计算的
称为递归可枚举集；完全不可计算的称为非递
归可枚举集。
? 可计算的问题的计算复杂性是不是都相同呢？
2010-5-14 计算机算法设计与分析 15
求解与验证
? 人们通常认为，求解一个问题要比验证一个问
题困难些。
? 但是也并非完全如此。例如 TSP问题。要验证
一条周游路线是否最小和求一条最小周游路线
实际上是一样的难。
? 希望能按计算的难度将问题分为两类：
? P类问题：多项式时间计算的问题。
? NP类问题：非多项式时间计算的问题 。
2010-5-14 计算机算法设计与分析 16
确定的图林机与不确定图林机
? NDTM是一种并行的工作方式，它可以用交叉
串行的确定方式来模拟。因此任何 NDTM都可
以用 DTM来模拟实现，但其复杂性却不相同。
? 对于一台复杂性为 T(n)的 NDTM,可用一台复
杂性为 O(CT(n))的 DTM来模拟，这里 C为常数。
? 实际上可以将 NDTM的运行方式看作并行的，
而 DTM是串行的。并行运行可用串行来模拟，
但并行的效率要高于串行的效率。
? 而现行计算机的运行方式本质是确定的。
2010-5-14 计算机算法设计与分析 17
P类与 NP类语言 /问题
? P = {L | L在多项式时间被 DTM接受 }
? NP = {L | L在多项式时间被 NDTM接受 }
? 这里也可用 RAM等其它的机器模型来定义。但
它们都是等价的。
若 Q∈ NP,则可以用一个 DTM来模拟接受 Q的
NDTM,所需要时间复杂性为 O(CT(n))。
? 这使人们认为 NP类问题要比 P类问题更难。
真的如此吗？? 显然，因为 DTM?NDTM,所以 P?NP。? 是否有 P≠NP？ 即是否有 Q?NP,且 Q?P？这是个尚未解决的问题。
2010-5-14 计算机算法设计与分析 18
问题的变换及时间等价性
? 若问题 A的求解能够变换成问题 B的求解且变
换的时间为 O(τ(n)),则称 A是 τ(n)时间变换为 B，
简记为 A∝ τ(n)B,其中 n为问题 A的规模。
? 若 A∝ τ(n)B,当 τ(n)为多项式时，称 A可多项式
归结为问题 B,记为 A∝ B 。
? 一般来说，可变换性不是对称的。
? 若 A∝ τ(n)B且 B∝ τ(n)A,则称 A和 B是 τ(n)时间
等价的。特别当 τ(n)为线性时，称 A和 B等价。
这时 A和 B具有相同的时间复杂性。
2010-5-14 计算机算法设计与分析 19
计算复杂性的归约
? 若 A∝ τ(n)B,设 A和 B的计算时间分别为 TA(n)
和 TB(n)，则 TA(n) = τ(n) + TB(n)
? 命题 1 (计算时间下界归约 ),若 TA(n)为 A的计
算时间下界, 则 B的计算时间 TB(n)的下界为：
Ω(TB(n)) = TA(n) – O(τ(n))
? 命题 1 (计算时间上界归约 ),若 TB(n)为 B的计
算时间上界, 则 A的计算时间 TA(n)的上界为：
O(TA(n)) = TB(n) + O(τ(n))
2010-5-14 计算机算法设计与分析 20
多项式归结与 NP困难
? 多项式归结显然有如下两个性质：
? (1) A∝ B且 B∈ P,则 A∈ P。
? (2) 若 A∝ B且 B∝ C,则 A∝ C。
? 定义：对于问题 Q,如果任意问题 Qi∈ NP,都
有 Qi∝ Q,则称问题 Q是 NP困难的 。
? 所谓 NP困难的问题，是指该问题不会比 NP中
的任何问题容易，至少是同样难或更难。
2010-5-14 计算机算法设计与分析 21
NP完全性
? 定义：对于问题 Q,若满足 Q∈ NP且 Q是 NP困
难的，则称 Q是 NP完全的 。
? 所有 NP完全的问题记为 NPC。
? 定理：设 Q∈ NPC,P=NP当且仅当 Q∈ P。
? 如果 P≠NP,则 P,NP与 NPC或许如下图所示：
NPP NPC
2010-5-14 计算机算法设计与分析 22
第一个 NP完全的问题
? Cook在 1971年证明了第一个 NP完全的问题。
? Cook定理：布尔表达式的可满足性 SAT是 NP完
全的。
所谓可满足性 SAT是这样的问题：给定 k个布尔
变量 x1,…x k的 m个布尔表达式 A1,…,A m,若存
在对各个布尔变量 xi的 0,1赋值，使得每个布尔
表达式 Ai都为真，则称布尔表达式 A1,…,A m是
可满足的。
Cook定理的证明由两个部分构成，第一部分是
SAT∈ NP,这基本是显然的。第二部分是任意
L∈ NP,可在多项式时间内转换为 SAT问题。这
是一个构造证明，即将接受 L的 NDTM的瞬象序
列转换为一个 SAT问题。
? 自从 Cook证明了第一个 NP完全的问题后，迄
今为止，已经发现了至少有 300多个 NP完全的
问题，但尚未证明其中任何一个是属于 P的。
? 这一事实，增强了人们对 P≠NP的猜测。但遗
憾的是，这个猜测迄今仍然还只是个猜测。
2010-5-14 计算机算法设计与分析 23
若干 NP完全问题
? 合取范式的可满足性问题 CNF-SAT
? 三元合取范式的可满足性 3-SAT
? 团问题 CLIQUE
? 顶点覆盖问题 VERTEX-COVER
? 子集和问题 SUBST-SUM
? 哈密顿回路问题 HAM-CYCLE
? 旅行售货员问题 TSP
第八章
NP完全性理论
2010-5-14 计算机算法设计与分析 2
随机存取机 RAM的构造
累加器指令
计数器 程序存储部件
内存储器
r0
r1
r2
…
只读输入带…
… 只写输出带
2010-5-14 计算机算法设计与分析 3
随机存取机 RAM的指令集
操作码 操作数 指令含义
⑴ LOAD =i / i / *i 取操作数入累加器
⑵ STORE i / *i 将累加器中数存入内存
⑶ ADD =i / i / *i 加法运算
⑷ SUB =i / i / *i 减法运算
⑸ MULT =i / i / *i 乘法运算
⑹ DIV =i / i / *i 除法运算
⑺ READ i / *i 读入
⑻ WRITE =i / i / *i 输出
⑼ JUMP 标号 无条件转移到标号语句
⑽ JGTZ 标号 正转移到标号语句
⑾ JZERO 标号 零转移到标号语句
⑿ HALT 停机
2010-5-14 计算机算法设计与分析 4
RAM机的复杂性标准
? 均匀耗费标准
? 对数耗费标准
每条 RAM指令需要一个单位时间，每个寄存器
占用一个单位空间。
RAM指令的执行时间与操作数的长度的对数成
比例，一个寄存器可放一个任意大小的整数。
? 若每个操作数不超过一个机器字，则用均匀耗
费标准是合理的，否则适用对数耗费标准。
2010-5-14 计算机算法设计与分析 5
随机存取存储程序机 RASP
? RASP与 RAM的区别在于 (1)RASP的程序存储
在内存并且可以修改自身； (2)RASP不允许间
接寻址，它通过修改指令模拟间接寻址。
? RASP的指令集见 P-238的表 8-6。
? RASP更加接近冯 ·诺伊曼体系结构。
? 无论是采用均匀耗费标准还是对数耗费标准，
在相差一个常数因子的意义下,RAM与 RASP
是等价的。
2010-5-14 计算机算法设计与分析 6
RAM的变形与简化
? (1)实随机存取机 RRAM；
? (2)直线式程序；
? (3)位式计算；
? (4)位向量计算；
? (5)判定数；
? (6)代数计算树 ACT；
? (7)代数判定树。
2010-5-14 计算机算法设计与分析 7
图林机的构造
? 图林机 (Turing Machine)是英国数学家 Turing在
1936年提出的计算模型，被认为是当今计算机
的理论模型。下面是图林机 (TM)原型的构造：
…… 输入带
有限
控制器
磁头 输入带被视为右无穷，并被划分为一个个
单元用于存放符号 (带符号 )。
有限控制器由有限个状态构成 。
磁头可左右移动，读写带符号。
2010-5-14 计算机算法设计与分析 8
TM的数学描述
? Q是有限状态的集合；
? T是有限个带符号的集合；
? I ? T,是输入符号的集合；
? δ,Q× T→Q × T× {L,R}为转移函数；
? b是唯一的空白符,b∈ T – I；
? q0和 qf分别为初始状态和终止状态。
M = (Q,T,I,δ,b,q0,qf )
其中：
2010-5-14 计算机算法设计与分析 9
图林机的变形
? 多道图林机 (输入带上有多个道 )。
? 双向图林机 (输入带被视为左右均是无穷的 )。
? 多带图林机 (具有多条输入带 )。
? 多头图林机 (具有多个磁头 )。
? 多维图林机 (输入带是多维的 )。
? 不确定的图林机 (有限控制器是不确定的 )。
不确定的图林机类似于不确定的自动机，即
δ,Q× T→ ρ(Q× T× {L,R})
将图林机是原型称为确定的，记为 DTM； 而
将不确定的图林机记为 NDTM，
? 已经证明各类变形图林机在可计算的能力上等
价于原型图林机。但是在复杂性是有区别的。
2010-5-14 计算机算法设计与分析 10
通用图林机
? 不失一般性，任何图林机的 T = {0,1}；
? δ,Q× T→Q × T× {L,R}的每个动作由五个部
分构成 (五字诀 ),δ含有有限个五字诀。
? 于是，任一图林机都可写成一个二进制编码。
? 所以任一图林机可用一个三带图林机来模拟。
? 这个三带图林机就被称为通用图林机。
输入带
编码带
工作带
有限
控制器 code1#code2#…#code n
qi
通用图林机将某个图林机 Mi的编码存储在编码
带上；工作带上初始时为初始状态 q0； 然后依
据状态及现行扫描的符号选择并执行编码。
2010-5-14 计算机算法设计与分析 11
用 RAM模拟 TM
? 定理 8-3：设算法 A,对于任何长度为 n的输入，
在图林机 TM下的时间复杂性为 T(n),则 A在
RAM下的时间复杂性为 O(T2(n))。
? 证明：每个寄存器放输入带一个单元的内容，
这样 RAM就可以模拟 TM的工作。
? 均匀耗费标准下，模拟 TM一个动作,RAM需
常数时间。 A在 RAM下时间复杂性为 O(T(n))。
? 对数耗费标准下,RAM模拟 TM的时间复杂性
为 O(T(n)logT(n)) =O(T2(n))。 。
2010-5-14 计算机算法设计与分析 12
用 TM模拟 RAM
? 定理 8-4：设算法 A,对于任何长度为 n的输入，
按对数耗费标准在 RAM下的时间复杂性为 T(n)，
则 A在 TM下的时间复杂性为 O(T2(n))。
? 证明：用一个五带 TM模拟 RAM的工作，
其中：
带 1用 <地址,内容 >的形式存放寄存器；
带 2存放累加器内容；带 3作为暂存工作带；
带 4和带 5作为输入带和输出带；
用 TM的状态对应 RAM的一步程序。
? TM模拟 RAM除乘 /除法外的指令的时间为常数，
查找寄存器的时间为 n,整个时间为 O(T2(n))。
? 对 RAM的乘除法,TM用加减法模拟的耗费不
会超过乘除法耗费的平方。
2010-5-14 计算机算法设计与分析 13
TM模型与 RAM模型的关系
? 定理 8-5：在对数耗费标准下，对于同一个算法，
采用 RAM模型和 TM模型的时间复杂性是多项
式相关的。对空间复杂性亦如此。
? 注意在均匀耗费标准下这个关系不成立。 TM
模拟 RAM的时间复杂性可能是指数的关系。
? 因为 TM模型比较原始，所以在大多数情况下
采用 RAM模型。
? 若算法在 RAM模型下的复杂性为多项式，则也
就认为其在 TM模型下的复杂性为多项式。
2010-5-14 计算机算法设计与分析 14
可计算性问题的层次
? 若某问题存在求解的算法，则称其为可计算的；
若不存在算法但是存在求解的过程，则称其为
半可计算的；若连过程也不存在，则称其为完
全不可计算的。
完全不可计算 半可计算
可计算
? 可计算的问题的集合称为递归集；半可计算的
称为递归可枚举集；完全不可计算的称为非递
归可枚举集。
? 可计算的问题的计算复杂性是不是都相同呢？
2010-5-14 计算机算法设计与分析 15
求解与验证
? 人们通常认为，求解一个问题要比验证一个问
题困难些。
? 但是也并非完全如此。例如 TSP问题。要验证
一条周游路线是否最小和求一条最小周游路线
实际上是一样的难。
? 希望能按计算的难度将问题分为两类：
? P类问题：多项式时间计算的问题。
? NP类问题：非多项式时间计算的问题 。
2010-5-14 计算机算法设计与分析 16
确定的图林机与不确定图林机
? NDTM是一种并行的工作方式，它可以用交叉
串行的确定方式来模拟。因此任何 NDTM都可
以用 DTM来模拟实现，但其复杂性却不相同。
? 对于一台复杂性为 T(n)的 NDTM,可用一台复
杂性为 O(CT(n))的 DTM来模拟，这里 C为常数。
? 实际上可以将 NDTM的运行方式看作并行的，
而 DTM是串行的。并行运行可用串行来模拟，
但并行的效率要高于串行的效率。
? 而现行计算机的运行方式本质是确定的。
2010-5-14 计算机算法设计与分析 17
P类与 NP类语言 /问题
? P = {L | L在多项式时间被 DTM接受 }
? NP = {L | L在多项式时间被 NDTM接受 }
? 这里也可用 RAM等其它的机器模型来定义。但
它们都是等价的。
若 Q∈ NP,则可以用一个 DTM来模拟接受 Q的
NDTM,所需要时间复杂性为 O(CT(n))。
? 这使人们认为 NP类问题要比 P类问题更难。
真的如此吗？? 显然，因为 DTM?NDTM,所以 P?NP。? 是否有 P≠NP？ 即是否有 Q?NP,且 Q?P？这是个尚未解决的问题。
2010-5-14 计算机算法设计与分析 18
问题的变换及时间等价性
? 若问题 A的求解能够变换成问题 B的求解且变
换的时间为 O(τ(n)),则称 A是 τ(n)时间变换为 B，
简记为 A∝ τ(n)B,其中 n为问题 A的规模。
? 若 A∝ τ(n)B,当 τ(n)为多项式时，称 A可多项式
归结为问题 B,记为 A∝ B 。
? 一般来说，可变换性不是对称的。
? 若 A∝ τ(n)B且 B∝ τ(n)A,则称 A和 B是 τ(n)时间
等价的。特别当 τ(n)为线性时，称 A和 B等价。
这时 A和 B具有相同的时间复杂性。
2010-5-14 计算机算法设计与分析 19
计算复杂性的归约
? 若 A∝ τ(n)B,设 A和 B的计算时间分别为 TA(n)
和 TB(n)，则 TA(n) = τ(n) + TB(n)
? 命题 1 (计算时间下界归约 ),若 TA(n)为 A的计
算时间下界, 则 B的计算时间 TB(n)的下界为：
Ω(TB(n)) = TA(n) – O(τ(n))
? 命题 1 (计算时间上界归约 ),若 TB(n)为 B的计
算时间上界, 则 A的计算时间 TA(n)的上界为：
O(TA(n)) = TB(n) + O(τ(n))
2010-5-14 计算机算法设计与分析 20
多项式归结与 NP困难
? 多项式归结显然有如下两个性质：
? (1) A∝ B且 B∈ P,则 A∈ P。
? (2) 若 A∝ B且 B∝ C,则 A∝ C。
? 定义：对于问题 Q,如果任意问题 Qi∈ NP,都
有 Qi∝ Q,则称问题 Q是 NP困难的 。
? 所谓 NP困难的问题，是指该问题不会比 NP中
的任何问题容易，至少是同样难或更难。
2010-5-14 计算机算法设计与分析 21
NP完全性
? 定义：对于问题 Q,若满足 Q∈ NP且 Q是 NP困
难的，则称 Q是 NP完全的 。
? 所有 NP完全的问题记为 NPC。
? 定理：设 Q∈ NPC,P=NP当且仅当 Q∈ P。
? 如果 P≠NP,则 P,NP与 NPC或许如下图所示：
NPP NPC
2010-5-14 计算机算法设计与分析 22
第一个 NP完全的问题
? Cook在 1971年证明了第一个 NP完全的问题。
? Cook定理：布尔表达式的可满足性 SAT是 NP完
全的。
所谓可满足性 SAT是这样的问题：给定 k个布尔
变量 x1,…x k的 m个布尔表达式 A1,…,A m,若存
在对各个布尔变量 xi的 0,1赋值，使得每个布尔
表达式 Ai都为真，则称布尔表达式 A1,…,A m是
可满足的。
Cook定理的证明由两个部分构成，第一部分是
SAT∈ NP,这基本是显然的。第二部分是任意
L∈ NP,可在多项式时间内转换为 SAT问题。这
是一个构造证明，即将接受 L的 NDTM的瞬象序
列转换为一个 SAT问题。
? 自从 Cook证明了第一个 NP完全的问题后，迄
今为止，已经发现了至少有 300多个 NP完全的
问题，但尚未证明其中任何一个是属于 P的。
? 这一事实，增强了人们对 P≠NP的猜测。但遗
憾的是，这个猜测迄今仍然还只是个猜测。
2010-5-14 计算机算法设计与分析 23
若干 NP完全问题
? 合取范式的可满足性问题 CNF-SAT
? 三元合取范式的可满足性 3-SAT
? 团问题 CLIQUE
? 顶点覆盖问题 VERTEX-COVER
? 子集和问题 SUBST-SUM
? 哈密顿回路问题 HAM-CYCLE
? 旅行售货员问题 TSP
