计算理论16难解性

2019/12/[e-mail]1/54Chap9难解性可以从下列文件获得素材：难解性素材.doc2019/12/[e-mail]2/54难解性的含义：若某一计算问题在理论上是可解的，但解法需要耗费大量的时间或空间，以至于无法在实践中应用，则称该问题是难解的。2019/12/[e-mail]3/54难解性的形式难解性可以有多种形式：例如：1、一个大部分时间容易计算但偶尔很难算的问题，仅在最坏情况下是难解的；2、在超级计算机上是易算的，但在PC机上可能需要过量时间的问题2019/12/[e-mail]4/54本章的目标证明存在理论上可判定但实际中不可判定的问题即可判定而难解的问题。2019/12/[e-mail]5/54总之：难解性问题指的是在最坏情况下复杂性太大，以至于在任何所能想象建造出来的计算机上所耗费的时间都将超过宇宙的余生。例如：SAT问题和所有的NP完全问题。2019/12/[e-mail]6/549.1层次定理层次定理的含义：定理中的每一个都能证明时间和空间复杂性类不全相同，它们形成了一个层次结构，其中时空界限较大的类比时空界限较小的类包含更多的语言。例如：层次定理能形式化的证明：图灵机在更多的时间或空间能扩大它所能解的问题类。也就是说，图灵机在时间n3内比n2内能判定更多的语言。2019/12/[e-mail]7/54层次定理的分类空间复杂性层次定理（简单）时间复杂性层次定理（复杂）2019/12/[e-mail]8/54函数f:NN,f(n)=logn称为空间可构造的，如果函数把1n（n个1的字符串）映射为f(n)的二进制表示，并在空间O(f(n))内是可计算的。含义：如果存在某个图灵机M，在O(f(n))空间内运行，并且在输入1n后总能停机，停机时f(n)的二进制表示出现在带子上，则f是空间可构造的定义9.12019/12/[e-mail]9/54通常出现的不小于logn的函数都是空间可构造的，例如logn，nlogn，n2.n2是空间可构造的，因为机器以1n为输入，通过数1的数目得到n的二进制形式，采用标推的方法将n自乘，输出。全部空间消耗是O(n)，当然也是O(n2)。例9.22019/12/[e-mail]10/54定理9.3空间层次定理对任何空间可构造函数f:NN，存在语言A，在空间O（f（n））内可判定，但不能在空间o（f（n））证明思路必须显示一个语言A具有两个性质：第一，A在空间O（f（n））内可判定；第二，A不能在空间o（f（n））判定。2019/12/[e-mail]11/54推论9.4空间层次定理对任何两个函数f1，f2：NN,其中f1（n）等于o（f2（n）），f2是空间可构造的，有SPACE（f1（n））真包含于SPACE（f2（n））该推论的作用能够把不同的空间复杂性类分开。2019/12/[e-mail]12/54推论9.5对任意两个实数0≤r1＜r2,有SPACE(nr1)真包含于SPACE(nr2)也可以用空间层次定理来分离前面碰到的的两个空间复杂性类。2019/12/[e-mail]13/54推论9.6NL真包含于PSPACE证明：萨维奇定理说明NL不真包含于SPACE(㏒2n),空间层次定理说明SPACE(㏒2n)真包含于SPACE(n),所以推论成立。2019/12/[e-mail]14/54推论9.7PSPACE真包含于EXPSPACE意义：判定过程必须消耗多于多项式的空间。2019/12/[e-mail]15/54定义9.8函数t:NN,t(n)=nlogn称为时间可构造的，如果函数把1n（n个1的字符串）映射为t(n)的二进制表示，并在时间O(t(n))内是可计算的。含义：如果存在某个图灵机M，在时间O(t(n))内运行，而且在输入1n上启动后总能停机，停机时t(n)的二进制表示出现在带子上，则t是时间可构造的。2019/12/[e-mail]16/54通常出现的不小于nlogn的函数都是时间可构造的，例如nlogn，,n2以及2n。是时间可构造的，首先设计一个TM，以二进制计算l的个数。为此该TM沿着带子移动一个二进制计数器，每到一个输入位置就把它加1，直至输入的末端。因为对于n个输入位置的每一个都需要消耗O(logn)步，所以这部分工作消耗O(nlogn)步。然后，从n的二进制表示中计算出的[]二进制形式。因为涉及的数的长度是O(logn)，所以任何合理的计算方法都将消耗时间O(nlogn)。例9.9nnnnnn2019/12/[e-mail]17/54定理9.10时间层次定理对于任何时间可构造函数t:NN，存在语言A，在时间O（t（n））内可判定，但在时间o（t（n）/logt(n))内不可判定证明思路类似10.3。2019/12/[e-mail]18/54推论9.11对任何两个函数t1，t2：其中t1（n）等于o(t2（n）/logt2(n))，t2是时间可构造的，有TIME(t1（n）)真包含于TIME(t2（n）)。2019/12/[e-mail]19/54推论9.12对任意两个实数0≤r1＜r2,有TIME(nr1)真包含于SPACE(nr2)2019/12/[e-mail]20/54推论9.13P真包含于EXPTIME2019/12/[e-mail]21/54指数空间完全性证明一个具体的语言事实难解需要分两步：第一：图灵机在EXPSPACE内比在PSPACE内判定更多的语言；第二：证明有关广义正则表达式的一个具体的语言是EXPSPACE完全的，即不能在多项式时间、也不能在多项式空间内判定。2019/12/[e-mail]22/54定义9.14语言B是EXPSPACE完全的，当且仅当：（1）B∈EXPSPACE;并且（2）EXPSPACE中的每个A都是多项式时间可归约到B。2019/12/[e-mail]23/54广义正则表达式正则表达式是，ε以及字母表中的符号经过有限次正则运算（并、连接和星）得到的表达式。广义正则表达式是允许指数运算（↑）的正则表达式。Rk=R↑k=R◦R◦…◦REQREX↑={Q,R|Q和R是等价的广义正则表达式}k2019/12/[e-mail]24/54定理9.15EQREX↑是EXPSPACE完全的。证明思路：在度量判定EQREX↑的复杂性时，假设所有指数都写成二进制整数。表达式的长度是它包含的所有符号的总数。2019/12/[e-mail]25/54９.2相对化2019/12/[e-mail]26/541.研究的主要的内容给出有力证据否定用对角化法解决P与NP问题的可能性.2019/12/[e-mail]27/542.几个基本概念和定义(1)谕示（可比喻为一块超级芯片，外星人的智能礼物）P138:语言B的一个谕示是一个能够报告某个串是否为B的成员的外部装置.一个谕示是一个语言A.(2)谕示图灵机MA是通常的图灵机附加一条谕示带,每当M在谕示带上写下一个字符串时,就能在一步计算内得知这个字符串是否属于A.2019/12/[e-mail]28/542.几个基本概念和定义(续)(3)PA采用谕示A的多项式时间谕示图灵机可判定的语言类.(4)NPA采用谕示A的非确定多项式时间谕示图灵机可判定的语言类.2019/12/[e-mail]29/543.举例(1)NP⊆PSAT含义:相对于可满足性问题的多项式时间计算包含了NP问题的全部.(2)CONP⊆PSAT(3)极小公式:如果一个公式没有更小的公式与之等价,则称它为极小的.2019/12/[e-mail]30/54NONMIN-FORMULA={Φ|Φ不是极小布尔公式}∈NPOR∉NP?∈NPSAT(1)等价问题属于CONP(2)谕示SAT检查是否有更小的等价公式.是则接受.2019/12/[e-mail]31/544.对角化方法的局限(1)对角化方法的核心:是一台图灵机对另一台图灵机的模拟.(2)结论:凡是仅用对角化方法证明的关于图灵机的定理,当给两台机器以相同谕示的时候,仍然成立.2019/12/[e-mail]32/54问题能否用对角化方法证明P与NP不同,亦即它们相对于任何谕示都不同?能否依据简单的模拟证明说明P与NP相等,即证明它们对于任何谕示都是相等的?2019/12/[e-mail]33/54定理９.191)存在谕示A使得PANPA2)存在谕示B使得PB=NPB上述定理表明不太可能用对角化方法和简单模拟的证明来解决P与NP问题.2019/12/[e-mail]34/54证明思路(2)只要令B是PSPACE完全问题如TQBF即可.NPTQBF⊆NPSPACE⊆PSPACE⊆PTQBF因为可以把非确定型多项式时间谕示机器转变为非确定型多项式空间机器.萨维奇定理因为TQBF是PSAPCE完全的.2019/12/[e-mail]35/54构造谕示A.设计A使得NPA中的某个语言LA可以证明需要蛮力搜索,因而LA不可能属于PA.因此可以得出PANPA的结论.LA={ω|∃x∈A[|x|=|ω|]}∈NPA∉PA2019/12/[e-mail]36/54关键构造谕示A:经过所有构造步骤以后状态没有确定下来的字符串声明为不在A中.亦即没有多项式时间谕示机器能够以谕示A判定LA.2019/12/[e-mail]37/549.3电路复杂性2019/12/[e-mail]38/54布尔电路定义９.20布尔电路是由导线连接的门和输入的集合。门的三种形式：与、或、非门布尔函数：AND、OR、NOT门：布尔函数处理器输入输出2019/12/[e-mail]39/54布尔电路示例x1输出门x2x3输入变量0x1输出1x20x3输入100111用函数描述布尔电路的输入/输出：Fc:{0,1}n--{0,1}Fc(a1,…,an)=b2019/12/[e-mail]40/54例9.21奇偶函数parityn:{0,1}n--{0,1}输出1，当且仅当输入变量中有奇数个1x1x2x3x4实现例10.21布尔电路2019/12/[e-mail]41/54电路族定义9.22一个电路族C是电路的一个无穷列表（C0，C1，C2，…),其中Cn有n个输入变量。称C在{0，1}上判定语言A，如果对于每个字符串w，wA当且仅当Cn(w)=1,其中n是w的长度。电路的规模-所包含门的数目规模复杂度：一个电路族（C0，C1，C2，…)的规模复杂度是一个函数f:N-N,其中f(n)是Cn的规模深度及复杂度：电路的深度是从输入变量到输出门的最长路径的长度。规模