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

《算法分析与设计-2016-第4讲.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、样分类是有局限性的，不一定完美，但能说明问题。相隔了近30年！非确定图灵机没法实现！因为判定问题都可以当作一个语言的识别问题。一个语言：给定符号集={0，1}，一个语言就是一个*的子集L*。判定一个x*是否属于L，即所谓判定问题。只能验证一面，SAT实例符号集合L，回答是的SAT实例集合判定：x*，是否属于L1变换到2，应该达到的目的：若2存在多项式算法，则1也有多项式算法。多项式变换(归约)：1=<1,L1,1>；2=<2,L2,2>变换f：1*2*IL1，f(I)L

3、2，1(I)=2(f(I))f变换可以在p(

4、I

5、=n)时间内计算完成。则f称为由1到2的多项式时间归约。Reduction(1)非确定型图灵机与验证机还是不同的。(2)但是有一个结论：一个问题是多项式时间可验证的，当且仅当它是非确定型图灵机多项式时间可计算的。(3)Rabin与Scott两个人最先在IBM做的工作。定义了非确定型计算，也就有了非确定型图灵机。21多项式算法多项式变换与NPC类，上次讲到什么是多项式变换。我们需要什么？定义多项式变换，达到如下目标：R-S的非确定图灵机的时间复杂性难定义。只

6、关心回答Yes的实例的时间就好说了。NP问题可以认为若实例回答是，则存在不确定多项式时间算法正确回答的判定问题类。*在定义NP问题时，只关心问题的那些回答Yes的实例。回答No的实例不关心。NP类：若对回答Yes的问题实例，存在NTM程序能够多项式时间回答是，则这个问题就属于NP类。*用不着关心那些回答No的实例。为什么？能够达到目的了。前人就是这么定义的。若有实例I，猜测机猜测了一个解放到读写带上，我们的程序验证回答是，则可以回答I是一个回答是的实例；不需要定义的是回答否的那些实例：若猜测机猜测了一个解放到读写带上

7、，我们的程序验证回答否，不知道I是否是回答否的实例，所以干脆不定义！希望：若1可以多项式归约到2，2存在多项式算法，则1也有多项式算法。前面的多项式归约进一步修改如下：认为与前面的定义等价。只关心那些回答yes的实例了。1=<1,L1,1>；2=<2,L2,2>变换f：(1)IL1，f(I)L2，(2)1(I)=12(f(I))=1，充分必要的。IY(1)f(I)Y(2)。不关心回答No的实例。实际前面NTM定义中就只关心回答Yes的实例。(3)f变换可以在p(

8、I

9、=n

10、)时间内计算完成。12*P问题可以在多项式时间回答是或否。*NP问题只能在多项式时间回答是。*P问题可以在多项式时间判定解的存在性。*NP问题只能多项式时间验证解存在。*1变换为2，当然希望2是多项式时间可计算的。引理3.1：若12，2P，则1P。注意一点，当多项式可解时，否的实例也能在多项式时间回答。证明：回答是的实例能够变换，回答否的实例也能够变换。当2P时，是和否都能多项式时间回答。当然1实例回答是和否也能多项式时间回答下面又要回忆前面的内容了！If(I)yesnoAlgIY(

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

12、lete问题可以多项式时间解决，则其他所有NP问题都可以在多项式时间解决。所有NP问题都能多项式时间可解，这件事其实很大的重任。几乎不可能的，所以NP-C问题多项式时间可解，也是不可能的。解释：如果NP-C行，什么鸟都行！每个NP问题都存在多项式时间解答算法吗？(1)首先要搞清楚，现在我们研究的问题是多项式时间可验证的问题类，最后只需要回答是和