唐常杰翻译的计算理论导引23

1、2020/7/4,1,Chap10复杂性理论中的高级专题(同学报告）,可以从下列文件获得PT素材：13_10-复杂理论高级专题-同学报告素材.doc本章提纲10.1近似算法、10.2概率算法10.3交错式10.4交互证明，10.5并行计算10.6密码学,2020/7/4,2,Chap10复杂性理论中的高级专题(同学报告）,可根据提供的PT素材+参考以前同学的报告，修改成为有自己见解的讨论报告建议：底色用浅色（象牙白，浅黄，白色等）适合色盲色弱观众字体颜色选择余地大在投影机效果差时也还能能看见,2020/7/4,3,近似算法,在最优化问题中，通常试图在可行解中寻找最好的解，即最优解。在实践中，可

2、能并不一定非要最优解不可，一个接近最优的解可能是足够好的，而且可能更容易找到。近似算法是为了求近似最优解而设计的。,2020/7/4,4,顶点覆盖问题,若G是无向图，则G的顶点覆盖是节点的一个子集，使得G的每条边都与子集中的节点之一相关联。,2020/7/4,5,最小顶点覆盖的一个近似算法,下述多项式时间算法近似地解这个最优化问题，它给出一个顶点覆盖，其大小不超过最小顶点覆盖的大小的2倍。A“对于输入，这里G是一个无向图：重复下述操作直至G中所有的边都与有标记的边相邻。在G中找一条不与任何有标记的边相邻的边。给这条边作标记。输出所有有标记边的顶点。”,2020/7/4,6,定理1.1,定理11

3、.1：A是一个多项式时间算法，它给出G的一个顶点覆盖，其大小不超过最小顶点覆盖的大小的2倍。证明思路:A的运行时间显然是多项式界限的。设X是它输出的顶点集合，H是有标记的边的集合。因为G的每一条边要么属于H，要么与H中的一条边相邻，因此X与G的所有边关联，因此X是一个顶点覆盖。证明X的大小不超过最小顶点覆盖Y的大小的2倍。X的大小是H的2倍H不大于Y,2020/7/4,7,k-优算法,如果一个最小化问题的近似算法总能找到不超过最优解k倍的可行解，则称这个算法是k-优的。对于最大化问题，一个k-优近似算法总能找到不小于最优解大小的1/k的可行解。,2020/7/4,8,最大割集的近似算法,把顶点

4、集V划分成两个不相交的子集S和T，称为无向图中的割。顶点分别在两个子集中的边称为割边，割边的数目称为割的大小。B“对于输入，这里G是顶点集为V的无向图：令S和TV。如果把一个顶点从S移到T或者从T移到S，使割的大小变大，则做这样的移动，并且重复这一步。如果不存在这样的顶点，则输出当前的割并且停止。”,2020/7/4,9,定理1.2,定理11.2：B是最大割集的2-优的多项式近似算法。证明：割的大小不超过G的边数，故B是多项式时间的。证明B输出的割X至少包含G中的所有边的一半。X的每个顶点的割边=非割边。X的所有顶点的割边数和X的割边总数2。X的所有顶点的非割边数和X的非割边总数2。X的割边数

5、和=X的非割边数和X的割边数=G的所有边数/2G的所有边数=最大割边数,2020/7/4,10,概率算法,概率算法使用随机过程的结果。典型包含一条“扔硬币”的指令，并且扔硬币的结果可能影响算法后面的执行和输出。BPP类素数性只读一次的分支程序,2020/7/4,11,概率图灵机,概率图灵机M是一种非确定型图灵机，它的每一非确定步，称作掷硬币步，并且有两个合法的下次动作。定义分支b的概率如下，其中k是在分支b中出现的掷硬币步的步数。定义M接受的概率为,2020/7/4,12,BPP类,对于0=1/2，如果满足下面的条件则称M以错误概率识别语言A。BPP是多项式时间的概率图灵机以错误概率1/3识别

6、的语言类。,2020/7/4,13,引理10.5,引理11.5：设是一个固定常数，且01/2。又设M1是一台错误概率为的多项式时间概率图灵机，则对于任意的多项式poly(n)，存在与M1等价的错误概率为的多项式时间概率图灵机M2。证明思路：M2用如下方式模拟M1：运行M1多项式次，并且取这些运行结果中的多数作为计算结果。错误概率将随M1的运行次数指数下降。,2020/7/4,14,素数性,定理11.6：例子：p通过在a的费马测试是指如果一个数能通过所有关于小于它且与它互素的数的费马测试，则称这个数为伪素数，其中可能包含卡米切尔数和素数。,2020/7/4,15,测试伪素数的多项式概率算法,如果

7、p是伪素数则能通过全部测试，如果p不是伪素数则至多能通过全部测试的一半。于是它通过全部k个随机选择的测试的概率不大于，因此该算法以错误概率识别所有伪素数组成的语言。,2020/7/4,16,避免卡米切尔数的算法PRIME,基本原理是：对于任意素数p，1恰好有两个模p的平方根：1和-1。而对于许多合数，包括卡米切尔数在内，1有4个或更多的平方根。引理11.7：如果p是一个奇素数，则引理11.8：如果p是一个奇合数，则,2020/7/4,17,RP类,定理11.9：单侧错误：当算法输出拒绝时，输入一定是合数，当输出接受时，只能知道输入可能是素数。RP是多项式时间概率图灵机识别的语言类，在这里，在语

8、言中的输入以不小于1/2的概率被接受；不在语言中的输入以概率1被拒绝。,2020/7/4,18,只读一次的分支程序,分支程序是一个无圈有向图，除两个输出顶点标记0和1外，其他顶点（询问顶点）都标记变量，并引出两条边，一条标记0、一条标记1，在分支程序中指定一个顶点为起始顶点。只读一次的分支程序是指在它的从起始顶点到输出顶点的每一条有向路径上，每个变量只能被询问一次。,2020/7/4,19,定理10.12,多项式时间概率算法,2020/7/4,20,10.3交错式,2020/7/4,21,交错式图灵机的定义,定义：一种特殊的非确定型图灵机。除qaccept和qreject外，它的状态分成全称状

9、态和存在状态。,2020/7/4,22,交错式语言类,ATIME(t(n)=L|L是被一台O(t(n)时间的交错式图灵机判定的语言ASPACE(t(n)=L|L是被一台O(f(n)空间的交错式图灵机判定的语言,2020/7/4,23,例10.16永真式是一个布尔公式，对于变量的每一个赋值，它的值都等于1。令TAUT=|是一个永真式对输入：全称的选取对的变量的所有赋值对一个具体的赋值，计算的值如果的值为1，则接受；否则拒绝TAUTAP,2020/7/4,24,例：令L=|不是一个永真式对输入：存在的选取对的变量的所有赋值对一个具体的赋值，计算的值如果的值为0，则接受；否则拒绝LNPTAUTcoN

10、P,2020/7/4,25,引理10.19对于f(n)n，有ATIME(f(n)SPACE(f(n)把O(f(n)时间的交错式图灵机M转换成O(f(n)空间的确定型图灵机SS如下模拟M：对于输入w，S对M的计算树做深度优先搜索，确定哪些顶点接受。如果树根接受，则S接受。,2020/7/4,26,引理10.20对于f(n)n，有SPACE(f(n)ATIME(f2(n)从O(f(n)空间的确定性图灵机M出发，构造一台O(f2(n)时间的交错式图灵机S,cm,t/2步内从c1到cm,t/2步内从cm到c2,t/2步内从c1到c2,起始格局接受格局,2df(n),2020/7/4,27,S的每个分支

11、使用的最大时间：O(f(n)递归深度：log2df(n)=O(f(n)因此，算法在交错时间O(f2(n)内运行,2020/7/4,28,引理10.21对于对于f(n)logn，有ASPACE(f(n)TIME(2O(f(n)构造一台2O(f(n)时间的确定型图灵机S，模拟O(f(n)空间的交错式图灵机。S构造M对w的计算图如下：顶点集是M关于w的所有格局，每一顶点最多使用df(n)空间（d是与M有关的常数）。从每一个格局到M移动一步所得到格局连一条边。,2020/7/4,29,由于f(n)logn，M关于w的格局数为2O(f(n)。因此，计算图的大小为2O(f(n)，可在2O(f(n)时间内构

12、造它。扫描时间类似，且扫描总次数不超过顶点数，所以，使用总时间为2O(f(n)。,2020/7/4,30,引理10.22对于f(n)logn，有ASPACE(f(n)TIME(2O(f(n),a,b,c,d,2O(f(n),2O(f(n),q,p,o,2020/7/4,31,综合以上四个引理，有如下定理定理10.18对于f(n)n，有ATIME(f(n)SPACE(f(n)ATIME(f2(n)对于f(n)logn，有ASPACE(f(n)=TIME(2O(f(n),2020/7/4,32,多项式时间层次,定义10.23设i是大于0的整数，i交错式图灵机是以存在步骤开始，最多含有i此全称步骤轮

13、换的交错式图灵机。i交错式图灵机与此类似，只是它以全称步骤开始。,2020/7/4,33,多项式时间层次,下述语言类集合称作多项式时间层次：显然有：NP=1PcoNP=1P,2020/7/4,34,10.5并行计算,2020/7/4,35,并行计算机,能够同时执行多个操作的计算机叫并行计算机,2020/7/4,36,并行计算模型,PRAM模型异步APRAM模型BSP模型logP模型,2020/7/4,37,PRAM模型,基本概念：由Fortune和Wyllie1978年提出，又称SIMD-SM模型。有一个集中的共享存储器和一个指令控制器，通过SM的R/W交换数据，隐式同步计算。结构图,2020

14、/7/4,38,PRAM模型,优点适合并行算法表示和复杂性分析，易于使用，隐藏了并行机的通讯、同步等细节。缺点不适合MIMD并行机，忽略了SM的竞争、通讯延迟等因素,2020/7/4,39,一致布尔电路,主要思想：将布尔电路模型用于描述并行计算优点：描述简单，证明容易缺点：不灵活，不便于编程,2020/7/4,40,一致布尔电路,门电路：,X1,X2,X3,2020/7/4,41,两种复杂度,处理器复杂度：布尔电路的规模，即布尔电路中门电路的数目并行时间复杂度：输入变量到输出门的最长距离规模、深度复杂度：(f(n),g(n),2020/7/4,42,电路族,（c1,c2,c3,cn）,2020

15、/7/4,43,例子,例10.31：识别奇数个1X1X2X3X4,+,+,+,(O(n),O(n),2020/7/4,44,例子,例10.31：识别奇数个1X1X2X3X4,+,+,+,规模深度复杂度(O(n),O(Logn),2020/7/4,45,例子,例10.32：布尔矩阵乘法（mXm）例11.33：矩阵A（mXm）的传递闭包AVA2VVAm,规模,深度复杂度(O(n3/2),O(Logn),n=2m2,规模,深度复杂度(O(n5/2),O(Log2n),n=2m2,2020/7/4,46,NC类,定义10.34：i=1,NCi是能够用多项式规模和O(Login)深度的一致布尔电路识别的

16、语言类；用这种电路族计算的函数叫NCi可计算和NC可计算的。,2020/7/4,47,NC类,定理10.35：NC1LL是确定型图灵机在对数空间内可判定的语言定理10.36：NLNC2NL是非确定型图灵机在对数空间内可判定的语言定理10.37：NCPP是确定型单带图灵机在多项式时间内可判定的语言类，P大致对应计算机上实际可解的问题类证明：将多项式时间用于运行对数空间转换器，生成电路Cn（对数空间可归约，对数空间转换器参见9.16P194）,2020/7/4,48,P的完全性,定义10.38：BP，P中每个A对数空间可归约到B，则B是P完全的；定理101.40（电路计算问题是否是P完全的）CIR

17、CUIT-VALUE是P完全的证明：P中任意语言A可对数空间归约到CIRCUIT-VALUE，生成模拟A的电路,2020/7/4,49,10.6：密码学,报告人：XXX,2020/7/4,50,密码技术的起源和发展,1949年，ClaudeShannon在贝尔系统技术杂志上发表论文保密系统的通信理论为单钥密码系统奠定了理论基础。1976年，W.Diffie和M.E.Hellman发表了密码学的新方向，建立了公钥密码系统，引发了密码学一次革命性的变革。随着密码学理论和技术的探索和实践，人们逐渐认识到认证和保密是两个独立的密码属性。G.J.Simmons系统地研究了认证问题，并建立了一套与香农保密

18、理论平行的认证理论。,2020/7/4,51,对称密码（单钥）,对称密码技术原理对称密码系统加密算法数据加密标准DES三重DES国际数据加密算法IDEA高级加密标准AES,2020/7/4,52,密码安全性,密钥长度增加：一次性衬垫数学上不能证明密码不可破译NP完全问题规约到密码破译问题：平均复杂度破译密码与因式分解对应,2020/7/4,53,公钥密码,公钥密码基本原理：Diffie和Hellman设想公钥密码系统满足如下条件：通讯双方A和B容易通过计算产生出一对密钥（公钥KU，私钥KR)在知道公钥KU和待加密报文M的情况下，对于发送方A，很容易通过计算产生对应密文C=EKU(M)接受方B使用私钥容易恢复原来的报文M=DKR(C)=DEKU(M)除A、B以外其他人知道公钥KU,要确定私钥KR在计算上式不可行的除A、B以外其他人知道公钥KU和密文C，要恢复原来的明文M在计算上也是不可行的,2020/7/4,54,公钥密码系统加密算法,密钥交换RSA算法,2020/7/4,55,单向函数,单向函数满足下面条件：它将一个定义阈映射到值域，使得每个函数值有一个唯一的原象；同时，函数值容易计算，而逆计算不可行。例子11.42(P248)单向函数构造私