计算理论16难解性技术总结.ppt

Chap 9 难解性;难解性的含义： 若某一计算问题在理论上是可解的，但解法需要耗费大量的时间或空间，以至于无法在实践中应用，则称该问题是难解的。;难解性的形式;本章的目标; 总之：难解性问题指的是在最坏情况下复杂性太大，以至于在任何所能想象建造出来的计算机上所耗费的时间都将超过宇宙的余生。 例如：SAT问题和所有的NP完全问题。;9.1 层次定理;层次定理的分类;函数 f:N N,f(n) =logn 称为空间可构造的，如果函数把1n（n个1的字符串） 映射为f(n)的二进制表示，并在空间O(f(n))内是可计算的。 含义：如果存在某个图灵机M，在O(f(n))空间内运行，并且在输入1n后总能停机，停机时f(n)的二进制表示出现在带子上，则f是空间可构造的; 通常出现的不小于logn的函数都是空间可构造的，例如logn ，nlogn ，n2. n2是空间可构造的，因为机器以1n为输入，通过数1的数目得到n的二进制形式，采用标推的方法将n自乘，输出。全部空间消耗是O(n)，当然也是O(n2) 。 ;定理9.3 空间层次定理; ; ; ; ; ; 通常出现的不小于nlogn的函数都是时间可构造的，例如nlogn ， ,n2以及2n 。 是时间可构造的，首先设计一个TM，以二进制计算l的个数。为此该TM沿着带子移动一个二进制计数器，每到一个输入位置就把它加1，直至输入的末端。因为对于n个输入位置的每一个都需要消耗O(logn)步，所以这部分工作消耗O(nlogn)步。然后，从n的二进制表示中计算出的[ ]二进制形式。因为涉及的数的长度是O(logn) ，所以任何合理的计算方法都将消耗时间O(nlogn) 。 ;定理9.10 时间层次定理; ; ; ;指数空间完全性;定义9.14;广义正则表达式;定理9.15;９.2 相对化;1. 研究的主要的内容;2. 几个基本概念和定义;2. 几个基本概念和定义(续);3. 举例;NONMIN-FORMULA={Φ| Φ不是极小布尔公式} ;4. 对角化方法的局限;问题;定理９.19 1) 存在谕示A使得PA NPA 2) 存在谕示B使得PB = NPB 上述定理表明不太可能用对角化方法和简单模拟的证明来解决P与NP问题.;证明思路; 构造谕示A.设计A使得NPA中的某个语言LA可以证明需要蛮力有哪些信誉好的足球投注网站,因而LA不可能属于PA.因此??以得出PANPA的结论. LA={ω|?x ∈ A [|x| = |ω|]} ;关 键;9.3 电路复杂性;布尔电路;布尔电路示例;例9.21 奇偶函数parityn:{0,1}n--{0,1}输出1，当且仅当输入变量中有奇数个1;电路族;电路复杂度;定理9.25 cp212;证明思路;证明; 构造电路Cn 对应画面的每一个单元有多个门，添加灯表示某些门的输出。对于画面的每个单元有k盏灯(k是гU(гXQ)中元素的数目)。总共kt(n)^2盏灯。灯表示为： 一个单元只能有一盏灯开着，如果light[i,j,s]开着，cell[i,j]就包含符号s。 通过考察转移函数，可以确定影响cell[i,j]的三个单元的哪些赋值会使cell[i,j]包含s。;0;;定理9.26 cp215;2 证明NP中的任何语言A可归约到CIRCUIT-SAT。 思路： f(w)=C即w∈ A ??布尔电路C是可满足的。 A属于NP,存在多项式验证机V,其输入的形式为x,c，c是证明x属于A的证书。 构造多项式归约f：构造电路C模拟V，把w和c的符号作为电路的输入。 若C可满足，则存在一个证书，所以w∈A. 若w∈A,则存在一个证书，所以C可满足。 考察归约时间： 电路的构造可以在n的多项式时间内完成。 验证机的运行时间是 ,所以构造电路的规模是O( ) 归约的运行时间是O( ) ;定理9.27 CP215;构造过程 电路C包含输入x1,…,xl和门g1,…,gm。 从C构造包含变量x1,…,xl,g1,…,gm的公式 。 变量xi对应C的输入导线，变量gi对应门的输出导线。把 的变量标记为w1,…,wl+m。 子句的描述：只有当变量的赋值正确地反映了门的功能时，所有的子句才能被满足。 ;构造满足要求 如果存在满足C的赋值，根据C在该赋值上的计算历史来给变量gi赋值，就可以得到满足 的赋值。C可满足-- 可满足 如果存在满足 的赋值，则它就给出了C的赋值，且输出值是1。可满足--C可满足