算法分析与设计2016第4讲

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

2、个语言的识别问题。一个语言：给定符号集=0，1，一个语言就是一个*的子集L *。判定一个x *是否属于L，即所谓判定问题。只能验证一面2，SAT实例符号集合L，回答是的SAT实例集合判定：x *，是否属于L31变换到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做的工作。定义了非确定型计算，也就有了非确定型图灵机。 21多项式算法多项式变换与NPC类，上次讲到什么是多项式变换。我们需要什么？定义多项式变换，达到如下目标：R-S的4非确定图灵机的时间复杂性难定义。只关心回答Yes的实例的时间就好说了。NP问题可以认为若实例回答是，则存在不确定多项式时间算法正确回答的判定问题类。*在定义NP问题时，只关心问题的那些回答Yes的实例。回答No的实例不关心。NP类：若对回答Yes的问题实例，存在NTM程序能够多项式时间回答是，则这个问题就属于NP类。*用不着关心那些回答No的实例。为什么？能够达到目的了。前人就

4、是这么定义的。若有实例I，猜测机猜测了一个解放到读写带上，我们的程序验证回答是，则可以回答I是一个回答是的实例；不需要定义的是回答否的那些实例：若猜测机猜测了一个解放到读写带上，我们的程序验证回答否，不知道I是否是回答否的实例，所以干脆不定义！5希望：若1可以多项式归约到2，2存在多项式算法，则1也有多项式算法。前面的多项式归约进一步修改如下：认为与前面的定义等价。只关心那些回答yes的实例了。 1=；2= 变换f：(1)IL1，f(I)L2，(2)1(I)=12(f(I)=1，充分必要的。IY(1)f(I)Y(2)。不关心回答No的实例。实际前面NTM定义中就只关心回答Yes的实例。(3)f

5、变换可以在p(|I|=n)时间内计算完成。 126*P问题可以在多项式时间回答是或否。*NP问题只能在多项式时间回答是。* P问题可以在多项式时间判定解的存在性。*NP问题只能多项式时间验证解存在。*1变换为2，当然希望2是多项式时间可计算的。引理3.1：若12，2P，则1P。注意一点，当多项式可解时，否的实例也能在多项式时间回答。证明：回答是的实例能够变换，回答否的实例也能够变换。当2P时，是和否都能多项式时间回答。当然1实例回答是和否也能多项式时间回答下面又要回忆前面的内容了！ If(I)yesnoAlgIY()IN()1 27再解释非确定Turing机：规定(1)猜测部件把猜测的解写在从

6、-1开始向左的存储带上。(2)我们自己编写的验证程序直接使用带方格x,-1中的猜测信息。(3)实际这不是最早(Rabin,Scott)的非确定型图灵机版本。(4)NP问题，多种定义版本，多项式时间可验证的，NTM多项式时间可求解的。8该说明什么是NP-Complete问题了。期望：若有一个特殊NP问题，任意一个NP问题均可多项式时间归约到该问题，则该问题非常特殊，称为NP-Complete问题。要求是NP类问题。若NP-Complete问题可以多项式时间解决，则其他所有NP问题都可以在多项式时间解决。所有NP问题都能多项式时间可解，这件事其实很大的重任。几乎不可能的，所以NP-C问题多项式时间

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

8、算法，则任意NP问题都有多项式时间求解算法。 NPNPC10定理3.12：若有， NPC，则下述(1)(2)等价。(1)PNP；(2) P，即：PNP P定理：若1NPC，2NP，12，则2NPC就是说1与2是多项式等价的。有一个是多项式的，则另一个也是多项式的。这是最重要的一个定理。只要有了一个NPC，其他问题也可以证明NPC了。下面的问题是寻找第一个NPC问题。 PNPNPCP引理3.1：若12，2P，则1P。111970年Cook证明Sat问题是NP-完全问题。即Cook定理。SAT的例子：是否存在U=u1,u2,u3,u4,u5的真值指派，使Y = ( )( )( )( )=T3.5C

9、ook定理任意一个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？12定理3.4：SAT NPC。证明：(要说明如果SAT有多项式时间算法，则所有NP问题都有多项式算法)(1)SATNP，首先要验证这个。不验证不能说明是NPC。不属于NP是否属于NPC? 不属于。

10、(2)将任意一个NP问题多项式归约到Sat。任意NP问题的实例：x1, x2, , xn这与Sat问题没法建立起联系来，要建立联系，还靠NTM。*每个NP问题都对应一个NTM的多项式时间验证程序。该验证程序最后回答Yes或No。只对yes的实例多项式时间回答是。但是我们只关心回答Yes的NP问题实例。任意一个NP问题的回答yes的实例放在NTM存储带上，NTM程序多项式时间步验证给出正确回答。若NP,1,1,则是NP-Complete.13设NTM描述为：描述问题需要的符号集=s1,s2,sm=s1, s2, , sm, si=siQ=q0,q1=qy,q2=qn,q3,qr(qi,si)=(

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

12、的SAT实例也回答Yes。要借助别的东西，借助验证程序。可以形式化地描述验证程序，(qi, si)(qi ,si ,i)下面是所有的规则：(r+1)(m+1)条一个实例回答是，就意味着存在一个NTM程序M，执行M可多项式时间停机在qy16NTM执行程序的每一步状态都可以用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)，在时刻i，M读写头正扫描带方格j。

13、(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程序表达了问题本身的个性。17解释：从0到P(n)每一个时刻的Turing机状态，读写头位置，读写带上的符号。都已经描述出来了。2NTM程序接受判定问题的实例I，M运行中应遵循下述规则。 G1在时刻i，M确切处在一个状态，q0, , qrG2在时刻

14、i, 读写头确切地扫描一个带方格。G3在时刻i,每个带方格确切地含有一个符号，中的。G4在时刻0，对于输入I，计算处于验证阶段的起始状态。G5在时刻P(n)，M处于qy状态，接受I。G6转换函数决定i时刻到i+1时刻的状态变化。18G1：在时刻i，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个19(2)不能同时有两个符号： ， ， 0iP(n)，-P(n)jP(n)，0 kkmG3的构成：在i时刻，每个带方格中含有一个固定的符号(1)Si,j,0,Si,j,1,Si

15、,j,m，0iP(n)，-P(n)jP(n)i时刻，j号带方格中的内容可能是b,s1,sm(1)项的数目：(P(n)+1)(2P(n)+1)(2)项的数目：(P(n)+1)(2P(n)+1) 20G4的构成：确定初始状态：(1)Q0,0：0时刻状态为q0(2)H0,0：0时刻读写头位于0号带方格S0,0,0，S0,1,k1，S0,n,knS0,n+1,0，S0,n+2,0，S0,P(n),00时刻带方格中的内容分别为：s0,sk1,skn。其他带方格中是什么内容？-1，-P(n) 有个秘密：猜测信息放在-1，-P(n)G5：在P(n)时刻，NTM处于接受状态。因为这是回答yes的实例QP(n)

16、,1，时刻P(n)的NTM状态为qy=q1。接受状态。 21G6:描述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=1G61的个数：(P(n)+1)(2P(n)+1)(m+1)G62：当NTM程序从一个状态转到另一个状态时，状态变化，读写头移动，符号改变遵从函数。(qk,sl)=( )必须按照这样的规则执行，改变状态。状态转换函数个数：(

17、r+1)(m+1) 22若Hi,j=1, Qi,k=1, Si,j,l=1, 则Hi+1,j+=1 i时刻的状态为qk，读写头位置为j，j方格中的符号为sl则读写头移动为。0iP(n)，-P(n)jP(n)，0kr，0lm所以这样的clause个数是：(P(n)+1)(2P(n)+1)(r+1)(m+1)111123(2)若Hi,j=1, Qi,k=1, Si,j,l=1, 则Qi+1,k=10iP(n)，-P(n) j P(n)，0kr，0 l m。所以(2)的clause个数是：(P(n)+1)(2P(n)+1)(r+1)(m+1)(3)Hi,j=1, Qi,k=1, Si,j,l=1,

18、则Si+1,j,l=10iP(n)，-P(n)jP(n)，0kr，0Lm(3)的个数也不超过：(P(n)+1)(2P(n)+1)(r+1)(m+1) 24上面是规约，首先说明这个规约是多项式规约，G1, G2, G3, G4, G5, G6都是多项式个clause，因此是多项式规约。G1: P(n)+1+(P(n)+1)P(n)/2个G2: 2P(n)+1+(P(n)+1)(2P(n)+1)(2P(n)/2个G3: (P(n)+1)(2P(n)+1)+(P(n)+1)(2P(n)+1)(m+1)m/2个G4: P(n)+3G5: 1G61: (P(n)+1)(2P(n)+1)(m+1)G62: (P(n)+1)(2P(n)+1)(r+1)(m+1) +(P(n)+1)(2P(n)+1)(r+1)(m+1) +(P(n)+1)(2P(n)+1)(r+1)(m+1) 25若的实例I回答yes，则NTM程序最后停机在qy，则必存在一个sat变量的真值指派使每个项均满足。若sat实例存在真值指派使每个项均满足，则最后NTM会停机在yes态，相应问题的实例回答yes。这就证明了第一个NP-complete问题。 再说明：*为什么SAT能多项式时间可解，则NTM就不用猜测解了。*S0,-1,s1，S0,-1,s2，S0,-1,sm，* S0,-2,s1，S0,-2,s2，