计算理论16难解性ppt课件.ppt

《计算理论16难解性ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chap9难解性可以从下列文件获得素材：难解性素材.doc2021/8/211SCUCSComputation难解性的含义：若某一计算问题在理论上是可解的，但解法需要耗费大量的时间或空间，以至于无法在实践中应用，则称该问题是难解的。难解性的形式难解性可以有多种形式：例如：1、一个大部分时间容易计算但偶尔很难算的问题，仅在最坏情况下是难解的；2、在超级计算机上是易算的，但在PC机上可能需要过量时间的问题本章的目标证明存在理论上可判定但实际中不可判定的问题即可判定而难解的问题。总之：难解性问题指的是在最坏情况下复杂性太大，以至于在任何所能想象建造出来的计算机上所耗费的时间都将超过宇宙

2、的余生。例如：SAT问题和所有的NP完全问题。9.1层次定理层次定理的含义：定理中的每一个都能证明时间和空间复杂性类不全相同，它们形成了一个层次结构，其中时空界限较大的类比时空界限较小的类包含更多的语言。例如：层次定理能形式化的证明：图灵机在更多的时间或空间能扩大它所能解的问题类。也就是说，图灵机在时间n3内比n2内能判定更多的语言。层次定理的分类空间复杂性层次定理（简单）时间复杂性层次定理（复杂）函数f:NN,f(n)>=logn称为空间可构造的，如果函数把1n（n个1的字符串）映射为f(n)的二进制表示，并在空间O(f(n))内是可计算的。含义：如果存在某个图灵机M，在O(f

3、(n))空间内运行，并且在输入1n后总能停机，停机时f(n)的二进制表示出现在带子上，则f是空间可构造的定义9.1通常出现的不小于logn的函数都是空间可构造的，例如logn，nlogn，n2.n2是空间可构造的，因为机器以1n为输入，通过数1的数目得到n的二进制形式，采用标推的方法将n自乘，输出。全部空间消耗是O(n)，当然也是O(n2)。例9.2定理9.3空间层次定理对任何空间可构造函数f:NN，存在语言A，在空间O（f（n））内可判定，但不能在空间o（f（n））证明思路必须显示一个语言A具有两个性质：第一，A在空间O（f（n））内可判定；第二，A不能在空间o（f（n））判定

4、。推论9.4空间层次定理对任何两个函数f1，f2：NN,其中f1（n）等于o（f2（n）），f2是空间可构造的，有SPACE（f1（n））真包含于SPACE（f2（n））该推论的作用能够把不同的空间复杂性类分开。推论9.5对任意两个实数0≤r1＜r2,有SPACE(nr1)真包含于SPACE(nr2)也可以用空间层次定理来分离前面碰到的的两个空间复杂性类。推论9.6NL真包含于PSPACE证明：萨维奇定理说明NL不真包含于SPACE(㏒2n),空间层次定理说明SPACE(㏒2n)真包含于SPACE(n),所以推论成立。推论9.7PSPACE真包含于EXPSPACE意义：判定过程必

5、须消耗多于多项式的空间。定义9.8函数t:NN,t(n)>=nlogn称为时间可构造的，如果函数把1n（n个1的字符串）映射为t(n)的二进制表示，并在时间O(t(n))内是可计算的。含义：如果存在某个图灵机M，在时间O(t(n))内运行，而且在输入1n上启动后总能停机，停机时t(n)的二进制表示出现在带子上，则t是时间可构造的。通常出现的不小于nlogn的函数都是时间可构造的，例如nlogn，,n2以及2n。是时间可构造的，首先设计一个TM，以二进制计算l的个数。为此该TM沿着带子移动一个二进制计数器，每到一个输入位置就把它加1，直至输入的末端。因为对于n个输入位置的每一个都需

6、要消耗O(logn)步，所以这部分工作消耗O(nlogn)步。然后，从n的二进制表示中计算出的[]二进制形式。因为涉及的数的长度是O(logn)，所以任何合理的计算方法都将消耗时间O(nlogn)。例9.9定理9.10时间层次定理对于任何时间可构造函数t:NN，存在语言A，在时间O（t（n））内可判定，但在时间o（t（n）/logt(n))内不可判定证明思路类似10.3。推论9.11对任何两个函数t1，t2：其中t1（n）等于o(t2（n）/logt2(n))，t2是时间可构造的，有TIME(t1（n）)真包含于TIME(t2（n）)。推论9.12对任意两个实数0≤r1＜r2,有

7、TIME(nr1)真包含于SPACE(nr2)推论9.13P真包含于EXPTIME指数空间完全性证明一个具体的语言事实难解需要分两步：第一：图灵机在EXPSPACE内比在PSPACE内判定更多的语言；第二：证明有关广义正则表达式的一个具体的语言是EXPSPACE完全的，即不能在多项式时间、也不能在多项式空间内判定。2021/8/2121SCUCSComputation定义9.14语言B是EXPSPACE完全的，当且仅当：（1）B∈EXPSPACE;并且（2）EXPSPACE中的每