《完全性理论》ppt课件

《《完全性理论》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第8章NP完全性理论18.1计算模型8.1.1随机存取机RAM8.1.2随机存取存储程序机RASP8.1.3图灵机8.1.4图灵机模型与RAM模型的关系8.1.5问题变换与计算复杂性归约28.1.1随机存取机RAM1.RAM的结构38.1.1随机存取机RAM2.RAM程序一个RAM程序定义了从输入带到输出带的一个映射。可以对这种映射关系作2种不同的解释。解释一：把RAM程序看成是计算一个函数若一个RAM程序P总是从输入带前n个方格中读入n个整数x1，x2，…，xn，并且在输出带的第一个方格上输出一个

2、整数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。48.1.1随机存取机RAM3.RAM程序的耗费标准标准一：均匀耗费标准在均匀耗费标准下，每条RAM指

3、令需要一个单位时间；每个寄存器占用一个单位空间。以后除特别注明，RAM程序的复杂性将按照均匀耗费标准衡量。标准二：对数耗费标准对数耗费标准是基于这样的假定，即执行一条指令的耗费与以二进制表示的指令的操作数长度成比例。在RAM计算模型下，假定一个寄存器可存放一个任意大小的整数。58.1.2随机存取存储程序机RASP1.RASP的结构RASP的整体结构类似于RAM，所不同的是RASP的程序是存储在寄存器中的。每条RASP指令占据2个连续的寄存器。第一个寄存器存放操作码的编码，第二个寄存器存放地址。RAS

4、P指令用整数进行编码。2.RASP程序的复杂性不管是在均匀耗费标准下，还是在对数耗费标准下，RAM程序和RASP程序的复杂性只差一个常数因子。在一个计算模型下T(n)时间内完成的输入-输出映射可在另一个计算模型下模拟，并在kT(n)时间内完成。其中k是一个常数因子。空间复杂性的情况也是类似的。68.3图灵机1.多带图灵机78.1.3图灵机1.多带图灵机根据有限状态控制器的当前状态及每个读写头读到的带符号，图灵机的一个计算步可实现下面3个操作之一或全部。(1)改变有限状态控制器中的状态。(2)清除当前

5、读写头下的方格中原有带符号并写上新的带符号。(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的函数。88.

6、1.3图灵机1.多带图灵机图灵机M的时间复杂性T(n)是它处理所有长度为n的输入所需的最大计算步数。如果对某个长度为n的输入，图灵机不停机，T(n)对这个n值无定义。图灵机的空间复杂性S(n)是它处理所有长度为n的输入时，在k条带上所使用过的方格数的总和。如果某个读写头无限地向右移动而不停机，S(n)也无定义。与RAM模型类似，图灵机既可作为语言接受器，也可作为计算函数的装置。98.1.4图灵机模型与RAM模型的关系图灵机模型与RAM模型的关系是指同一问题在这2种不同计算模型下的复杂性之间的关系。定

7、理8-3对于问题P的任何长度为n的输入，设求解问题P的算法A在k带图灵机模型TM下的时间复杂性为，那么，算法A在RAM模型下的时间复杂性为。定理8-4对于问题P的任何长度为n的输入，设求解问题P的算法A在RAM模型下，不含有乘法和除法指令，且按对数耗费标准其时间复杂性为，那么，算法A在k带图灵机模型TM下的时间复杂性为。108.1.5问题变换与计算复杂性归约具体地说，假设有2个问题A和B，将问题A变换为问题B是指：(1)将问题A的输入变换为问题B的适当输入。(2)解出问题B。(3)把问题B的输出变换

8、为问题A的正确解。若用O(τ(n))时间能完成上述变换的第(1)步和第(3)步，则称问题A是τ(n)时间可变换到问题B，且简记为A∝τ(n)B。其中的n通常为问题A的规模(大小)。当τ(n)为n的多项式时，称问题A可在多项式时间内变换为问题B。特别地，当τ(n)为n的线性函数时，称问题A可线性地变换为问题B。通过问题变换的技巧，可以将2个不同问题的计算复杂性联系在一起。这样就可以将一个问题的计算复杂性归结为另一个问题的计算复杂性，从而实现问题的计算复杂性归约。118.