计算理论16难解性

1、2022-3-2SCU CS Computation1Chap 9 难解性 可以从下列文件获得素材：可以从下列文件获得素材：难解性难解性素材素材.doc2022-3-2SCU CS Computation2难解性的含义：难解性的含义： 若某一计算问题在理论上是可若某一计算问题在理论上是可解的，但解法需要耗费大量的时解的，但解法需要耗费大量的时间或空间，以至于无法在实践中间或空间，以至于无法在实践中应用，则称该问题是难解的。应用，则称该问题是难解的。2022-3-2SCU CS Computation3难解性的形式难解性的形式难解性可以有多种形式：难解性可以有多种形式：例如例如 ： 1、一个大部

2、分时间容易计算但偶尔、一个大部分时间容易计算但偶尔很难算的问题，仅在最坏情况下是难解很难算的问题，仅在最坏情况下是难解的；的； 2、在超级计算机上是易算的，但在、在超级计算机上是易算的，但在PC机上可能需要过量时间的问题机上可能需要过量时间的问题2022-3-2SCU CS Computation4本章的目标本章的目标 证明存在理论上可判定证明存在理论上可判定但实际中不可判定的问题即但实际中不可判定的问题即可判定而难解的问题。可判定而难解的问题。2022-3-2SCU CS Computation5 总之：难解性问题指的是在最坏情总之：难解性问题指的是在最坏情况下复杂性太大，以至于在任何所能想

3、况下复杂性太大，以至于在任何所能想象建造出来的计算机上所耗费的时间都象建造出来的计算机上所耗费的时间都将超过宇宙的余生。将超过宇宙的余生。 例如：例如：SAT问题和所有的问题和所有的NP完全问完全问题。题。2022-3-2SCU CS Computation69.1 层次定理层次定理 层次定理的含义：定理中的每一个都能证明时层次定理的含义：定理中的每一个都能证明时间和空间复杂性类不全相同，它们形成了一个层次间和空间复杂性类不全相同，它们形成了一个层次结构，其中时空界限较大的类比时空界限较小的类结构，其中时空界限较大的类比时空界限较小的类包含更多的语言。包含更多的语言。 例如：层次定理能形式化的

4、证明：图灵机在更例如：层次定理能形式化的证明：图灵机在更多的时间或空间能扩大它所能解的问题类。也就是多的时间或空间能扩大它所能解的问题类。也就是说，图灵机在时间说，图灵机在时间n3 内比内比n2内能判定更多的语言。内能判定更多的语言。2022-3-2SCU CS Computation7层次定理的分类层次定理的分类n空间复杂性层次定理（简单）（简单）n时间复杂性层次定理（复杂）（复杂） 2022-3-2SCU CS Computation8函数函数 f:N N,f(n) =logn 称为空间可称为空间可构造的，如果函数把构造的，如果函数把1n（n个个1的字符串）的字符串） 映射为映射为f(n)

5、的二进制表示，并在空间的二进制表示，并在空间O(f(n)内是可计算的。内是可计算的。 含义：如果存在某个图灵机含义：如果存在某个图灵机M，在在O(f(n)空间内运行，并且在输入空间内运行，并且在输入1n后总能后总能停机，停机时停机，停机时f(n)的二进制表示出现在带子的二进制表示出现在带子上，则上，则f是空间可构造的是空间可构造的定义9.12022-3-2SCU CS Computation9 通常出现的不小于通常出现的不小于logn的函数都是空的函数都是空间可构造的，例如间可构造的，例如logn ，nlogn ，n2. . n2是空间可构造的，因为机器以是空间可构造的，因为机器以1 1n为输

6、为输入，通过数入，通过数1 1的数目得到的数目得到n的二进制形式，的二进制形式，采用标推的方法将采用标推的方法将n自乘，输出。全部空间自乘，输出。全部空间消耗是消耗是O( (n) )，当然也是，当然也是O( (n2) ) 。 例9.22022-3-2SCU CS Computation10定理9.3 空间层次定理 对任何空间可构造函数对任何空间可构造函数f:N N，存在语言存在语言A，在空间在空间O（f（n）内可判内可判定，但不能在空间定，但不能在空间o（f（n） 证明思路证明思路 必须显示一个语言必须显示一个语言A具有具有两个性质：第一，两个性质：第一，A在空间在空间O（f（n）内可判定；第

7、二，内可判定；第二，A不能在空间不能在空间o（f（n）判定。判定。2022-3-2SCU CS Computation11 推论9.4 空间层次定理 对任何两个函数对任何两个函数f1 ， f2：N N,其中其中f1（n）等于等于o（f2（n），）， f2是空间可构是空间可构造的，有造的，有SPACE（f1（n）真包含于真包含于SPACE（f2（n） 该推论的作用能够把不同的空间复杂该推论的作用能够把不同的空间复杂性类分开。性类分开。2022-3-2SCU CS Computation12 推论9.5 对任意两个实数对任意两个实数0r1 r2, ,有有SPACE(n r1)真包含于真包含于SPA

8、CE(n r2)也可以用空间层次定理来分离前也可以用空间层次定理来分离前面碰到的的两个空间复杂性类。面碰到的的两个空间复杂性类。2022-3-2SCU CS Computation13 推论9.6 NLNL真包含于真包含于PSPACEPSPACE证明：萨维奇定理说明证明：萨维奇定理说明NL不真包含于不真包含于SPACE(2n ),空间层次定理说明空间层次定理说明SPACE(2n )真包含于真包含于SPACE(n), ,所以推所以推论成立。论成立。 2022-3-2SCU CS Computation14 推论9.7 PSPACEPSPACE真包含于真包含于EXPSPACEEXPSPACE 意义

9、：判定过程必须消耗多于多项式意义：判定过程必须消耗多于多项式的空间。的空间。2022-3-2SCU CS Computation15 定义9.8函数函数 t:N N,t(n) =nlogn 称为时间可称为时间可构造的，如果函数把构造的，如果函数把1 1n（n个个1 1的字符串）的字符串） 映射为映射为t(n)的二进制表示，并在时间的二进制表示，并在时间O(t(n)内是可计算的。内是可计算的。 含义：如果存在某个图灵机含义：如果存在某个图灵机M，在时在时间间O(t(n)内运行，而且在输入内运行，而且在输入1 1n上启动后上启动后总能停机，停机时总能停机，停机时t(n)的二进制表示出现的二进制表示

10、出现在带子上，则在带子上，则t是时间可构造的。是时间可构造的。2022-3-2SCU CS Computation16 通常出现的不小于通常出现的不小于nlogn的函数都是时的函数都是时间可构造的，例如间可构造的，例如nlogn ， , ,n2 2以及以及2 2n 。 是时间可构造的，首先设计一个是时间可构造的，首先设计一个TM，以二进制计算以二进制计算l l的个数。为此该的个数。为此该TM沿着带子移动沿着带子移动一个二进制计数器，每到一个输入位置就把它加一个二进制计数器，每到一个输入位置就把它加1，直至输入的末端。因为对于，直至输入的末端。因为对于n个输入位置的每个输入位置的每一个都需要消耗

11、一个都需要消耗O(logn)步，所以这部分工作消步，所以这部分工作消耗耗O(nlogn)步。然后，从步。然后，从n的二进制表示中计算的二进制表示中计算出的出的 二进制形式。因为涉及的数的长度是二进制形式。因为涉及的数的长度是O(logn) ，所以任何合理的计算方法都将消耗时，所以任何合理的计算方法都将消耗时间间O(nlogn) 。 例9.9n nn nn n2022-3-2SCU CS Computation17定理9.10 时间层次定理 对于任何时间可构造函数对于任何时间可构造函数t:N N，存在语言存在语言A，在时间在时间O（t（n）内可判定，内可判定，但在时间但在时间o（t（n）/log

12、t(n)内不可判定内不可判定 证明思路证明思路 类似类似10.310.3。2022-3-2SCU CS Computation18 推论9.11 对任何两个函数对任何两个函数t1 ， t2：其中其中t1（n）等于等于o(t2（n）/logt2 (n)， t2是时间可是时间可构造的，有构造的，有TIME(t1（n）)真包含于真包含于TIME(t2（n）)。 2022-3-2SCU CS Computation19 推论9.12 对任意两个实数对任意两个实数0r1 r2 , 有有TIME(n r1 )真包含于真包含于SPACE(n r2 )2022-3-2SCU CS Computation20

13、推论9.13P真包含于真包含于EXPTIME2022-3-2SCU CS Computation21指数空间完全性指数空间完全性证明一个具体的语言事实难解需要分两步：证明一个具体的语言事实难解需要分两步： 第一：图灵机在第一：图灵机在EXPSPACE内比在内比在PSPACE内判定更多的语言；内判定更多的语言； 第二：证明有关广义正则表达式的一第二：证明有关广义正则表达式的一个具体的语言是个具体的语言是EXPSPACE完全的，即不完全的，即不能在多项式时间、也不能在多项式空间内能在多项式时间、也不能在多项式空间内判定。判定。2022-3-2SCU CS Computation22定义定义9.14

14、9.14语言语言B是是EXPSPACE完全的，当且仅当：完全的，当且仅当： （1）B EXPSPACE;并且并且 （2）EXPSPACE中的每个中的每个A都是多项都是多项式时间可归约到式时间可归约到B。2022-3-2SCU CS Computation23广义正则表达式广义正则表达式 正则表达式是正则表达式是， 以及字母表中的符以及字母表中的符号经过有限次正则运算（并、连接和星）得号经过有限次正则运算（并、连接和星）得到的表达式。到的表达式。 广义正则表达式是允许指数运算（广义正则表达式是允许指数运算（）的正则表达式。的正则表达式。Rk = Rk = R R REQREX =|Q和和R是等价

15、的广义是等价的广义正则表达式正则表达式k2022-3-2SCU CS Computation24定理定理9.159.15EQREX 是是EXPSPACE完全的。完全的。 证明思路：在度量判定证明思路：在度量判定 EQREX 的复杂性的复杂性时，假设所有指数都写成二进制整数。表时，假设所有指数都写成二进制整数。表达式的长度是它包含的所有符号的总数。达式的长度是它包含的所有符号的总数。2022-3-2SCU CS Computation25.2 相对化2022-3-2SCU CS Computation261. 研究的主要的内容给出有力证据否定用对角化法解决给出有力证据否定用对角化法解决P与与NP

16、问题的可能性问题的可能性.2022-3-2SCU CS Computation272. 几个基本概念和定义(1)谕示 （可比喻为 一块 超级芯片 ， 外星人的智能礼物） P138:语言B的一个谕示是一个能够报告某个串是否为B的成员的外部装置. 一个谕示是一个语言A.(2)谕示图灵机MA是通常的图灵机附加一条谕示带, 每当M在谕示带上写下一个字符串时,就能在一步计算内得知这个字符串是否属于A.2022-3-2SCU CS Computation282. 几个基本概念和定义(续)(3)PA采用谕示A的多项式时间谕示图灵机可判定的语言类.(4)NPA采用谕示A的非确定多项式时间谕示图灵机可判定的语言

17、类.2022-3-2SCU CS Computation293. 举例(1)NPP(1)NPPSATSAT 含义含义: :相对于可满足性问题的多项式时间计相对于可满足性问题的多项式时间计算包含了算包含了NPNP问题的全部问题的全部. .(2)(2)COCONP PNP PSATSAT(3)(3)极小公式极小公式: :如果一个公式没有更小的公式与如果一个公式没有更小的公式与之等价之等价, ,则称它为极小的则称它为极小的. .2022-3-2SCU CS Computation30NONMIN-FORMULA=NONMIN-FORMULA=| 不是极小布尔公式不是极小布尔公式 NP OR NP?

18、NPSAT(1)等价问题属于等价问题属于CONP(2)谕示谕示SAT检查是否有检查是否有更小的等价公式更小的等价公式.是则接是则接受受.2022-3-2SCU CS Computation314. 对角化方法的局限(1)对角化方法的核心:是一台图灵机对另一台图灵机的模拟.(2)结论:凡是仅用对角化方法证明的关于图灵机的定理,当给两台机器以相同谕示的时候,仍然成立.2022-3-2SCU CS Computation32问题n 能否用对角化方法证明P与NP不同,亦即它们相对于任何谕示都不同? n能否依据简单的模拟证明说明P与NP相等,即证明它们对于任何谕示都是相等的?2022-3-2SCU CS

19、 Computation331) 存在谕示A使得PA NPA2) 存在谕示B使得PB = NPB上述定理表明不太可能用对角化方法和简单模拟的证明来解决P与NP问题.2022-3-2SCU CS Computation34证明思路证明思路(2)只要令B是PSPACE完全问题如TQBF即可. NPTQBFNPSPACE PSPACE PTQBF因为可以把非确定型多项式时间谕示机器转变为非确定型多项式空间机器.萨维奇定理因为TQBF是PSAPCE完全的.2022-3-2SCU CS Computation35 构造谕示A.设计A使得NPA中的某个语言LA可以证明需要蛮力搜索,因而LA不可能属于PA.

20、因此可以得出PANPA的结论. LA=|x A |x| = | NPA PA2022-3-2SCU CS Computation36关 键n构造谕示A: 经过所有构造步骤以后状态没有确定下来的字符串声明为不在A中.亦即没有多项式时间谕示机器能够以谕示A判定LA.2022-3-2SCU CS Computation379.3 电路复杂性电路复杂性2022-3-2SCU CS Computation38布尔电路布尔电路n定义.20 n布尔电路是由导线连接的门和输入的集合。n门的三种形式：与、或、非门n布尔函数：AND、OR、NOTn门：布尔函数处理器输入输出2022-3-2SCU CS Compu

21、tation39布尔电路示例布尔电路示例x1输出门x2x3输入变量0 x1输出1x20 x3输入100111用函数描述布尔电路的输入/输出：Fc:0,1n-0,1Fc(a1,an)=b2022-3-2SCU CS Computation40例例9.21 奇偶函数奇偶函数parityn:0,1n-0,1输出输出1，当且仅当输入变，当且仅当输入变量中有奇数个量中有奇数个1x1x2x3x4实现例10.21 布尔电路2022-3-2SCU CS Computation41电路族电路族n定义9.22 n一个电路族C是电路的一个无穷列表（C0， C1， C2，), 其中Cn有n个输入变量。n称C在0，1上

22、判定语言A，如果对于每个字符串w，wA 当且仅当Cn(w)=1,其中n是w的长度。n电路的规模-所包含门的数目n规模复杂度：一个电路族（C0， C1， C2，)的规模复杂度是一个函数f:N-N, 其中f(n)是Cn的规模n深度及复杂度：电路的深度是从输入变量到输出门的最长路径的长度。n规模极小、深度极小2022-3-2SCU CS Computation42电路复杂度电路复杂度n定义9.23 n语言的电路规模复杂度是该语言的极小电路族的规模复杂度。n语言的电路深度复杂度是该语言的极小电路族的深度复杂度。2022-3-2SCU CS Computation43定理定理9.25 cp212n定理1

23、0.25设t:N-N是一个函数，t(n) n。若 ，则A的电路复杂度为 。n时间复杂度小的语言，电路复杂度也小)( ntTimeA)(2ntO2022-3-2SCU CS Computation44证明思路证明思路nM是在时间t(n)内判定A的TM。对每个n，构造电路Cn模拟M在长为n的输入上的运算。nCn的门分成行，每一行对应M进行运算的一个格局。每一行用导线连到上一行，指示从上一行的格局能够计算得到自己的格局。n修改M使得输入编码为0，1。nM在进入接收状态之前，把读写头移到最左单元，写下空格符号。这样就可以指定电路的最后一行的一个门为输出门。2022-3-2SCU CS Computat

24、ion45证明证明M在输入w上的画面定义起始格局第二个格局第t(n)个格局Cell1,1Cellt(n),1（接受位置） 状态和读写头下的符号表示为一个单一的复合字符。 通过察看cellt(n),1，就能确定M是否已经接受。 每一单元的内容都由上一行的某些单元来决定。 celli-1,j-1,celli-1,j,celli-1,j+1-celli,j2022-3-2SCU CS Computation46 构造电路Cn对应画面的每一个单元有多个门，添加灯表示某些门的输出。对于画面的每个单元有k盏灯(k是U(XQ)中元素的数目)。总共kt(n)2盏灯。灯表示为：一个单元只能有一盏灯开着，如果li

25、ghti,j,s开着，celli,j就包含符号s。通过考察转移函数，可以确定影响celli,j的三个单元的哪些赋值会使celli,j包含s。)(),(,1 ,Qsntjisjilight2022-3-2SCU CS Computation4701010101v一盏灯的电路2022-3-2SCU CS Computation48特殊处理1 画面左边界和右边界的单元,只有上一行的两个单元可能影响它的内容，修改电路，模拟这种情况。2 第一行的单元对应起始格局，它们的灯用导线连到输入变量。这些单元的值是由输入字符串w决定的。Light1,1,q01-w1 light1,1, q00- -w1Light

26、1,2,1-w2 light1,2,0- -w2 light1,n,1-wn light1,n,0- -wn第一行中剩余单元对应带子上初始值为空的位置的灯亮。3指定输出门为与lightt(n),1,qaccept相关联的门。2022-3-2SCU CS Computation49定理定理9.26 cp215n布尔电路是可满足的，如果输入的某一赋值使电路布尔电路是可满足的，如果输入的某一赋值使电路输出输出1。n电路可满足性问题电路可满足性问题CIRCUIT-SAT=|C是可满足的布尔电路是可满足的布尔电路n定理定理10.26 CIRCUIT-SAT是是NP完全的。完全的。n1 证明证明CIRCUIT-SAT属于属于NPn这是显然的，因为非确定型多项式时间图灵机这是显然的，因为非确定型多项式时间图灵机很容易验证电路是否是可满足的。很容易验证电路是否是可满足的。 2022-3-2SCU CS Computation502 证明NP中的任何语言A可归约到