清华大学出版社 TSINGHUA UNIVERSITY PRESS 第8章NP完全性理论
1 第8章 NP完全性理论
清华大学出版社 TSINGHUA UNIVERSITY PRESS 8.1计算模型 8.1.1随机存取机RAM ·8.1.2随机存取存储程序机RASP ·8.1.3RAM模型的变形与简化 8.1.4图灵机 ·8.1.5图灵机模型与RAM模型的关系 ·8.1.6问题变换与计算复杂性归约 2
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 问题变换与计算复杂性归约
清华大学出版社 TSINGHUA UNIVERSITY PRESS 81.1随机存取机RAM 1.RAM的结构 x1x2·xn二只读输入带 累加器 指令计数器 程序存储部件 内存储器 「y1|y2|- 只写输出带
3 8.1.1 随机存取机RAM 1. RAM的结构
清华大学出版社 TSINGHUA UNIVERSITY PRESS 8.1.1随机存取机RAM 2.RAM程序 △个RAM程序定义了从输入带到输出带的一个映射。可以对 这种映射关系作2种不同的解释。 解释一:把RAM程序看成是计算一个函数 若一个RAM程序P总是从输入带前n个方格中读入n个整数 X1X ,Xn,并且在输出带的第一个方格上输出一个整数 后停机,那么就说程序P计算了函数f(X1,X2 X 解释二:把RAM程序当作一个语言接受器。 将字符串S=a1a2an放在输入带上。在输入带的第一个方 格中放入符号a1,第二个方格中放入符号a2,…,第n个方格中 放入符号an。然后在第n+1个方格中放入0,作为输入串的结束标 志符。如果一个RAM程序P读了字符串S及结束标志符0后,在输 带的第一格输出一个1并停机,就说程序P接受字符串S。4
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=a1 a2…an放在输入带上。在输入带的第一个方 格中放入符号a1，第二个方格中放入符号a2，…，第n个方格中 放入符号an。然后在第n+1个方格中放入0，作为输入串的结束标 志符。如果一个RAM程序P读了字符串S及结束标志符0后，在输出 带的第一格输出一个1并停机，就说程序P接受字符串S
清华大学出版社 TSINGHUA UNIVERSITY PRESS 8.1.1随机存取机RAM 3RAM程序的耗费标准 标准一:均匀耗费标准 在均匀耗费标准下,每条RAM指令需要一个单位时间;每 个寄存器占用一个单位空间。以后除特别注明,RAM程序的复杂 性将按照均匀耗费标准衡量。 标准二:对数耗费标准 对数耗费标准是基于这样的假定,即执行条指令的耗费 与以二进制表示的指令的操作数长度成比例。在RAM计算模型下 假定一个寄存器可存放—个任意大小的整数。因此若设|(是整 数所占的二进制位数,则 og i≠0 i=0
5 8.1.1 随机存取机RAM 3. RAM程序的耗费标准 标准一：均匀耗费标准 在均匀耗费标准下，每条RAM指令需要一个单位时间；每 个寄存器占用一个单位空间。以后除特别注明，RAM程序的复杂 性将按照均匀耗费标准衡量。 标准二：对数耗费标准 对数耗费标准是基于这样的假定，即执行一条指令的耗费 与以二进制表示的指令的操作数长度成比例。在RAM计算模型下， 假定一个寄存器可存放一个任意大小的整数。因此若设l(i)是整 数i所占的二进制位数，则 0 0 1 log | | ( ) = = i i i l i
清华大学出版和 8.1,2随机存取存储程序机RASP RASP的结构 RASP的整体结构类似于RAM,所不同的是RASP的程 序是存储在寄存器中的。每条RASP指令占据2个连续的 寄存器。第一个寄存器存放操作码的编码,第二个寄存器 存放地址。RASP指令用整数迸行编码。 2.RASP程序的复杂性 不管是在均匀耗费标准下,还是在对数耗费标准下 RAM程序和RASP程序的复杂性只差一个常数因子。在一 个计算模型下T(η)时间内完成的输入-输出映射可在另 个计算模型下模拟,并在kT(nη)时间内完成。其中k是一个 常数因子。空间复杂性的情况也是类似的
6 8.1.2 随机存取存储程序机RASP 1. RASP的结构 RASP的整体结构类似于RAM，所不同的是RASP的程 序是存储在寄存器中的。每条RASP指令占据2个连续的 寄存器。第一个寄存器存放操作码的编码，第二个寄存器 存放地址。RASP指令用整数进行编码。 2. RASP程序的复杂性 不管是在均匀耗费标准下，还是在对数耗费标准下， RAM程序和RASP程序的复杂性只差一个常数因子。在一 个计算模型下T(n)时间内完成的输入-输出映射可在另一 个计算模型下模拟，并在kT(n)时间内完成。其中k是一个 常数因子。空间复杂性的情况也是类似的
清华大学出版社 TSINGHUA UNIVERSITY PRESS 813RAM模型的变形与简化 1.实随机存取机RRAM 在RRAM模型下,一个存储单元可以存放一个实数。下列的各 运算为基本运算且每个运算只耗费单位时间。 (1)算术运算+,-,X,/。 (2)2个实数间的比较()。 3)间接寻址(輕数地址) (4)常见函数的计算,如三角函数,指数函数,对 数函数等 优点:能够方使处理实数 适合于用 FORTRAN, PASCAL等高级语言写的算
7 8.1.3 RAM模型的变形与简化 1. 实随机存取机 RRAM 在RRAM模型下，一个存储单元可以存放一个实数。下列的各 运算为基本运算且每个运算只耗费单位时间。 (1)算术运算+，－，×，／。 (2)2个实数间的比较()。 (3)间接寻址(整数地址)。 (4)常见函数的计算，如三角函数，指数函数，对 数函数等。 优点：能够方便处理实数； 适合于用FORTRAN，PASCAL等高级语言写的算 法
清华大学出版社 TSINGHUA UNIVERSITY PRESS 813RAM模型的变形与简化 2.直线式程序 对于许多问题,所设计的RAM程序中的转移指令仅用于重复 组指令,而且重复的次数与问题的输入规模n成比例。在这种情 况下,可以用重复地写出相同指令组的方法来消除程序中的循环 由此,对每一个固定的n得到一个无循环的直线式程序。 经过对RAM模型的简化,得到直线式程序的指令系统如下 Xy+z Xy-z Xy Z 每条指令耗费一个单位时间。 X 其中,)和z是符号地址(或变量),而是常数
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是常数。 每条指令耗费一个单位时间
清华大学出版社 TSINGHUA UNIVERSITY PRESS 813RAM模型的变形与简化 3位式计算 直线式程序计算模型显然是基于均匀耗费标准的。在对数 耗费标准下,使用另一个RAM的简化计算模型,称之为位式计算 ( Bitwise Computation)模型。 除了下列2点外,该计算模型与直线式程序计算模型基本 相同 1)假设所有变量取值0或1,即为位变量。 (2)所用的运算是逻辑运算而不是算术运算。 用∧代表与,V代表或,⊕代表异或,一代表非。 在位式计算模型下,每个逻辑运算指令耗费一个单位时间
9 8.1.3 RAM模型的变形与简化 3. 位式计算 直线式程序计算模型显然是基于均匀耗费标准的。在对数 耗费标准下，使用另一个RAM的简化计算模型，称之为位式计算 (Bitwise Computation)模型。 除了下列2点外，该计算模型与直线式程序计算模型基本 相同： (1)假设所有变量取值0或1，即为位变量。 (2)所用的运算是逻辑运算而不是算术运算。 用∧代表与，∨代表或，代表异或，代表非。 在位式计算模型下，每个逻辑运算指令耗费一个单位时间
清华大学出版社 TSINGHUA UNIVERSITY PRESS 813RAM模型的变形与简化 4.位向量运算( Bit Vector Operations) 若在直线式程序计算模型中,假设所有变量均为位向量,而 且所用的运算均为位操作指令,则得到位向量运算计算模型。 例如,要表示—个有100个页点的图中从顶点V到其余各顶点 间有没有边相连,可以用100位的一个位向量表示。若顶点V到顶 点V之间有边相连,则该位向量的第位为1,否则为0。 缺点:所需的机器字长要远大于其他模型
10 8.1.3 RAM模型的变形与简化 4. 位向量运算(Bit Vector Operations) 若在直线式程序计算模型中，假设所有变量均为位向量，而 且所用的运算均为位操作指令，则得到位向量运算计算模型。 例如，要表示一个有100个顶点的图中从顶点v到其余各顶点 间有没有边相连，可以用100位的一个位向量表示。若顶点v到顶 点vj之间有边相连，则该位向量的第j位为1，否则为0。 缺点：所需的机器字长要远大于其他模型