第7周 计算复杂性理论理论计算机科学基础1理论计算机科学基础2第3部分 复杂性理论第8章 时间复杂性第9章 空间复杂性第10章 难解性第11章 复杂性理论高级专题理论计算机科学基础3第8章 时间复杂性度量复杂性度量复杂性O( ),o( )记号记号 算法分析算法分析模型间复杂性关系模型间复杂性关系P类、类、NP类类P=?NP问题问题coNP类、类、EXP类类2024/7/25理论计算机科学基础第12讲4第9章 空间复杂性萨维奇定理萨维奇定理PSPACE类类L类类, NL类类NL=coNL2024/7/25理论计算机科学基础第14讲5第10章 难解性层次定理层次定理多项式层次多项式层次(第第11章章)理论计算机科学基础6重要的复杂性类和计算问题PNPcoNPEXPPSPACENLLTQBFSATPATHPH函数的阶理论计算机科学基础7理论计算机科学基础8O()设设f和和g是函数是函数, f,g:NR+. 若若 c,n0, n n0, f(n) cg(n), 则说则说 f(n)=O(g(n), 或或g是是f的的(渐进渐进)上界上界.gfcg理论计算机科学基础9例例例8.3: 设设f(n)=5n3+2n2+22n+6. 则则 (1) f(n)=O(n3). (2) f(n)=O(n4). (3) f(n) O(n2). 例例8.4: f(n)=3nlog2n+5nlog2log2n+2. 则则 f(n)=O(nlog n).理论计算机科学基础10o()f(n)=o(g(n): 例例8.6: 1) 2) n=o(nloglogn) 3) nloglogn=o(nlogn) 4) nlogn=o(n2) 5) n2=o(n3)理论计算机科学基础11多项式界, 指数界多项式界多项式界: nO(1)n0.1, n0.99, n, n1.1, n2, n2.57, n3, n10, n100, 指数界指数界: 理论计算机科学基础12多项式与指数的区别多项式与指数在增长率上多项式与指数在增长率上 有巨大差异有巨大差异当当n=1000时时, n3=10亿亿(尚可处理尚可处理) 2n宇宙中原子数宇宙中原子数多项式有稳定性多项式有稳定性对加对加,减减,乘乘,除除,合成封闭合成封闭计算模型互相模拟的开销计算模型互相模拟的开销 是多项式的是多项式的时间复杂性、时间复杂性类理论计算机科学基础13理论计算机科学基础14DTM运行时间设设M是处处停机的是处处停机的DTM. timeM: *N, timeM(x)=M在输入在输入x上上 的运行步数的运行步数运行时间由运行时间由输入输入确定确定timeM: NN, timeM(n)=M在长度为在长度为n的的 输入上的运行步数输入上的运行步数运行时间由运行时间由输入长度输入长度来确定来确定 * n理论计算机科学基础15时间复杂性timeM: NN, timeM(n)=M在长度为在长度为n的的 输入上的运行步数输入上的运行步数timeM(n)是是M的时间的时间复杂性复杂性(度度)输入长度输入长度运行时间运行时间理论计算机科学基础16最坏情形,平均情形最坏情形最坏情形复杂性复杂性timeM(n)=M在长度为在长度为n的的 输入上的输入上的最大最大运行步数运行步数平均情形平均情形复杂性复杂性timeM(n)=M在长度为在长度为n的的 输入上的输入上的平均平均运行步数运行步数本课只讨论最坏情形复杂性本课只讨论最坏情形复杂性理论计算机科学基础17输入长度,输入规模例例: 图图G=顶点表和边表顶点表和边表: n=|V|, m=|E|=O(n2) | = O(|V| log|V|+|E| 2log|V|) = O(nlogn+m2logn) = O(n2logn) = O(n3)邻接矩阵邻接矩阵: O(n2)输入长度与编码有关输入长度与编码有关输入规模输入规模(问题中的自然参数问题中的自然参数) 与编码无关与编码无关要求二者是多项式相关的要求二者是多项式相关的理论计算机科学基础18算法分析算法分析算法分析: 确定算法的确定算法的 (时间时间)复杂性复杂性例例: A = 0k1k | k 0 单带单带DTM M1: O(n2)单带单带DTM M2: O(nlogn)单带单带DTM在在o(nlogn)时间内时间内 只能识别正则语言只能识别正则语言双带双带DTM M3: O(n)理论计算机科学基础19M1M1=“对输入串对输入串w: 1) 扫描带扫描带,若在若在1右边发现右边发现0, 就就拒绝拒绝; 2) 若若0和和1都在带上都在带上, 就重复下一步就重复下一步; 3) 扫描带扫描带, 删除一个删除一个0和一个和一个1; 4) 若所有若所有1被删除后还有被删除后还有0, 或所有或所有0被删除后还有被删除后还有1,就就拒绝拒绝; 否则否则,带上没有留下带上没有留下1和和0,接受接受. ”时间时间: 2n+n n/2+n=O(n2)理论计算机科学基础20M2M2=“对输入串对输入串w: 1) 扫描带扫描带,若在若在1右边发现右边发现0,就就拒绝拒绝; 2) 若带上还有若带上还有0和和1,就重复下一步就重复下一步; 3) 扫描带扫描带, 检查剩余的检查剩余的0和和1总数总数, 若总数是奇数若总数是奇数,就就拒绝拒绝; 4) 再次扫描带再次扫描带, 从第一个从第一个0开始开始, 隔一个删除一个隔一个删除一个0,然后从第一个然后从第一个 1开始开始, 隔一个删除一个隔一个删除一个1; 5) 若带上没有留下若带上没有留下1和和0,接受接受; 否则否则,拒绝拒绝. ”时间时间: n+n (1+log2n)+n=O(nlogn)理论计算机科学基础21M3M3=“对输入串对输入串w: 1) 扫描带扫描带,若在若在1右边发现右边发现0,就就拒绝拒绝; 2) 扫描带扫描带1上的上的0,把每个把每个0复制到带复制到带2上上, 直到第一个直到第一个1为止为止; 3) 扫描带扫描带1上的上的1直到输入结尾直到输入结尾, 每次从带每次从带1上读到一个上读到一个1, 就在带就在带2上上 删除一个删除一个0, 若在读完若在读完1之前删除了之前删除了 所有的所有的0,就就拒绝拒绝; 4) 若所有若所有0都被删除都被删除,就就接受接受;否则否则,拒绝拒绝. ”时间时间: n+n+n+n=O(n)理论计算机科学基础22时间复杂性类时间复杂性类时间复杂性类TIME(t(n)TIME(t(n) = L | 某个某个O(t(n) 时间的时间的单带单带 DTM判定语言判定语言L 例：例：A = 0k1k | k 0 A TIME(nlogn)A TIME(n2) 模型间的复杂性关系理论计算机科学基础23理论计算机科学基础24模型间的复杂性关系时间复杂性与模型有关时间复杂性与模型有关多带与单带多带与单带: 平方平方非确定型与确定型非确定型与确定型: 指数指数理论计算机科学基础25定理8.8定理定理8.8: 设函数设函数t(n) n, 则每个则每个t(n)时间多带时间多带TM都与某个都与某个O(t2(n)时间单带时间单带TM等价等价证明思路证明思路: 分析定理分析定理4.8的证明的证明, 每步模拟需要每步模拟需要O(t(n)时间时间, 总共模拟总共模拟t(n)步步证明证明: (略略)理论计算机科学基础26NTM运行时间判定机判定机NTM N的运行时间是的运行时间是函数函数f:NN, f(n)=在长为在长为n的输入上的输入上 所有计算分支的最大步数所有计算分支的最大步数. f(n)f(n)理论计算机科学基础27定理8.10定理定理8.10: 设函数设函数t(n) n, 则每个则每个t(n)时间单带时间单带NTM都与某个都与某个2O(t(n)时间单带时间单带DTM等价等价证明思路证明思路: 分析定理分析定理4.10的证明的证明, 每个分支模拟需要每个分支模拟需要O(t(n)时间时间, 总共模拟总共模拟bt(n)个分支个分支, b是所有节点的最大分支数是所有节点的最大分支数证明证明: (略略)P类理论计算机科学基础28理论计算机科学基础29P类P = UkTIME(nk) = L | 某个多项式时间某个多项式时间 单带单带DTM判定语言判定语言L . P的重要性的重要性: 对于所有与单带对于所有与单带DTM 多项式时间等价的计算模型来说多项式时间等价的计算模型来说, P是不变的；是不变的； P大致对应于在计算机上实际可解大致对应于在计算机上实际可解 的问题类，实际算法往往是的问题类，实际算法往往是O(n), O(n2),O(n3), 几乎没有几乎没有O(n100).理论计算机科学基础30路径问题路径问题路径问题: 给定一个有向图给定一个有向图, 一个起点和一个终点一个起点和一个终点,确定是否存在从起点到终点确定是否存在从起点到终点 的有向路径的有向路径PATH=|有向图有向图G有有 从从s到到t的有向路径的有向路径理论计算机科学基础31PATHP定理定理8.12: PATH P分析分析:输入规模输入规模: 顶点数顶点数m蛮力搜索蛮力搜索: O(mm) 宽度优先搜索宽度优先搜索(标记算法标记算法): O(m)证明证明: (略略) #理论计算机科学基础32互素问题互素问题互素问题: 确定两个自然数是否互素确定两个自然数是否互素RELPRIME=|x与与y互素互素理论计算机科学基础33RELPRIMEP定理定理8.13: RELPRIME P分析分析: 输入规模输入规模: 数的二进制表示的长度数的二进制表示的长度n蛮力蛮力: O(2n), 辗转相除辗转相除: O(n2)证明证明: (略略) #理论计算机科学基础34上下文无关语言定理定理8.14: 若若L是是CFL,则则L P.分析分析: 输入规模输入规模: 串长度串长度n=|w|蛮力蛮力: CNF, O(22n-1),动态规划动态规划: O(n3)理论计算机科学基础35上下文无关语言动态规划动态规划: O(n3)输入输入w=w1w2wn维护一个维护一个n n表表: (i,j)项包含产生子串项包含产生子串 wiwi+1wj的变元的变元利用利用Aa填写长为填写长为1的子串的子串对长为对长为k+1的子串的子串, 以以k种方式分成种方式分成2段段, 对每条规则对每条规则ABC, 检查是否检查是否 B产生第产生第1段段, C产生第产生第2段段.证明证明: (略略) #NP类理论计算机科学基础36理论计算机科学基础37哈密顿路径问题(有向有向)哈密顿路径问题哈密顿路径问题: 给定一个有向图给定一个有向图,一个起点一个起点, 一个终点一个终点, 确定是否存在确定是否存在 从起点到终点的哈密顿路径从起点到终点的哈密顿路径(有向有向)哈密顿路径哈密顿路径: (有向有向)图图G中中经过每个顶点恰好一次的经过每个顶点恰好一次的(有向有向)路径路径st理论计算机科学基础38HAMPATHHAMPATH = | (有向有向)图图G 包含从包含从s到到t的哈密顿路径的哈密顿路径st理论计算机科学基础39搜索归约为判定HAMPATH = | (有向有向)图图G 包含从包含从s到到t的哈密顿路径的哈密顿路径判定问题判定问题: 有没有哈密顿路径有没有哈密顿路径搜索问题搜索问题: 求出哈密顿路径求出哈密顿路径st理论计算机科学基础40搜索归约为判定stst理论计算机科学基础41搜索归约为判定stst理论计算机科学基础42搜索归约为判定stst理论计算机科学基础43多项式时间可验证HAMPATH = | (有向有向)图图 G包含从包含从s到到t的哈密顿路径的哈密顿路径搜索问题搜索问题: 解可在多项式时间内验证解可在多项式时间内验证解解: 长度为长度为n的顶点序列的顶点序列, 相邻顶点之间有边相邻顶点之间有边st理论计算机科学基础44验证机语言语言A = w | 字符串字符串c, 算法算法V接受接受 算法算法V是语言是语言A的的验证机验证机c称为称为w是是A的成员的的成员的 资格资格证书证书(证明证明). 理论计算机科学基础45多项式时间验证机语言语言A = w | 字符串字符串c, 算法算法V接受接受 |c|是是|w|的多项式的多项式(“短证明短证明”)在在|w|的多项式时间内运行的多项式时间内运行 (“容易验证容易验证”)若若A有多项时间验证机有多项时间验证机, 则则 称称A为为多项式可验证的多项式可验证的. 理论计算机科学基础46合数问题合数问题合数问题:确定给定的自然数是否合数确定给定的自然数是否合数合数合数: 两个大于两个大于1的自然数的乘积的自然数的乘积COMPOSITES = x | x=pq, 整数整数p,q1理论计算机科学基础47NP类NP = L | 语言语言L有有 多项时间验证机多项时间验证机 解的长度是输入规模的多项式解的长度是输入规模的多项式验证解所花费时间是输入规模验证解所花费时间是输入规模 的多项式的多项式候选解个数是输入规模的指数候选解个数是输入规模的指数理论计算机科学基础48例HAMPATH NP的证书是一条的证书是一条 从从s到到t的哈密顿路径的哈密顿路径COMPOSITES NPx的证书是的证书是x的一个因子的一个因子 HAMPATHc ?NP可能没有多项式时间验证机可能没有多项式时间验证机COMPOSITESc NP问题问题*8.18理论计算机科学基础49非确定型多项式时间判定多项式时间多项式时间NTM N1判定判定HAMPATH.N1=“对输入对输入, 其中其中G是是 包含顶点包含顶点s和和t的的(有向有向)图图: 1) 写下一列写下一列m个数个数p1,p2,pm, m是是G的顶点数的顶点数, 每个每个pi都从都从 1到到m中非确定地挑选中非确定地挑选; 2) 检查列中是否有重复的数检查列中是否有重复的数, 若有重复若有重复,则则拒绝拒绝; 3) 检查是否检查是否s=p1且且t=pm, 若不是若不是,则则拒绝拒绝; 4) 对于对于i从从1到到m-1,检查检查(pi,pi+1) 是否是否G中的边中的边. 若有一个不是若有一个不是,则则拒绝拒绝; 否则否则, 所有检查都通过所有检查都通过, 接受接受. ” #理论计算机科学基础50定理8.17定理定理8.17: NP=L|某个多项式某个多项式 时间时间NTM判定语言判定语言L分析分析: 多项式时间验证机多项式时间验证机 非确定型非确定型多项式时间判定机多项式时间判定机证明证明: ( ) 设设A NP, 则则A有有多项式时间验证机多项式时间验证机V. 设设V的运行时间是的运行时间是nk. 构造构造非确定型非确定型多项式时间判定机多项式时间判定机N. 理论计算机科学基础51定理8.17证明证明证明(续续1): N=“对长为对长为n的输入的输入w: 1) 非确定地选择非确定地选择 长为长为nk的字符串的字符串c;2) 在输入在输入上运行上运行V;3) 若若V接受接受,则则接受接受; 否则否则,拒绝拒绝. ”理论计算机科学基础52定理8.17证明证明证明(续续2): ( ) 设多项式时间设多项式时间 NTM N判定判定A. 构造构造A的的 多项式时间验证机多项式时间验证机V. V=“对输入对输入, 其中其中w,c是字符串是字符串: 1) 在输入在输入w上模拟上模拟N, 把把c的每个符号看作的每个符号看作 对每一步非确定选择的描述对每一步非确定选择的描述; 2) 若若N的该计算分支接受的该计算分支接受, 则则接受接受; 否则否则,拒绝拒绝. ” #理论计算机科学基础53NTIME( ), NP定义定义8.18: NTIME(t(n) = L | 某个某个O(t(n)时间时间NTM 判定语言判定语言L . 推论推论8.19: NP=UkNTIME(nk). NP表示非确定型多项式时间类表示非确定型多项式时间类理论计算机科学基础54NP中问题举例团问题子集和问题理论计算机科学基础55团问题团团: 一组顶点两两彼此相邻一组顶点两两彼此相邻k-团团: 由由k个顶点组成的团个顶点组成的团(Kk子图子图)团问题团问题: CLIQUE=|无向图无向图G有有k-团团理论计算机科学基础56子集和问题子集和问题子集和问题: SUBSET-SUM = | S=x1,x2,xk, xi,t Z, y1,y2,yh x1,x2,xk, yi=t 注注: y1,y2,yh, x1,x2,xk 是是多重集多重集例例: SUBSET-SUM, 4+21=25理论计算机科学基础57定理8.20定理定理8.20: CLIQUE NP证明证明: 验证机验证机DTM V=“ 对输入对输入,c: 1) 检查检查c是否是否G中中k个顶点的个顶点的 集合集合; 2) 检查检查G是否包含连接是否包含连接c中中 顶点的所有边顶点的所有边; 3) 若两项检查都通过若两项检查都通过,则则接受接受; 否则否则,拒绝拒绝.” #理论计算机科学基础58定理8.20(另证)定理定理8.20: CLIQUE NP另证另证: NTM N=“对输入对输入: 1) 非确定性地选择非确定性地选择G中中 k个顶点的子集个顶点的子集c; 2) 检查检查G是否包含连接是否包含连接c中中 顶点的所有边顶点的所有边; 3) 若检查通过若检查通过,则则接受接受; 否则否则,拒绝拒绝.” #理论计算机科学基础59定理8.21定理定理8.21: SUBSET-SUM NP证明证明: 验证机验证机DTM V=“ 对输入对输入,c: 1) 检查检查c是否总和为是否总和为t的的 数的集合数的集合; 2) 检查检查S是否包含是否包含c中所有数中所有数; 3) 若两项检查都通过若两项检查都通过,则则接受接受; 否则否则,拒绝拒绝.” #理论计算机科学基础60定理8.21(另证)定理定理8.21: SUBSET-SUM NP另证另证: NTM N=“对输入对输入: 1) 非确定性地选择非确定性地选择S中中 数的子集数的子集c; 2) 检查检查c是否总和为是否总和为t的的 数的集合数的集合; 3) 若检查通过若检查通过,则则接受接受; 否则否则,拒绝拒绝.” #coNP类、EXP类、P与NP问题理论计算机科学基础61理论计算机科学基础62coNPcoNP=NP中语言的补语言中语言的补语言例例: CLIQUEc coNPNP=?coNP是个难题是个难题P NP coNPPNPcoNPNPcoNP理论计算机科学基础63P与NP问题P=成员资格可以成员资格可以快速判定快速判定的语言类的语言类NP=成员资格可以成员资格可以快速验证快速验证的语言类的语言类P NP EXP=P=?NP问题是著名的难题问题是著名的难题多数研究者认为多数研究者认为P NPP EXPNPPEXPcoNP理论计算机科学基础64小结时间复杂性时间复杂性: 定义定义, 算法分析算法分析, 模型间关系模型间关系常见时间复杂性类常见时间复杂性类P: 定义定义, 问题问题NP: 两种等价定义两种等价定义, 问题问题EXP: 定义定义, 蛮力搜索蛮力搜索理论计算机科学基础65小结时间复杂性类时间复杂性类PNPcoNPNPcoNPEXP空间复杂性、空间复杂性类理论计算机科学基础66理论计算机科学基础67DTM的空间复杂性设设DTM M在所有输入上都停机在所有输入上都停机. 设设M在长度为在长度为n的输入上最多的输入上最多扫描扫描f(n)个不同带方格个不同带方格, 则则M的的空间复杂性空间复杂性是是f(n). 理论计算机科学基础68NTM的空间复杂性设设NTM M在所有输入的在所有输入的所有计算分支上所有计算分支上都停机都停机. 设设M在长度为在长度为n的输入上的输入上在任何计算分支上在任何计算分支上最多最多扫描扫描f(n)个不同带方格个不同带方格, 则则M的的空间复杂性空间复杂性是是f(n).理论计算机科学基础69空间复杂性类SPACE(f(n) = L | 语言语言L被被O(f(n)空间空间 DTM判定判定 NSPACE(f(n) = L | 语言语言L被被O(f(n)空间空间 NTM判定判定 2024/7/25理论计算机科学基础第11讲70可满足性问题可满足性问题可满足性问题给定一个布尔公式给定一个布尔公式, 确定确定 这个公式是否可满足这个公式是否可满足例例: ( x ( y x) (x y) x=1,y=0是可满足赋值是可满足赋值SAT = | 是可满足是可满足 布尔公式布尔公式 理论计算机科学基础71例9.3SAT SPACE(O(n). DTM M1=“ 对输入对输入, 是布尔公式是布尔公式: 1) 对于对于 的变量的变量x1,x2,xm的的 每种赋值每种赋值:2) 计算计算 在该赋值下的值在该赋值下的值;3) 若若 的值为的值为1,则接受则接受; 否则否则,就拒绝就拒绝. ”存储每个赋值需要存储每个赋值需要O(m)空间空间,计算计算 的值需要的值需要O(n)空间空间, m n, 总空间是总空间是O(n). #理论计算机科学基础72例9.4ALLNFA = | M是是NFA且且 L(M)= * ALLcNFA NSPACE(O(n).猜测猜测NFA拒绝的串拒绝的串, 用非确定型线性空间跟踪用非确定型线性空间跟踪NFA状态状态ALLcNFA NP ?ALLcNFA coNP ? ALLNFA NP ? 理论计算机科学基础73例9.4NTM N=“ 对输入对输入, M是是NFA: 1) 在在NFA的初始状态放一个标记的初始状态放一个标记;2) 反复执行反复执行2q次下列语句次下列语句 (q是是M的状态数的状态数);3) 非确定地选择一个输入符号非确定地选择一个输入符号, 改变改变M状态上标记的位置状态上标记的位置 来模拟读取这个输入符号来模拟读取这个输入符号;4) 若在执行步骤若在执行步骤2和和3过程中过程中 某一时刻所有标记都不落在某一时刻所有标记都不落在 接受状态上接受状态上,则接受则接受; 否则否则,拒绝拒绝. ”所有标记的不同位置组合共有所有标记的不同位置组合共有2q种种. 存放所有标记需要存放所有标记需要O(q)空间空间, q n, 总空间是总空间是O(n). #萨维奇定理理论计算机科学基础74理论计算机科学基础75复习NTIME( f(n) ) TIME( 2O(f(n) )用确定型时间来模拟非确定型时间用确定型时间来模拟非确定型时间, 要有指数的增长要有指数的增长所以所以 NP EXP = EXPTIMEf(n)理论计算机科学基础76Savitch定理NSPACE( f(n) ) SPACE( f2(n) )要求要求 f(n) n用确定型空间来模拟非确定型空间用确定型空间来模拟非确定型空间, 只有平方的增长只有平方的增长所以所以 NPSPACE = PSPACE空间可以重复利用空间可以重复利用, 时间则不能时间则不能理论计算机科学基础77Savitch定理定理定理9.5:(Savitch定理定理)设设f(n) n, 则则NSAPCE(f(n) DSPACE(f2(n)证明思路证明思路: f(n)空间的计算空间的计算, 格局大小为格局大小为O(f(n)不同格局的个数是不同格局的个数是2O(f(n), 可以运行可以运行2O(f(n)步步每一步都可以进行非确定选择每一步都可以进行非确定选择如果顺序考察每个计算分支如果顺序考察每个计算分支, 则需要则需要2O(f(n)空间空间, NSAPCE(f(n) NTIME(2O(f(n) 理论计算机科学基础78Savitch定理证明图示证明思路证明思路: 2O(f(n)ffNTIME(f(n)2O(f)fNSPACE(f(n)理论计算机科学基础79可产生性问题可产生性问题可产生性问题给定一个机器给定一个机器, 两个格局和两个格局和一个步数一个步数, 确定这个机器能否确定这个机器能否在这个步数内从第一个格局在这个步数内从第一个格局产生出第二个格局产生出第二个格局CANYIELD=|机器机器M 的格局的格局c1能在能在t步内到达格局步内到达格局c2. 理论计算机科学基础80Savitch定理证明思路证明思路证明思路:递归过程递归过程CANYIELD(c1,c2,t): 格局格局c1能否在能否在t步内到达格局步内到达格局c2. CANYIELD(c1,c2,t)= cm CANYIELD(c1,cm,t/2) CANYIELD(cm,c2,t/2) .存储每个格局需要存储每个格局需要O(f(n)空间空间, t=O(2f(n), 递归深度为递归深度为O(f(n), 总空间总空间O(f2(n). 理论计算机科学基础81定理9.5证明证明证明: 设设A=L(N), N是是O(f(n)空间的空间的NTM, N在长度为在长度为n的输入上不同格局的输入上不同格局总数为总数为2df(n). 构造构造DTM M=“对输入对输入w: 1) 输出输出CANYIELD(cstart,caccept,2df(n). ” CANYIELD=“对输入对输入(c1,c2,t): 1) 若若t=1, 则检查是否则检查是否: c1=c2或或 根据根据N的转移函数的转移函数c1在在1步内产生步内产生c2. 若是若是,则接受则接受,否则否则,就拒绝就拒绝; 2) (接下页接下页)理论计算机科学基础82定理9.5证明证明证明:(续续) 2) 若若t1,则对则对N在在w上每个空间上每个空间 为为O(f(n)的格局的格局cm: 3) 运行运行CANYIELD(c1,cm, t/2 ); 4) 运行运行CANYIELD(cm,c2, t/2 ); 5) 若第若第3和第和第4步都接受步都接受,则接受则接受; 6) 若此时还没有接受若此时还没有接受,则拒绝则拒绝. ”理论计算机科学基础83定理9.5证明证明证明:(续续) M正确模拟正确模拟N, 因此因此L(M)=A. M递归深度为递归深度为 log 2df(n)=O(f(n), 每次需要把每次需要把(c1,c2,t)入栈入栈, 需要空间需要空间O(f(n), 总空间总空间O(f2(n). #PSPACE类理论计算机科学基础84理论计算机科学基础85PSPACE类PSPACE = kSPACE(nk)PSPACE = NPSPACENPSPACE = kNSPACE(nk)NSAPCE(nk) SPACE(n2k)2024/7/25理论计算机科学基础第12讲86带量词布尔公式带量词布尔公式带量词布尔公式(qbf) = x y(x y) ( xy) zz是自由变元是自由变元前束范式前束范式全全带量词布尔公式带量词布尔公式(tqbf) = x y(x y) ( xy)无自由变元无自由变元2024/7/25理论计算机科学基础第12讲87全带量词布尔公式问题全全带量词布尔公问题带量词布尔公问题给定一个全带量词布尔公式给定一个全带量词布尔公式,确定这个公式在论域确定这个公式在论域0,1上上 的真假的真假TQBF = | 是真的是真的tqbf 一般书上叫一般书上叫QBF, 有的书上叫有的书上叫QSAT2024/7/25理论计算机科学基础第12讲88定理9.8定理定理9.8: TQBF PSPACE.证明证明: 递归算法递归算法. DTM T=“ 对输入对输入, 是是tqbf: 1) 若若 不含量词不含量词,则直接计算则直接计算 , 若结果为真若结果为真,则接受则接受; 否则否则,就拒绝就拒绝;2) 若若 = x , 则输出则输出T( |x=0) T( |x=1);3) 若若 = x , 则输出则输出T( |x=0) T( |x=1). ”递归深度等于变量个数递归深度等于变量个数, 每次每次1个个变量值入栈变量值入栈,总空间总空间O(m). #理论计算机科学基础89小结PNPcoNPNPcoNPEXPPSPACE=NPSPACE理论计算机科学基础90重要的悬而未决问题已知已知P NP PSPACE EXPP EXP未知未知P = NP ?P = PSPACE ?NP = PSPACE ?亚线性空间、L类、NL类理论计算机科学基础91理论计算机科学基础92亚线性(sub-linear)亚线性函数亚线性函数f(n)f(n)/n 0 ( n )例如例如 n/log n, n0.99, n, (log n)k, log n, 亚线性空间亚线性空间TM ? 理论计算机科学基础93亚线性空间一条输入带一条输入带(外存外存)只读只读, 不计复杂性不计复杂性一条工作带一条工作带(内存内存)可读写可读写,计入复杂性计入复杂性有穷有穷控制控制只读输入带只读输入带只写输出带只写输出带读写工作带读写工作带f(n)理论计算机科学基础94L类, NL类对数空间复杂性类对数空间复杂性类 L = SPACE( log n )NL = NSPACE( log n )为什么考虑为什么考虑log n而不是而不是 n或或log2n ? 稳健性稳健性: 与机器模型和编码方法无关与机器模型和编码方法无关丰富性丰富性: 足以表示指向输入的指针足以表示指向输入的指针, 可以解决许多有趣的计算问题可以解决许多有趣的计算问题理论计算机科学基础95例9.13A= 0k1k | k 0 L工作空间是一个计数器工作空间是一个计数器, 保存保存 k 值值 有穷有穷控制控制log nn理论计算机科学基础96例9.14PATH = | 有向图有向图G 包含从包含从s到到t的有向路径的有向路径 PATH P (定理定理8.12)PATH NL (本例本例)从从s到到t的路径的路径(顶点序列顶点序列)是是“短证书短证书”可在对数空间内验证这条路径可在对数空间内验证这条路径起点是起点是s终点是终点是t相邻顶点之间有边相邻顶点之间有边理论计算机科学基础97利用局部信息理论计算机科学基础98例9.14NTM M=“对输入对输入: 1) 令当前顶点等于令当前顶点等于s; 2) 执行下列步骤执行下列步骤m步步: 3) 若当前顶点为若当前顶点为t,则接受则接受;4) 非确定地选择下一个顶点非确定地选择下一个顶点, 检查当前顶点到所选择检查当前顶点到所选择 顶点之间是否有一条边顶点之间是否有一条边;5) 若是若是,则令当前顶点等于则令当前顶点等于 所选顶点所选顶点; 否则否则,拒绝拒绝; 6) 若执行完上述若执行完上述m步后还不接受步后还不接受, 就拒绝就拒绝. ” 保存当前顶点需要保存当前顶点需要O(log m)空间空间, m是顶点数是顶点数. #理论计算机科学基础99对数空间TM的格局若若M是有一条只读输入带的是有一条只读输入带的TM, 则则M在在w上的格局上的格局是由状态是由状态,工作带内容工作带内容,两个带头的位置所组成两个带头的位置所组成(注意注意: 输入输入w不不是格局的组成部分是格局的组成部分).有穷控制log nn理论计算机科学基础100对数空间TM的格局数设设f(n)空间空间TM有有c个状态个状态, g个带符号个带符号不同格局有不同格局有cnf(n)gf(n) = n2O(f(n) 个个每个格局长度为每个格局长度为logn+O(f(n)所以，所以，L NL P萨维奇定理萨维奇定理: NSPACE(f) SPACE(f2) 条件为条件为 f(n) n实际条件为实际条件为 f(n) logn .理论计算机科学基础101小结PNPcoNPEXPPSPACE=NPSPACENL=coNLLNL=coNL理论计算机科学基础102理论计算机科学基础103NSPACE(f) = coNSPACE(f)确定性复杂性类对确定性复杂性类对补补封闭封闭L, P, PSPACE, EXP非确定性复杂性类对非确定性复杂性类对补补封闭封闭 ?时间类时间类NP = coNP ?空间类空间类NSPACE(f(n) = coNSPACE(f(n), 条件为条件为 f(n) log n理论计算机科学基础104NL = coNL定理定理9.22: NL = coNL证明思路证明思路: 证明证明 PATHc NL. 当不存在从当不存在从s到到t的路径时的路径时, “短证书短证书”是是从从s可达的顶点的个数可达的顶点的个数cm-1 (m是顶点数是顶点数) 从从s出发出发i步内可达的顶点的集合步内可达的顶点的集合Ai 从从s出发出发i步内可达的顶点的个数步内可达的顶点的个数cicm-1个不同的顶点个不同的顶点 每个顶点从每个顶点从s可达可达 每个顶点都不等于每个顶点都不等于t理论计算机科学基础105定理9.22证明思路图示证明思路证明思路: 证明证明 PATHc NL.如果知道从如果知道从s可达顶点的个数可达顶点的个数c, 则可以在则可以在NL内判定内判定 PATH: 猜猜c个顶点个顶点,验证每个顶点从验证每个顶点从s可达可达, 验证每个顶点都不等于验证每个顶点都不等于t.理论计算机科学基础106定理9.22证明思路图示证明思路证明思路:如何在如何在NL中计算中计算c ? 定义定义 Ai = u | u与与s距离不超过距离不超过i , ci=|Ai|, c=cm-1, m是顶点数是顶点数, 在在NL中从中从ci计算出计算出ci+1AiAi+1理论计算机科学基础107例stadcbesabcdet理论计算机科学基础108例stadcbesabcdetsabcdet理论计算机科学基础109例Ai = u | u与与s距离不超过距离不超过i ci=|Ai| sabcdetsabcdet1356666A1A2A0A3A4A5A6理论计算机科学基础110例v Ai+1 u Ai u=v或或是边是边 v Ai+1 u Ai u v且且不是边不是边 sabcdetsabcdetcici+11vu理论计算机科学基础111定理9.22证明证明证明: 判定判定PATHc的算法如下的算法如下. M = “ 对输入对输入: 1) 令令c0=1 2) For i=0 to m-1 12) d=0 理论计算机科学基础112定理9.22证明2) For i=0 to m-2 3) 令令ci+1=0 4) 对对G中每个顶点中每个顶点v: 5) 令令d=0 6) 对对G中每个顶点中每个顶点u: 7)非确定地执行或跳过以下步骤非确定地执行或跳过以下步骤: 8)非确定地沿从非确定地沿从s出发长为出发长为i的路径的路径 前进前进, 若未遇到若未遇到u, 则则拒绝拒绝 /* u属于属于Ai */ 9) d加加1 10) 若若u=v或或(u,v)是是G的边的边, 则则ci+1加加1, v变为下一个顶点变为下一个顶点, 转到转到5) /* v属于属于Ai+1 */11) 若若d ci, 则则拒绝拒绝 /* 找到找到Ai中所有顶点中所有顶点*/理论计算机科学基础113定理9.22证明12) 令令d=013) 对对G中每个顶点中每个顶点u: 14)非确定地执行或跳过以下步骤非确定地执行或跳过以下步骤: 15)非确定地沿从非确定地沿从s出发长为出发长为m-1的的 路径前进路径前进, 若未遇到若未遇到u, 则则拒绝拒绝 16)若若u=t, 则则拒绝拒绝 17)d加加118)若若d cm-1, 则则拒绝拒绝; 否则否则, 接受接受. ”任何时刻都只存储任何时刻都只存储ci,d,i,j,和指向路径和指向路径末端的指针末端的指针, 所以算法在对数空间内运行所以算法在对数空间内运行. #理论计算机科学基础114小结NSPACE(f(n) SPACE(f2(n), ( f(n) logn )NSPACE(f(n)=coNSPACE(f(n), ( f(n) logn )理论计算机科学基础115小结PNPcoNPEXPPSPACE=NSPACENL=coNLLTQBFSATPATH空间层次定理理论计算机科学基础116理论计算机科学基础117空间可构造空间可构造函数空间可构造函数 f: NN 满足满足f(n) log n 且且f(n)在在O(f(n)空间内可计算空间内可计算输入输入1n, 输出二进制输出二进制f(n)存在存在TM以以f(n)作为空间复杂性作为空间复杂性理论计算机科学基础118例10.2logn, nlogn, n2, 都是空间可构造的都是空间可构造的理论计算机科学基础119线性加速定理定理定理: 对任何常数对任何常数c1, TIME( c f(n) ) = TIME( f(n) )SPACE( c f(n) ) = SPACE( f(n) )证明思路证明思路修改字母表修改字母表, 把若干相邻格子并作一个格子把若干相邻格子并作一个格子修改转移函数修改转移函数, 把若干步并作一步把若干步并作一步意义意义: 采用采用O( )记号的理由记号的理由理论计算机科学基础120带空间限制的通用机设设f(n)是空间可构造的是空间可构造的, g(n)=o(f(n), 则存在则存在TM U在在f(n)空间内运行空间内运行, 并且并且对于在对于在g(n)空间内运行的任意空间内运行的任意TM M和和足够长的输入足够长的输入w, U在输入在输入上模拟上模拟M在输入在输入w上的计算上的计算, 即即U()=M(w). U字母表固定字母表固定, M字母表任意字母表任意, U用用d个格子表示个格子表示M的一个格子的一个格子, U使用空间使用空间dg(n)模拟模拟M, 存在存在n0, 当当n n0时时, dg(n)f(n).理论计算机科学基础121带空间限制的TM的列表设设f(n)是空间可构造的是空间可构造的, 并且并且g(n)=o(f(n), 则可列举出则可列举出TM M1,M2,M3, 使得使得SPACE(g(n) L(M1), L(M2), L(M3), .设全体设全体TM的列表是的列表是N1,N2,N3,给上述每个给上述每个TM增加增加“里程表里程表”, 对于足够长的输入对于足够长的输入, 控制其运行空间不超过控制其运行空间不超过f(n)对于较短的有限个输入对于较短的有限个输入, 把答案把答案“固化固化”在在TM里里 增加增加“时钟时钟”, 控制其运行时间不超过控制其运行时间不超过2f(n),就得到就得到M1,M2,M3,理论计算机科学基础122填塞引理引理引理: 识别同一个语言的识别同一个语言的TM有无穷多个有无穷多个证明思路证明思路: 给程序增加无用语句给程序增加无用语句给给TM增加无用状态和无用转移增加无用状态和无用转移,10,100, 1000,.用用10*表示表示的填塞的填塞(padding)理论计算机科学基础123对角化TM B=“对输入对输入w: 1) 令令n是是w的长度的长度. 2) 利用空间可构造性计算利用空间可构造性计算f(n), 并且划分出这么多带空间并且划分出这么多带空间. 如果后面的步骤企图使用更多的空间如果后面的步骤企图使用更多的空间, 就拒绝就拒绝. /*里程表里程表*/3) 如果如果w不形如不形如10*, M是是TM, 则拒绝则拒绝. /*padding*/ 4) 在在w上模拟上模拟M, 同时计算模拟过程中同时计算模拟过程中 使用的步数使用的步数. 如果计数超过如果计数超过2f(n), 则拒绝则拒绝. /*时钟时钟*/5) 若若M接受接受,则拒绝则拒绝; 若若M拒绝拒绝,则接受则接受.” /*对角化对角化*/ 理论计算机科学基础124U(M,10n0)结果10*10*10*10*10*10*M1接受接受拒绝拒绝接受接受拒绝拒绝接受接受接受接受M2拒绝拒绝接受接受拒绝拒绝拒绝拒绝接受接受拒绝拒绝M3拒绝拒绝拒绝拒绝拒绝拒绝拒绝拒绝拒绝拒绝拒绝拒绝M4接受接受拒绝拒绝接受接受拒绝拒绝接受接受拒绝拒绝M5接受接受接受接受接受接受接受接受接受接受接受接受M6拒绝拒绝接受接受拒绝拒绝拒绝拒绝拒绝拒绝接受接受 理论计算机科学基础125U(M,10n0)结果10*10*10*10*10*10*M1接受接受拒绝拒绝接受接受拒绝拒绝接受接受接受接受M2拒绝拒绝接受接受拒绝拒绝拒绝拒绝接受接受拒绝拒绝M3拒绝拒绝拒绝拒绝拒绝拒绝拒绝拒绝拒绝拒绝拒绝拒绝M4接受接受拒绝拒绝接受接受拒绝拒绝接受接受拒绝拒绝M5接受接受接受接受接受接受接受接受接受接受接受接受M6拒绝拒绝接受接受拒绝拒绝拒绝拒绝拒绝拒绝接受接受 理论计算机科学基础126B(10n0)结果10*10*10*10*10*10*M1拒绝拒绝拒绝拒绝接受接受拒绝拒绝接受接受接受接受M2拒绝拒绝拒绝拒绝拒绝拒绝拒绝拒绝接受接受拒绝拒绝M3拒绝拒绝拒绝拒绝接受接受拒绝拒绝拒绝拒绝拒绝拒绝M4接受接受拒绝拒绝接受接受接受接受接受接受拒绝拒绝M5接受接受接受接受接受接受接受接受拒绝拒绝接受接受M6拒绝拒绝接受接受拒绝拒绝拒绝拒绝拒绝拒绝拒绝拒绝 理论计算机科学基础127空间层次定理定理定理10.3: 对任何空间可构造函数对任何空间可构造函数f, 存在语言存在语言A, 在在O(f)空间可判定空间可判定, 但不能在但不能在o(f)空间内判定空间内判定.证明思路证明思路构造一个语言构造一个语言A A SPACE(O(f(n), A SPACE(o(f(n), 对角化对角化理论计算机科学基础128定理10.3证明证明证明: TM B=“对输入对输入w: 1) 令令n是是w的长度的长度. 2) 划定划定f(n)大小的工作空间大小的工作空间, 如果后面的步骤企图超越如果后面的步骤企图超越 这个空间这个空间,则拒绝则拒绝. 3) 若若w不形如不形如10*, M是是TM, 则拒绝则拒绝. 4) 在在w上模拟上模拟M,如果超过如果超过2f(n)步步, 则拒绝则拒绝; 5) 若若M接受接受,则则拒绝拒绝;若若M拒绝拒绝,则则接受接受.”理论计算机科学基础129定理10.3证明证明证明(续续): B是是O(f)空间的空间的, 设设A=L(B),则则A SPACE(O(f). 下证下证A SPACE(o(f): (反证反证) 设设A=L(M)并且并且M在在g(n)空间内运行空间内运行, g(n)=o(f(n). B需要需要dg(n)空间模拟空间模拟M, d是只与是只与M有关的常数有关的常数. 设设n n0时时有有dg(n)f(n), B可以完成对可以完成对M的模拟的模拟, 则则 10n0 L(M) 10n0 L(B), 即即10n0 A 10n0 A, 矛盾矛盾! #理论计算机科学基础130推论推论推论10.4: 设函数设函数f2(n)是空间可构造的是空间可构造的, 并且函数并且函数f1(n)=o(f2(n), 则则 SPACE(f1(n) SPACE(f2(n)推论推论10.5: 若若01 2,则则 SPACE(n 1) SPACE(n 2).推论推论10.6: NL PSPACE.证明证明: NL SPACE(log2n) SPACE(n). #推论推论10.6: PSPACE EXPSPACE.时间层次定理理论计算机科学基础131理论计算机科学基础132时间可构造时间可构造函数时间可构造函数 t: NN 满足满足t(n) n log n 并且并且t(n)在在O(t(n)时间内可计算时间内可计算输入输入1n, 输出二进制输出二进制f(n)存在存在TM以以t(n)作为时间复杂性作为时间复杂性理论计算机科学基础133例10.9nlogn, n n, n2, 2n ,都是时间可构造的都是时间可构造的理论计算机科学基础134带时间限制的通用机设设t(n)是时间可构造的是时间可构造的, s(n)logs(n)=o(t(n),或或s(n)=o(t(n)/logt(n), 则存在则存在TM U在在t(n)时间内运行时间内运行, 并且对于在并且对于在s(n)时间内运行的时间内运行的任意任意TM M和足够长的输入和足够长的输入w, U在输入在输入上模拟上模拟M在输入在输入w上的计算上的计算, 即即U()=M(w). U字母表固定字母表固定, M字母表任意字母表任意, U用用d个格子表示个格子表示M的一个格子的一个格子, U使用时间使用时间ds(n)logs(n)模拟模拟M, 存在存在n0, 当当n n0时时, ds(n)logs(n)t(n).理论计算机科学基础135带时间限制的TM的列表设设t(n)是时间可构造的是时间可构造的, 并且并且 s(n)=o(t(n)/logt(n), 则可列举出则可列举出 TM M1,M2,M3, 使得使得TIME(s(n) L(M1), L(M2), L(M3), .设全体设全体TM的枚举是的枚举是N1,N2,N3,给上述每个给上述每个TM增加增加“时钟时钟”, 对于足够长的输入对于足够长的输入, 控制其运行时间不超过控制其运行时间不超过t(n)对于较短的有限个输入对于较短的有限个输入, 把答案把答案“固化固化”在在TM里里, 就得到就得到M1,M2,M3,理论计算机科学基础136对角化TM B=“对输入对输入w: 1) 令令n是是w的长度的长度. 2) 利用时间可构造性计算利用时间可构造性计算t(n), 把值把值 t(n)/logt(n) 保存在二进制计数器里保存在二进制计数器里. 每执行一次步骤每执行一次步骤3,4,5之前把该计数器减之前把该计数器减1. 若计数器减到若计数器减到0, 就拒绝就拒绝. /*时钟时钟*/3) 如果如果w不形如不形如10*, M是是TM, 则拒绝则拒绝. /*padding*/ 4) 在在w上模拟上模拟M.5) 若若M接受接受,则拒绝则拒绝; 若若M拒绝拒绝,则接受则接受.” /*对角化对角化*/ 理论计算机科学基础137时间层次定理定理定理10.10: 对任何时间可构造函数对任何时间可构造函数t, 存在语言存在语言A, 在在O(t)时间内可判定时间内可判定, 但不能在但不能在o(t/logt)时间内判定时间内判定.证明思路证明思路构造一个语言构造一个语言A A TIME(O(t(n), A TIME(o(t/logt), 对角化对角化理论计算机科学基础138定理10.10证明证明证明:TM B=“对输入对输入w: 1) 令令n是是w的长度的长度. 2) 利用时间可构造性计算利用时间可构造性计算t(n), 执行下列步骤执行下列步骤 t(n)/logt(n) 步步. 若在这个步数内还没有执行到若在这个步数内还没有执行到 步骤步骤5, 就拒绝就拒绝. 3) 如果如果w不形如不形如10*, M是是TM, 则拒绝则拒绝. 4) 在在w上模拟上模拟M.5) 若若M接受接受,则拒绝则拒绝; 若若M拒绝拒绝,则接受则接受.” 理论计算机科学基础139定理10.10证明证明证明(续续): B采用采用3条轨道条轨道, 一条存储一条存储M的带内容的带内容,一条存储一条存储M的当前状态和转移函数的当前状态和转移函数的副本的副本, 一条存储二进制计数器一条存储二进制计数器. B在常数时间内模拟在常数时间内模拟M的一步的一步, 一共模拟一共模拟 t(n)/logt(n) 步步. B每模拟每模拟M的一步的一步, 就就在在logt(n)时间内时间内给计数器减给计数器减1, 所以所以B是是O(t(n)时间的时间的. 设设A=L(B),则则A TIME(O(t(n). 理论计算机科学基础140定理10.10证明证明证明(续续): 下证下证A TIME(o(t(n)/logt(n): (反证反证) 设设A=L(M)且且M在在g(n)时间内运行时间内运行, g=o(t/logt). B需要需要dg(n)时间模拟时间模拟M, d是只与是只与M有关的常数有关的常数. 设设n n0时有时有dg(n)t(n)/logt(n), 则则 B可以完成对可以完成对M的模拟的模拟,10n0 L(M) 10n0 L(B), 即即 10n0 A 10n0 A, 矛盾矛盾! #理论计算机科学基础141推论推论推论10.11: 设函数设函数t2(n)是时间可构造的是时间可构造的, 并且函数并且函数t1(n)=o( t2(n) / log t2 (n) ), 则则 TIME(t1(n) TIME(t2(n)推论推论10.12: 若若11 2,则则 TIME (n 1) TIME(n 2).推论推论10.13: P EXP.交错式复杂性类理论计算机科学基础142理论计算机科学基础143交错式图灵机交错式图灵机交错式图灵机(ATM)是一种是一种NTM, 其计算树中的非确定性分支点包括其计算树中的非确定性分支点包括全称全称( )和和存在存在( )两类两类,一个全称分支点接受当且仅当一个全称分支点接受当且仅当 它它所有所有儿子接受儿子接受,一个存在分支点接受当且仅当一个存在分支点接受当且仅当 它它至少一个至少一个儿子接受儿子接受,根接受则整个计算接受根接受则整个计算接受. 交错式是对非确定性的推广交错式是对非确定性的推广理论计算机科学基础144ATM的计算树比较比较: NTM只有存在状态只有存在状态,没有全称状态没有全称状态1010NTMATM理论计算机科学基础145交错式时间与空间类ATM在某个输入上的时间在某个输入上的时间(空间空间)复杂性复杂性是所有分支所用时间是所有分支所用时间(空间空间)的最大值的最大值ATIME(t(n)=L(M)|M是是 O(t(n)时间时间ATMASPACE(f(n)=L(M)|M是是 O(f(n)空间空间ATMAP=ATIME(poly)APSPACE=ASPACE(poly)AL=ASPACE(log)理论计算机科学基础146例11.16NP coNP APTAUT = | 是永真式是永真式 AP.ATM M=“对输入对输入: 1) 全称地选择对全称地选择对 的变元的所有赋值的变元的所有赋值;2) 对一个具体的赋值对一个具体的赋值,计算计算 的值的值;3) 如果如果 的值为的值为1,则则接受接受;否则否则拒绝拒绝.” #a1a2na2101计算树理论计算机科学基础147例11.17MIN-FORMULA= | 是极小布尔公式是极小布尔公式 AP.ATM M=“对输入对输入: 1) 全称地选择所有比全称地选择所有比 短的公式短的公式 ;2) 存在地选取对存在地选取对 的变元的一个赋值的变元的一个赋值;3) 计算计算 和和 关于这个赋值的值关于这个赋值的值;4) 如果这两个公式的值不同如果这两个公式的值不同,则则接受接受; 否则否则拒绝拒绝.” #理论计算机科学基础148例11.17(计算树)1m2a1a2a2na1a2a2n1,0,=0,=1,理论计算机科学基础149定理11.18定理定理11.18: 设设f(n) n,则则ATIME(f(n) SPACE(f(n) ATIME(f2(n) 设设f(n) log n, 则则 ASPACE(f(n)=TIME(2O(f(n) L P PSPACE EXP AL AP APSPACE交错式代表一种并行处理能力交错式代表一种并行处理能力=理论计算机科学基础150引理引理引理11.19: f(n) n,ATIME(f(n) SPACE(f(n)引理引理11.20: f(n) n,SPACE(f(n) ATIME(f2(n)引理引理11.21: f(n) log n, ASPACE(f(n) TIME(2O(f(n)引理引理11.22: f(n) log n, ASPACE(f(n) TIME(2O(f(n)多项式时间层次(PH类)理论计算机科学基础151理论计算机科学基础152多项式时间层次(PH) i型型ATM从存在状态开始从存在状态开始, 最多有最多有 (i-1)次全称状态与存在状态交错次全称状态与存在状态交错. i型型ATM从全称状态开始从全称状态开始, 最多有最多有 (i-1)次存在状态与全称状态交错次存在状态与全称状态交错. iTIME(f(n), iTIME(f(n) iP= k iTIME(nk), iP= k iTIME(nk)PH= k iP= k iP文献中一般写成文献中一般写成 ip, ip理论计算机科学基础153例11.17(讨论) 是最小布尔公式是最小布尔公式 | | | , a是赋值是赋值a, (a)(a) 2P= L | L=x| py1, py2,R(x,y1,y2) 2P= L | L=x| py1, py2,R(x,y1,y2) 1P=NP, 1P=coNP, kP, kP,“PH不塌不塌”?: 1 2 3 k ?理论计算机科学基础154PHPH不塌不塌 P NP (2个常用的假设个常用的假设)1p2p3p1p2p3pPHPSPACEEXPP理论计算机科学基础155PH等价定义用用ATM: iP, iP用用OTM: i+1P=NP iP, i+1P=coNP iP, 用量词用量词: iP, iP x L y1 y2 y3QyiR(x, y1,y2 ,yi) x L y1 y2 y3QyiR(x, y1,y2 ,yi)所有量词都是多项式有界的所有量词都是多项式有界的, R是多项式时间可计算谓词是多项式时间可计算谓词约定约定: 0P= 0P=P本周内容小结理论计算机科学基础156理论计算机科学基础157第7周小结度量复杂性度量复杂性O( ),o( )记号、算法分析记号、算法分析模型间复杂性关系模型间复杂性关系 层次定理、交错式图灵机层次定理、交错式图灵机时间类：时间类： P类、类、NP类：类：P=?NP问题问题 coNP类、类、 PH类、类、EXP类类空间类：空间类： PSPACE类：萨维奇定理类：萨维奇定理 L类类, NL类：类：NL=coNL理论计算机科学基础158重要的复杂性类和计算问题PNPcoNPEXPPSPACENLLTQBFSATPATHPH