计算理论17复杂理论高级专题

[e-mail]2019/12/171/55Chap10复杂性理论中的高级专题本章提纲10.1近似算法、10.2概率算法10.3交错式10.4交互证明，10.5并行计算10.6密码学[e-mail]2019/12/172/55近似算法在最优化问题中，通常试图在可行解中寻找最好的解，即最优解。在实践中，可能并不一定非要最优解不可，一个接近最优的解可能是足够好的，而且可能更容易找到。近似算法是为了求近似最优解而设计的。[e-mail]2019/12/173/55顶点覆盖问题若G是无向图，则G的顶点覆盖是节点的一个子集，使得G的每条边都与子集中的节点之一相关联。[e-mail]2019/12/174/55最小顶点覆盖的一个近似算法下述多项式时间算法近似地解这个最优化问题，它给出一个顶点覆盖，其大小不超过最小顶点覆盖的大小的2倍。A＝“对于输入G，这里G是一个无向图：重复下述操作直至G中所有的边都与有标记的边相邻。在G中找一条不与任何有标记的边相邻的边。给这条边作标记。输出所有有标记边的顶点。”[e-mail]2019/12/175/55定理1０.1定理11.1：A是一个多项式时间算法，它给出G的一个顶点覆盖，其大小不超过最小顶点覆盖的大小的2倍。证明思路:A的运行时间显然是多项式界限的。设X是它输出的顶点集合，H是有标记的边的集合。因为G的每一条边要么属于H，要么与H中的一条边相邻，因此X与G的所有边关联，因此X是一个顶点覆盖。证明X的大小不超过最小顶点覆盖Y的大小的2倍。X的大小是H的2倍H不大于[e-mail]2019/12/176/55k-优算法如果一个最小化问题的近似算法总能找到不超过最优解k倍的可行解，则称这个算法是k-优的。对于最大化问题，一个k-优近似算法总能找到不小于最优解大小的1/k的可行解。[e-mail]2019/12/177/55最大割集的近似算法把顶点集V划分成两个不相交的子集S和T，称为无向图中的割。顶点分别在两个子集中的边称为割边，割边的数目称为割的大小。B＝“对于输入G，这里G是顶点集为V的无向图：令S＝Ø和T＝V。如果把一个顶点从S移到T或者从T移到S，使割的大小变大，则做这样的移动，并且重复这一步。如果不存在这样的顶点，则输出当前的割X并且停止。”[e-mail]2019/12/178/55定理1０.2定理11.2：B是最大割集的2-优的多项式近似算法。证明：割的大小不超过G的边数，故B是多项式时间的。证明B输出的割X至少包含G中的所有边的一半。G的每个顶点的割边=非割边。G的所有顶点的割边数和＝X的割边总数×2。G的所有顶点的非割边数和＝非割边总数×2。X的割边数和=非割边数和X的割边数=G的所有边数/2G的所有边数=最大割边数[e-mail]2019/12/179/55概率算法概率算法使用随机过程的结果。典型包含一条“扔硬币”的指令，并且扔硬币的结果可能影响算法后面的执行和输出。BPP类素数性只读一次的分支程序[e-mail]2019/12/1710/55概率图灵机概率图灵机M是一种非确定型图灵机，它的每一非确定步，称作掷硬币步，并且有两个合法的下次动作。定义分支b的概率如下，其中k是在分支b中出现的掷硬币步的步数。定义M接受ω的概率为kb2]Pr[是接受分支＝接受b][Pr]Pr[bM[e-mail]2019/12/1711/55BPP类对于0=ε1/2，如果满足下面的条件则称M以错误概率ε识别语言A。BPP是多项式时间的概率图灵机以错误概率1/3识别的语言类。1]Pr[1]Pr[拒绝蕴涵接受蕴涵[e-mail]2019/12/1712/55引理10.5引理11.5：设ε是一个固定常数，且0ε1/2。又设M1是一台错误概率为ε的多项式时间概率图灵机，则对于任意的多项式poly(n)，存在与M1等价的错误概率为的多项式时间概率图灵机M2。证明思路：M2用如下方式模拟M1：运行M1多项式次，并且取这些运行结果中的多数作为计算结果。错误概率将随M1的运行次数指数下降。)(2npoly[e-mail]2019/12/1713/55素数性定理11.6：例子：p通过在a的费马测试是指如果一个数能通过所有关于小于它且与它互素的数的费马测试，则称这个数为伪素数，其中可能包含卡米切尔数和素数。。，则是素数，且如果)(mod11paappp25mod23,32222,617mod64,64222,75)16(6)17(apap)(mod11pap[e-mail]2019/12/1714/55测试伪素数的多项式概率算法如果p是伪素数则能通过全部测试，如果p不是伪素数则至多能通过全部测试的一半。于是它通过全部k个随机选择的测试的概率不大于，因此该算法以错误概率识别所有伪素数组成的语言。，则接受；否则拒绝”都等于如果所有计算出来的值，计算对于每一个中随机地选取在：“对于输入1mod,,)1(1paiaapEPSEUDOPRIMpikpk2k[e-mail]2019/12/1715/55避免卡米切尔数的算法PRIME基本原理是：对于任意素数p，1恰好有两个模p的平方根：1和-1。而对于许多合数，包括卡米切尔数在内，1有4个或更多的平方根。引理11.7：如果p是一个奇素数，则引理11.8：如果p是一个奇合数，则1]Pr[pPRIME接受kpPRIME2]Pr[接受[e-mail]2019/12/1716/55RP类定理11.9：单侧错误：当算法输出拒绝时，输入一定是合数，当输出接受时，只能知道输入可能是素数。RP是多项式时间概率图灵机识别的语言类，在这里，在语言中的输入以不小于1/2的概率被接受；不在语言中的输入以概率1被拒绝。BPPPRIMESnnPRIMES，是二进制素数令}{[e-mail]2019/12/1717/55只读一次的分支程序分支程序是一个无圈有向图，除两个输出顶点标记0和1外，其他顶点（询问顶点）都标记变量，并引出两条边，一条标记0、一条标记1，在分支程序中指定一个顶点为起始顶点。只读一次的分支程序是指在它的从起始顶点到输出顶点的每一条有向路径上，每个变量只能被询问一次。[e-mail]2019/12/1718/55定理10.12多项式时间概率算法BPPEQBBBBEQROBPROBP},{2121则有的分支程序是两个等价的只读一次和令，则接受；否则拒绝”，，，，如果的值，，在和的多项式和计算赋给，，个元素中随机选取在程序：是两个只读一次的分支和，“对输入个元素的有限域。是一个至少含有设)()(,312111212112121mmmmaapaapaappBBaamFBBBBDmF[e-mail]2019/12/1719/55交错式图灵机的定义定义：一种特殊的非确定型图灵机。除qaccept和qreject外，它的状态分成全称状态和存在状态。∨∧∧∧∧∨∨···[e-mail]2019/12/1720/55交错式语言类ATIME(t(n))={L|L是被一台O(t(n))时间的交错式图灵机判定的语言}ASPACE(t(n))={L|L是被一台O(f(n))空间的交错式图灵机判定的语言}kknPTIMEAP)(kknASPACEAPSPACE)()(lognASPACEAL[e-mail]2019/12/1721/55例10.16永真式是一个布尔公式，对于变量的每一个赋值，它的值都等于1。令TAUT={Ф|Ф是一个永真式}对输入Ф：1.全称的选取对Ф的变量的所有赋值2.对一个具体的赋值，计算Ф的值3.如果Ф的值为1，则接受；否则拒绝TAUT∈[e-mail]2019/12/1722/55例：令L={Ф|Ф不是一个永真式}对输入Ф：1.存在的选取对Ф的变量的所有赋值2.对一个具体的赋值，计算Ф的值3.如果Ф的值为0，则接受；否则拒绝L∈NPTAUT∈[e-mail]2019/12/1723/55引理10.19对于f(n)≥n，有ATIME(f(n))SPACE(f(n))把O(f(n))时间的交错式图灵机M转换成O(f(n))空间的确定型图灵机SS如下模拟M：对于输入w，S对M的计算树做深度优先搜索，确定哪些顶点接受。如果树根接受，则S接受。[e-mail]2019/12/1724/55引理10.20对于f(n)≥n，有SPACE(f(n))ATIME(f2(n))从O(f(n))空间的确定性图灵机M出发，构造一台O(f2(n))时间的交错式图灵机S∨∧∧…cmt/2步内从c1到cmt/2步内从cm到c2t/2步内从c1到c2起始格局接受格局2df(n)[e-mail]2019/12/1725/55S的每个分支使用的最大时间：O(f(n))递归深度：log2df(n)=O(f(n))因此，算法在交错时间O(f2(n))内运行[e-mail]2019/12/1726/55引理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移动一步所得到格局连一条边。[e-mail]2019/12/1727/55由于f(n)≥logn，M关于w的格局数为2O(f(n))。因此，计算图的大小为2O(f(n))，可在2O(f(n))时间内构造它。扫描时间类似，且扫描总次数不超过顶点数，所以，使用总时间为2O(f(n))。[e-mail]2019/12/1728/55引理10.22对于f(n)≥logn，有ASPACE(f(n))TIME(2O(f(n)))abcd2O(f(n))2O(f(n))[e-mail]2019/12/1729/55综合以上四个引理，有如下定理定理10.18对于f(n)≥n，有ATIME(f(n))SPACE(f(n))ATIME(f2(n))对于f(n)≥logn，有ASPACE(f(n))=TIME(2O(f(n)))[e-mail]2019/12/1730/55多项式时间层次定义