第九章NP完全性理论与近似算法PPT课件

已不将经确图证定林明的机各图是类林原变机型形类称图似为林于确机不定在确的可定，计的记算自为的动DT能机M力，；上即而等 价将于不原确型定δ：图的Q林图×机林T。机→但记ρ(是为Q×在NDT复×T杂M{L性，, 是R}有) 区别的。
• 注意在均匀耗费标准下这个关系不成立。TM 模拟RAM的时间复杂性可能是指数的关系。
三种机器在计算能力上是等价的，差别在于计算速度不同
2020/11/27
计算机算法设计与分析
14
图林机的变形
• 多道图林机(输入带上有多个道)。 • 双向图林机 (输入带被视为左右均是无穷的)。 • 多带图林机(具有多条输入带)。 • 多头图林机 (具有多个磁头)。 • 多维图林机(输入带是多维的)。 • 不确定的图林机(有限控制器是不确定的)。
1. 改变有限状态控制器的状态 2. 清除读写头下方的原有符号，并写上新的
符号
3. 读写头向左或者向右移动一个方格，或不 动
202Байду номын сангаас/11/27
计算机算法设计与分析
10
TM的数学描述
M = (Q, T, I, δ, b, q0, qf ) 其中：
• Q是有限状态的集合； • T是有限个带符号的集合； • I T，是输入符号的集合； • δ：Q×Tk→Q×(T×{L,R,S})k为转移函数； • b是唯一的空白符，b∈T – I； • q0和qf分别为初始状态和终止状态。
2020/11/27
计算机算法设计与分析
11
δ的进一步说明
• δ操作可以表示为δ(q,a1,…ak)=(q’,(a1’,d1),…,(ak’,dk)) • 当图灵机处于状态q且对一切i，1<=i<=k，第i条带的
读写头扫描着的当前方格中的符号为ai时，图灵机就 按这个δ操作进行工作：
1. q变为q’ 2. a变为a’ 3. 左移或者右移
标号
零转移到标号语句
停机
计算机算法设计与分析
5
RAM机的复杂性标准
• 均匀耗费标准
每条RAM指令需要一个单位时间，每个寄存器 占用一个单位空间。 • 对数耗费标准
RAM指令的执行时间与操作数的长度的对数(l(i)) 成比例，一个寄存器可放一个任意大小的整数。
若每个操作数不超过一个机器字，则用均匀耗 费标准是合理的，否则适用对数耗费标准。
2020/11/27
计算机算法设计与分析
3
随机存取机RAM (Random Access Machine)的构造
… 只读输入带
指令 计数器
程序存储部件
r0 r1 r2
…
累加器
内存储器
… 只写输出带
2020/11/27
计算机算法设计与分析
4
随机存取机RAM的指令集
操作码 ⑴LOAD ⑵STORE ⑶ADD ⑷SUB ⑸MULT ⑹DIV ⑺READ ⑻WRITE ⑼JUMP ⑽JGTZ ⑾JZERO ⑿HALT
2020/11/27
计算机算法设计与分析
6
随机存取存储程序机RASP
(Random Access Stored Program Machine)
• RASP与RAM的区别在于(1)RASP的程序存储 在内存并且可以修改自身；(2)RASP不允许间 接寻址，它通过修改指令模拟间接寻址。
• RASP的指令集见表9-4。
• 如果对于某个长度为n的输入，图灵机不停机，T(n)对这个n值无 定义。
• 例：4整除问题：构造一个图灵机，判断输入的二进制串是否能 被4整除。
2020/11/27
计算机算法设计与分析
13
RAM与TM
• 由定理可知：
– 可用RAM来模拟TM – 也可用TM来模拟RAM
• 定理（补）：在对数耗费标准下，对于同一个 算法，采用RAM模型和TM模型的时间复杂性 是多项式相关的。对空间复杂性亦如此。
• 定理 不论在均匀耗费标准下还是在对数耗费标准下， 对每一个时间复杂性为T(n)的RASP程序，都有一个时 间复杂性为kT(n)的RAM程序与之等价，k为常数。
2020/11/27
计算机算法设计与分析
8
图林机(Turing Machine)的构造
• 图林机(Turing Machine)是英国数学家Turing在 1936年提出的计算模型，被认为是当今计算机 的理论模型。下面是图林机(TM)原型的构造：
2020/11/27
操作数
指令含义
=i / i / *i
取操作数入累加器
i / *i
将累加器中数存入内存
=i / i / *i
加法运算
=i / i / *i
减法运算
=i / i / *i
乘法运算
=i / i / *i
除法运算
i / *i
读入
=i / i / *i
输出
标号
无条件转移到标号语句
标号
正转移到标号语句
2020/11/27
计算机算法设计与分析
12
图灵机的语言
• 当 进且入仅终当止从状指态q定f时的，初称始图状灵态机q0接开受始这，个经输过入一符系号列串计。算步后，最终 • 所有这台图灵机能接受的输入符号串的集合就是这台图灵机识别
的一个语言。
• 图灵机也可作为计算函数的装置。函数的自变量可编码成一字符 串输入到一条输入带上，用一特殊符号＃隔开。若图灵机经过有 限步后，在一条指定的带上输出整数y并停机，则可以说图灵机 计算出了f(x)=y。
…… 输入带
磁头
有限 控制器
输入带被视为右无穷，并被划分为一个个 单元用于存放符号(带符号)。 有限控制器由有限个状态构成。
磁头可左右移动，读写带符号。
2020/11/27
计算机算法设计与分析
9
图灵机的操作
• 根据有限状态控制器的当前状态及每 个读写头读到的带符号，图灵机的一 个计算步可实现下面三个操作之一或 全部。
• RASP更加接近冯·诺伊曼体系结构。
• 无论是采用均匀耗费标准还是对数耗费标准， 在相差一个常数因子的意义下，RAM与RASP 是等价的。
2020/11/27
计算机算法设计与分析
7
RAM与RASP是等价的
• 定理 不论在均匀耗费标准下还是在对数耗费标准下， 对时间复杂性为T(n)的任一RAM程序，都存在一个时 间复杂性为kT(n)的RASP程序与之等价，k为常数。
第九章
NP完全性理论
2020/11/27
计算机算法设计与分析
1
难？易？
• 可在多项式时间内解决的问题看作是 “易”解问题。
• 将需要指数函数时间解决的问题看作是 “难”问题。
• 这里所说的时间是针对问题规模n的多项 式还是指数函数。
2020/11/27
计算机算法设计与分析
2
内容
• 两部分：
– 三种机器（RAM, RASP, TM） – NP完全理论