算法分析与设计-2016-第4讲

《算法分析与设计-2016-第4讲》由会员分享，可在线阅读，更多相关《算法分析与设计-2016-第4讲（30页珍藏版）》请在金锄头文库上搜索。

1、算法分析与设计,第4讲-2016 山东大学计算机学院/软件学院,上次内容： (1)确定型图灵机与P类，DTM多项式时间可解的-P类 (2)非确定图灵机与NP类，NP类-多项式时间可验证的，或NTM多项式时间可计算的。 注意：在定义时空复杂性时， 我们只关心NTM程序计算回答为Yes的实例的时空复杂性。 回答否的实例不关心。 只是针对那些回答为Yes的实例定义时空复杂性， 这样定义足以满足我们的需要。 Rabin与Scott两个人最先在IBM做的工作，最先定义的非确定计算。 企图把算法分为两大类，多项式时间的和指数时间的， 其实这样分类是有局限性的，不一定完美，但能说明问题。,相隔了近30年！

2、非确定图灵机没法实现！,因为判定问题都可以当作一个语言的识别问题。一个语言：给定符号集=0，1，一个语言就是一个*的子集L *。 判定一个x *是否属于L，即所谓判定问题。,只能验证一面,，SAT实例符号集合 L，回答是的SAT实例集合 判定：x *，是否属于L,1变换到2，应该达到的目的：若2存在多项式算法， 则1也有多项式算法。 多项式变换(归约)： 1=；2= 变换f：1* 2* IL1，f(I)L2，1(I)=2(f(I) f变换可以在p(|I|=n)时间内计算完成。 则f称为由1到2的多项式时间归约。Reduction,(1)非确定型图灵机与验证机还是不同的。 (2)但是有一个结论：

3、一个问题是多项式时间可验证的， 当且仅当它是非确定型图灵机多项式时间可计算的。 (3)Rabin与Scott两个人最先在IBM做的工作。 定义了非确定型计算，也就有了非确定型图灵机。,多项式算法,多项式变换与NPC类，上次讲到什么是多项式变换。 我们需要什么？定义多项式变换，达到如下目标：,R-S的,非确定图灵机的时间复杂性难定义。 只关心回答Yes的实例的时间就好说了。 NP问题可以认为若实例回答是， 则存在不确定多项式时间算法正确回答的判定问题类。 *在定义NP问题时，只关心问题的那些回答Yes的实例。 回答No的实例不关心。 NP类：若对回答Yes的问题实例，存在NTM程序能够多项式 时

4、间回答是，则这个问题就属于NP类。 *用不着关心那些回答No的实例。为什么？能够达到目的了。 前人就是这么定义的。,若有实例I，猜测机猜测了一个解放到读写带上，我们的程序验证回答是，则可以回答I是一个回答是的实例； 不需要定义的是回答否的那些实例： 若猜测机猜测了一个解放到读写带上，我们的程序验证回答否，不知道I是否是回答否的实例，所以干脆不定义！,希望： 若1可以多项式归约到2，2存在多项式算法， 则1也有多项式算法。 前面的多项式归约进一步修改如下： 认为与前面的定义等价。只关心那些回答yes的实例了。,1=；2= 变换f：,(1)IL1，f(I)L2， (2)1(I)=12(f(I)=1

5、，充分必要的。 IY(1)f(I)Y(2)。不关心回答No的实例。 实际前面NTM定义中就只关心回答Yes的实例。 (3)f变换可以在p(|I|=n)时间内计算完成。,1,2,*P问题可以在多项式时间回答是或否。 *NP问题只能在多项式时间回答是。 * P问题可以在多项式时间判定解的存在性。 *NP问题只能多项式时间验证解存在。 *1变换为2，当然希望2是多项式时间可计算的。,引理3.1：若12，2P，则1P。 注意一点，当多项式可解时， 否的实例也能在多项式时间回答。 证明：回答是的实例能够变换，回答否的实例也能够变换。 当2P时，是和否都能多项式时间回答。 当然1实例回答是和否也能多项式时

6、间回答 下面又要回忆前面的内容了！,I,f(I),1 2,再解释非确定Turing机：规定 (1)猜测部件把猜测的解写在从-1开始向左的存储带上。 (2)我们自己编写的验证程序直接使用带方格x,-1中的猜测信息。 (3)实际这不是最早(Rabin,Scott)的非确定型图灵机版本。 (4)NP问题，多种定义版本，多项式时间可验证的， NTM多项式时间可求解的。,该说明什么是NP-Complete问题了。 期望：若有一个特殊NP问题， 任意一个NP问题均可多项式时间归约到该问题， 则该问题非常特殊，称为NP-Complete问题。 要求是NP类问题。 若NP-Complete问题可以多项式时间解

7、决， 则其他所有NP问题都可以在多项式时间解决。 所有NP问题都能多项式时间可解，这件事其实很大的重任。 几乎不可能的，所以NP-C问题多项式时间可解， 也是不可能的。,解释：如果NP-C行， 什么鸟都行！,每个NP问题都存在多项式时间解答算法吗？,(1)首先要搞清楚， 现在我们研究的问题是多项式时间可验证的问题类， 最后只需要回答是和否即可以。 (2)有很多问题不是多项式时间可验证的，那个留到以后再说。 因此也不是NPC的。这就是为什么只研究判定问题了。 (3)判定问题正面绝大多数都是多项式时间可验证的。,多项式变换的符号： 引理3.2：12，23，则13 定义3.10：12，21，则称1和

8、2多项式等价。,定义3.11：NP，1NP，1，则称是NP-Complete的。 NP-完全的。其他人有很多叫法。 简称NPC问题。若是NPC问题， 定义的含义： 有多项式时间算法，则任意NP问题都有多项式时间求解算法。,定理3.12：若有， NPC，则下述(1)(2)等价。 (1)PNP；(2) P，即：PNP P,定理：若1NPC，2NP，12，则2NPC 就是说1与2是多项式等价的。有一个是多项式的， 则另一个也是多项式的。 这是最重要的一个定理。只要有了一个NPC， 其他问题也可以证明NPC了。 下面的问题是寻找第一个NPC问题。,1970年Cook证明Sat问题是NP-完全问题。 即

9、Cook定理。 SAT的例子：是否存在U=u1,u2,u3,u4,u5的真值指派，使 Y = ( )( )( )( )=T,3.5Cook定理 任意一个NP问题都有一个多项式时间验证程序。 多项式时间验证结果回答Yes。 一个问题要形式化描述，怎么描述？ 1970年Cook证明Sat问题是NP-完全问题。即Cook定理。,实例：U=u1,u2,u3,u4,u5,C=C1,C2,C3,C4 询问：If there is an assignment of U such that all clauses in C are satisefied？,定理3.4：SAT NPC。 证明：(要说明如果SAT

10、有多项式时间算法，则所有NP问题 都有多项式算法) (1)SATNP，首先要验证这个。 不验证不能说明是NPC。 不属于NP是否属于NPC? 不属于。 (2)将任意一个NP问题多项式归约到Sat。 任意NP问题的实例：x1, x2, , xn 这与Sat问题没法建立起联系来，要建立联系，还靠NTM。 *每个NP问题都对应一个NTM的多项式时间验证程序。 该验证程序最后回答Yes或No。 只对yes的实例多项式时间回答是。 但是我们只关心回答Yes的NP问题实例。 任意一个NP问题的回答yes的实例放在NTM存储带上， NTM程序多项式时间步验证给出正确回答。,若NP,1,1,则是NP-Comp

11、lete.,设NTM描述为：描述问题需要的符号集 =s1,s2,sm=s1, s2, , sm, si=si Q=q0,q1=qy,q2=qn,q3,qr (qi,si)=(qi,si,i)，变化规则早已确定了，就是程序。 P(n)：M接受输入I，|I| = n，I是回答是的实例， I：sk1, sk2, , skn 按照计算，对于猜测的解，经过不超过P(n)步计算， 到达停机态qy，P(n)是n的多项式函数。 最多有(r+1)(m+1)条规则。,问题实例,每个实例都存放在读写带上了，要把这个实例变成SAT的实例。 实例为：sk1, sk2, , skn。 怎样把这个实例变成SAT实例？ 这个

12、实例回答Yes变成的SAT实例也回答Yes。 要借助别的东西，借助验证程序。 可以形式化地描述验证程序， (qi, si)(qi ,si ,i) 下面是所有的规则：(r+1)(m+1)条,一个实例回答是，就意味着存在一个NTM程序M，执行M可多项式时间停机在qy,NTM执行程序的每一步状态都可以用SAT布尔变量表示。 开始归约：变量描述求解过程，项约束求解中程序遵循的规则。 1定义三种变量描述NTM的求解状态， (1)Qi,k:描述状态，0iP(n)，0kr， 在时刻i，M处于状态qk，(r+1)(P(n)+1)个这样的变量。 (2)Hi,j：描述读写头位置，0iP(n)，-P(n)jP(n)

13、， 在时刻i，M读写头正扫描带方格j。(2P(n)+1)(P(n)+1)个变量。 (3)Si,j,l：描述带方格内容，0iP(n)，-P(n)jP(n)，0lm， 在i时刻,带方格j中存储的符号为sl，(m+1)(2P(n)+1)(P(n)+1)。,其实，是想用Sat的语句来描述任意一个NP问题是怎样验证的。也就是描述NP问题是怎样回答是的。怎样回答是，就把问题自身特点描述出来了，就是用NTM程序表达了问题本身的个性。,解释：从0到P(n)每一个时刻的Turing机状态， 读写头位置，读写带上的符号。都已经描述出来了。 2NTM程序接受判定问题的实例I，M运行中应遵循下述规则。,G1：在时刻i

14、，M确切处在一个状态 (1)Qi,0,Qi,1,Qi,r，0iP(n) (2) ，0iP(n)，0jjr,(1)有P(n)+1个， (2)有(P(n)+1)P(n)/2个,P(n)+1个,(2)不能同时有两个符号： ， ， 0iP(n)，-P(n)jP(n)，0 kkm,G3的构成：在i时刻，每个带方格中含有一个固定的符号 (1)Si,j,0,Si,j,1,Si,j,m，0iP(n)，-P(n)jP(n) i时刻，j号带方格中的内容可能是b,s1,sm,G4的构成：确定初始状态： (1)Q0,0：0时刻状态为q0 (2)H0,0：0时刻读写头位于0号带方格 S0,0,0，S0,1,k1，S0,

15、n,kn S0,n+1,0，S0,n+2,0，S0,P(n),0 0时刻带方格中的内容分别为：s0,sk1,skn。 其他带方格中是什么内容？-1，-P(n) 有个秘密：猜测信息放在-1，-P(n),G5：在P(n)时刻，NTM处于接受状态。因为这是回答yes的实例 QP(n),1，时刻P(n)的NTM状态为qy=q1。接受状态。,G6:描述NTM必须按照程序的规则运行。 G6=G61G62，两个子项 G61：保证在时刻i，若读写头不扫描带方格j， 则在时刻i+1，j带方格的内容与i时刻j带方格的内容相同。 不能随便改变。 ，Hi,j,Si+1,j,l，0iP(n)，-P(n)jP(n)，0lm,若 Si,j,l=1,Hi,j=0,则Si+1,j,l=1 G61的个数：(P(n)+1)(2P(n)+1)(m+1),G62：当NTM程序从一个状态转到另一个状态时