唐常杰翻译的计算理论导引21

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,Chap 9,难解性 供同学报告修改,可以从下列文件获得素材：,参考以前同学的报告，,修改成为有自己见解的讨论报告,13_09d1_难解性同学报告素材.doc,2024/9/21,1,可根据 提供的,PT,素材,+,参考以前同学的报告， 修改成为有自己见解的讨论报告建议：,底色用浅色（象牙白， 浅黄， 白色等） 适合色盲 色弱 观众 字体颜色选择余地大 在投影机 效果差时 也还能能看见,2024/9/21,2,难解性的含义：,若某一计算问题在理论上是可解的，但解法需要耗费大量的时间或空间，以至于无法在实践中应用，则称该问题是难解的。,2024/9/21,3,难解性的形式,难解性可以有多种形式：,例如 ：,1、一个大部分时间容易计算但偶尔很难算的问题，仅在最坏情况下是难解的；,2、在超级计算机上是易算的，但在,PC,机上可能需要过量时间的问题,2024/9/21,4,本章的目标,证明存在理论上可判定但实际中不可判定的问题即可判定而难解的问题。,2024/9/21,5,总之：难解性问题指的是在最坏情况下复杂性太大，以至于在任何所能想象建造出来的计算机上所耗费的时间都将超过宇宙的余生。,例如：,SAT,问题和所有的,NP,完全问题。,2024/9/21,6,9.1,层次定理,层次定理的含义：定理中的每一个都能证明时间和空间复杂性类不全相同，它们形成了一个层次结构，其中时空界限较大的类比时空界限较小的类包含更多的语言。,例如：层次定理能形式化的证明：图灵机在更多的时间或空间能扩大它所能解的问题类。也就是说，图灵机在时间,n,3,内比,n,2,内能判定更多的语言。,2024/9/21,7,层次定理的分类,空间复杂性层次定理,（简单）,时间复杂性层次定理,（复杂）,2024/9/21,8,函数,f:N N,f(n),=,logn,称为空间可构造的，如果函数把,1,n,（,n,个1的字符串） 映射为,f(n),的二进制表示，并在空间,O(f(n),内是可计算的。,含义：如果存在某个图灵机,M，,在,O(f(n),空间内运行，并且在输入,1,n,后总能停机，停机时,f(n),的二进制表示出现在带子上，则,f,是空间可构造的,定义,9.1,2024/9/21,9,通常出现的不小于,logn,的函数都是空间可构造的，例如,logn,，,nlogn,，,n,2,.,例,9.2,2024/9/21,10,定理,9.3,空间层次定理,对任何空间可构造函数,f:N N,，,存在语言,A，,在空间,O（f（n）,内可判定，但不能在空间,o（f（n）,证明思路 必须显示一个语言,A,具有两个性质：第一，,A,在空间,O（f（n）,内可判定；第二，,A,不能在空间,o（f（n）,判定。,2024/9/21,11,推论,9.4,空间层次定理,对任何两个函数,f,1,，,f,2,：,N N,其中,f,1,（n）,等于,o,（,f,2,（n）， f,2,是空间可构造的，有,SPACE,(,f,1,（n）),真包含于,SPACE,(,f,2,（n）),该推论的作用能够把不同的空间复杂性类分开。,2024/9/21,12,推论,9.5,对任意两个实数,0,r1 r2,有,SPACE(n,r1,),真包含于,SPACE(n,r2,),也可以用空间层次定理来分离前面碰到的的两个空间复杂性类。,2024/9/21,13,推论,9.6,NL,真包含于,PSPACE,证明：萨维奇定理说明,NL,不真包含于,SPACE(,2,n,),空间层次定理说明,SPACE(,2,n,),真包含于,SPACE(n),所以推论成立。,2024/9/21,14,推论,9.7,PSPACE,真包含于,EXPSPACE,意义：判定过程必须消耗多于多项式的空间。,2024/9/21,15,定义,9.8,函数,t:N N,t(n),=,nlogn,称为时间可构造的，如果函数把1,n,（,n,个1的字符串） 映射为,t(n),的二进制表示，并在时间,O(t(n),内是可计算的。,含义：如果存在某个图灵机,M，,在时间,O(t(n),内运行，而且在输入,1,n,上启动后总能停机，停机时,t(n),的二进制表示出现在带子上，则,t,是时间可构造的。,2024/9/21,16,通常出现的不小于,n,logn,的函数都是时间可构造的，例如,n,logn,，,n,2,以及,2,n,。,例,9.9,2024/9/21,17,定理,9.10,时间层次定理,对于任何时间可构造函数,t:N N,，,存在语言,A，,在时间,O（t（n）,内可判定，但在时间,o（t（n）/logt(n),内不可判定,证明思路 类似10.3。,2024/9/21,18,推论,9.11,对任何两个函数,t,1,，,t,2,：,其中,t,1,（n）,等于,o(t,2,（n）/logt,2,(n),，,t,2,是时间可构造的，有,TIME(t,1,（n）),真包含于,TIME(t,2,（n）),。,2024/9/21,19,推论,9.12,对任意两个实数0,r1,r2,有,TIME(n,r1,),真包含于,SPACE(n,r2,),2024/9/21,20,推论,9.13,P,真包含于,EXPTIME,2024/9/21,21,指数空间完全性,证明一个具体的语言事实难解需要分两步：,第一：图灵机在,EXPSPACE,内比在,PSPACE,内判定更多的语言；,第二：证明有关广义正则表达式的一个具体的语言是,EXPSPACE,完全的，即不能在多项式时间、也不能在多项式空间内判定。,2024/9/21,22,定义,9.14,语言,B,是,EXPSPACE,完全的，当且仅当：,（1）,B,EXPSPACE,;,并且,（2）,EXPSPACE,中的每个,A,都是多项式时间可归约到,B,。,2024/9/21,23,定理,9.15,EQ,REX,是,EXPSPACE,完全的。,证明思路：在度量判定,EQ,REX,的复杂性时，假设所有指数都写成二进制整数。表达式的长度是它包含的所有符号的总数。,2024/9/21,24,.2,相对化,2024/9/21,25,1.,研究的主要的内容,给出有力证据否定用对角化法解决,P,与,NP,问题的可能性,.,2024/9/21,26,2.,几个基本概念和定义,(1),谕示 （可比喻为 一块 超级芯片 ， 外星人的智能礼物）,P138:,语言,B,的一个谕示是一个能够报告某个串是否为,B,的成员的外部装置,.,一个谕示是一个语言,A.,(2),谕示图灵机,M,A,是通常的图灵机附加一条谕示带,每当,M,在谕示带上写下一个字符串时,就能在一步计算内得知这个字符串是否属于,A.,2024/9/21,27,2.,几个基本概念和定义,(,续,),(3)P,A,采用谕示,A,的多项式时间谕示图灵机可判定的语言类,.,(4)NP,A,采用谕示,A,的非确定多项式时间谕示图灵机可判定的语言类,.,2024/9/21,28,3.,举例,(1)NP,P,SAT,含义,:,相对于可满足性问题的多项式时间计算包含了,NP,问题的全部,.,(2)CONP P,SAT,(3),极小公式,:,如果一个公式没有更小的公式与之等价,则称它为极小的,.,2024/9/21,29,NONMIN-FORMULA=|,不是极小布尔公式,NP OR NP?,NP,SAT,(1),等价问题属于,CONP,(2),谕示,SAT,检查是否有更小的等价公式,.,是则接受,.,2024/9/21,30,4.,对角化方法的局限,(1),对角化方法的核心,:,是一台图灵机对另一台图灵机的模拟,.,(2),结论,:,凡是仅用对角化方法证明的关于图灵机的定理,当给两台机器以相同谕示的时候,仍然成立,.,2024/9/21,31,问题,能否用对角化方法证明,P,与,NP,不同,亦即它们相对于任何谕示都不同,?,能否依据简单的模拟证明说明,P,与,NP,相等,即证明它们对于任何谕示都是相等的,?,2024/9/21,32,定理,.19,1),存在谕示,A,使得,P,A, NP,A,2),存在谕示,B,使得,P,B,= NP,B,上述定理表明不太可能用对角化方法和简单模拟的证明来解决,P,与,NP,问题,.,2024/9/21,33,证明思路,(2),只要令,B,是,PSPACE,问题如,TQBF,即可,.,NP,TQBF,NPSPACE PSPACE P,TQBF,因为可以把非确定型多项式时间谕示机器转变为非确定型多项式空间机器,.,萨维奇定理,因为,TQBF,是,PSAPCE,完全的,.,2024/9/21,34,构造谕示,A.,设计,A,使得,NP,A,中的某个语言,L,A,可以证明需要蛮力搜索,因而,L,A,不可能属于,P,A,.,因此可以得出,P,A,NP,A,的结论,.,L,A,=,|,x A |x| = |,|,NP,A,P,A,2024/9/21,35,关 键,构造谕示,A:,经过所有构造步骤以后状态没有确定下来的字符串声明为不在,A,中,.,亦即没有多项式时间谕示机器能够以谕示,A,判定,L,A,.,2024/9/21,36,9.3,电路复杂性,2024/9/21,37,布尔电路,定义.20,布尔电路是由导线连接的门和输入的集合。,门的三种形式：与、或、非门,布尔函数：,AND、OR、NOT,门：布尔函数处理器,输入,输出,2024/9/21,38,布尔电路示例,x1,输出门,x2,x3,输入变量,0,x1,输出,1,x2,0,x3,输入,1,0,0,1,1,1,用函数描述布尔电路的输入/输出：,Fc:0,1,n,-0,1,Fc(a1,a,n,)=b,2024/9/21,39,例,9.21,奇偶函数,parity,n,:0,1,n,-0,1,输出1，当且仅当输入变量中有奇数个1,x1,x2,x3,x4,实现,例10.21 布尔电路,2024/9/21,40,电路族,定义,9.22,一个电路族,C,是电路的一个无穷列表（,C,0,， C,1,， C,2,，),其中,C,n,有,n,个输入变量。,称,C,在0，1上判定语言,A，,如果对于每个字符串,w，w,A,当且仅当,Cn(w)=1,其中,n,是,w,的长度。,电路的规模-所包含门的数目,规模复杂度：一个电路族（,C,0,， C,1,， C,2,，),的规模复杂度是一个函数,f:N-N,其中,f(n),是,C,n,的规模,深度及复杂度：电路的深度是从输入变量到输出门的最长路径的长度。,规模极小、深度极小,2024/9/21,41,电路复杂度,定义,9.23,语言的电路规模复杂度是该语言的极小电路族的规模复杂度。,语言的电路深度复杂度是该语言的极小电路族的深度复杂度。,2024/9/21,42,电路复杂性的三个定理,2024/9/21,43,定理,9.25 cp212,定理,10.25,设,t:N-N,是一个函数，,t(n),n,。若,，则,A,的电路复杂度为,。,时间复杂度小的语言，电路复杂度也小,2024/9/21,44,证明思路,M,是在时间,t(n),内判定,A,的,TM,。对每个,n,，构造电路,Cn,模拟,M,在长为,n,的输入上的运算。,Cn,的门分成行，每一行对应,M,进行运算的一个格局。每一行用导线连到上一行，指示从上一行的格局能够计算得到自己的格局。,修改,M,使得输入编码为,0,，,1,。,M,在进入接收状态之前，把读写头移到最左单元，写下空格符号。这样就可以指定电路的最后一行的一个门为输出门。,2024/9/21,45,证明,M,在输入,w,上的画面定义,起始格局,第二个格局,第,t(n),个格局,Cell1,1,Cellt(n),1,（接受位置）,状态和读写头下的符号表示为一个单一的复合字符。,通过察看,cellt(n),1,，,就能确定,M,是否已经接受。,每一单元的内容都由上一行的某些单元来决定。,celli-1,j-1,celli-1,j,celli-1,j+1-celli,j,2024/9/21,46,构造电路,Cn,对应画面的每一个单元有多个门，添加灯表示某些门的输出。对于画面的每个单元有,k,盏灯,(k,是,U(XQ),中元素的数目,),。总共,kt(n)2,盏灯。灯表示为：,一个单元只能有一盏灯开着，如果,lighti,j,s,开,着，,celli,j,就,包含符号,s,。,通过考察转移函数，可以确定影响,celli,j,的,三个单元的哪些赋值会使,celli,j,包含,s,。,2024/9/21,47,0,1,0,1,0,1,0,1,v,一盏灯的电路,2024/9/21,48,特殊处理,1,画面左边界和右边界的单元,只有上一行的两个单元可能影响它的内容，修改电路，模拟这种情况。,2,第一行的单元对应起始格局，它们的灯用导线连到输入变量。这些单元的值是由输入字符串,w,决定的。,Light1,1,q,0,1-w,1,light1,1, q,0,0- -w,1,Light1,2,1-w,2,light1,2,0- -w,2,light1,n,1-w,n,light1,n,0- -w,n,第一行中剩余单元对应带子上初始值为空的位置的灯亮。,3,指定输出门为与,lightt(n),1,q,accept,相关联的门。,2024/9/21,49,定理,9.26 cp215,布尔电路是可满足的，如果输入的某一赋值使电路输出,1,。,电路可满足性问题,CIRCUIT-SAT=|C,是可满足的布尔电路,定理,10.26 CIRCUIT-SAT,是,NP,完全的。,1,证明,CIRCUIT-SAT,属于,NP,这是显然的，因为非确定型多项式时间图灵机很容易验证电路是否是可满足的。,2024/9/21,50,2,证明,NP,中的任何语言,A,可归约到,CIRCUIT-SAT,。,思路：,f(w)=,即,w,A,布尔电路,C,是可满足的。,A,属于,NP,存在多项式验证机,V,其输入的形式为,，,c,是证明,x,属于,A,的证书。,构造多项式归约,f,：构造电路,C,模拟,V,，把,w,和,c,的符号作为电路的输入。,若,C,可满足，则存在一个证书，所以,w,A.,若,w,A,则存在一个证书，所以,C,可满足。,考察归约时间：,电路的构造可以在,n,的多项式时间内完成。,验证机的运行时间是,所以构造电路的规模是,O( ),归约的运行时间是,O( ),2024/9/21,51,定理,9.27 CP215,3SAT,是,NP,完全的。（库克,-,列文定理）,思路,:,证明,CIRCUIT-SAT,在多项式时间内归约到,3SAT,。,构造归约：把电路转化为公式 ，,C,可满足,可满足。,2024/9/21,52,构造过程,电路,C,包含输入,x,1,x,l,和门,g,1,g,m,。,从,C,构造包含变量,x,1,x,l,g,1,g,m,的公式 。 变量,x,i,对应,C,的输入导线，变量,g,i,对应门的输出导线。把 的变量标记为,w,1,w,l+m,。,子句的描述：只有当变量的赋值正确地反映了门的功能时，所有的子句才能被满足。,2024/9/21,53,构造满足要求,如果存在满足,C,的赋值，根据,C,在该赋值上的计算历史来给变量,g,i,赋值，就可以得到满足 的赋值。,C,可满足,-,-,可满足,如果存在满足 的赋值，则它就给出了,C,的赋值，且输出值是,1,。,可满足,-,-C,可满足,归约可在多项式时间内完成,计算历史简单，输出规模是输入规模的多项式。,2024/9/21,54,