10 复性理论高级专题.ppt

计算理论;主要内容;近似算法;顶点覆盖问题;最小顶点覆盖的一个近似算法;定理 10.1;k-优算法;最大割集;最大割集的近似算法;定理 10.2;主要内容;米凯尔·拉宾 (Michael O．Rabin) ;概率算法;概率算法;定义 10.3;BPP 类;引理10.5;引理10.5 的证明;引理10.5 的证明;素数性;费马小定理;测试伪素数的多项式概率算法;避免卡米切尔数的算法 PRIME;避免卡米切尔数的算法 PRIME;素数性概率算法的正确性说明;素数性;素数性;素数性;素数性;素数性概率算法;只读一次的分支程序;分支程序是一个有向无环图。其中，除两个输出顶点标记为 0 或 l 外，它的所有顶点都被标记为变量。被标记为变量的顶点叫做查询顶点。每一个查询顶点引出两条边，一条标记 0，另一条标记 1。两个输出顶点没有引出的边。在分支程序中指定一个顶点为起始顶点。;只读一次的分支程序;只读一次的分支程序;定理10.12 EQROBP 在 BPP 中。;只读一次的分支程序;引理 10.13;引理 10.14;引理10.14;主要内容;交错式;交错式;交错式时间与交错式空间;例10.17 永真式(tautology)是一个布尔公式，对于变量的每一个赋值，它的值都等于 1。令 TAUT={? | ? 是一个永真式}。 下述交错式算法表明 TAUT 在 AP 中。 “对输入? ： 1) 全称地选取对? 的变量的所有赋值。 2) 对一个具体的赋值，计算? 的值。 3) 如果? 的值为 l，则接受；否则拒绝。”;交错式时间与交错式空间;交错式时间与交错式空间;交错式时间与交错式空间;交错式时间与交错式空间;交错式时间与交错式空间;交错式时间与交错式空间;多项式时间层次;主要内容;交互式证明系统;图的非同构;模型的定义;模型的定义;模型的定义;定义 10.25;IP=PSPACE;断言 10.28;定理 10.30;主要内容;并行计算（Parallel Computing）;并行计算;并行计算;并行计算;一致布尔电路;定义 10.31;一致布尔电路;一致布尔电路;例10.34设A={aij}是一个m×n布尔矩阵，A的传递闭包(transitive closure)是矩阵 A∨A2∨…∨Am 其中Ai是i个A的矩阵乘积，∨是矩阵元素的按位OR。传递闭包运算与PATH问题关系密切，因而与NL类的关系密切。设A是有向图G的邻接矩阵，Ai是顶点与G相同、边表示G中存在??度i的路径的图邻接矩阵。A的传递闭包是图的邻接矩阵，图中的边表示G中存在一条路径。 可以用规模为i和深度为logi的二元树表示Ai的计算，其中每个顶点计算它下面的两个矩阵的乘积。每个顶点是一个O(n3/2)规模和对数深度的电路。因此，计算Am的电路的规模为O(n2)，深度为O(log2n)。对每一个Ai构造一个电路，共要添加O(nm)=O(n3/2)规模和O(logn)深度。因此，传递闭包的规模-深度复杂度(O(n5/2)，O(log2n))。;定义 10.35;定理 10.36;定理 10.37;;定理 10.38;定义 10.39;定理 10.40;定理 10.41;主要内容;;;;定义 10.42;定义 10.42;例10.43乘法函数mult可能是一个单向函数。设?={0,1}。对于任意的w∈ ?*，令mult(w)是表示w的前一半与后一半乘积的字符串。形式地表示为： mult(w)=w1·w2 其中w=w1·w2，且当|w|为偶数时，|w1|=|w2|；当|w|为奇数时，| w1|=| w2 |+1。 w1和w2作为二进制数处理。在mult(w)的前面添加0使得它与w一样长。尽管人们对整数因子分解问题做了大量研究，但还不知道有多项式时间概率算法能够反演mult，即使对于输入的多项式分之一也不知道这样的算法。;天窗函数(trapdoor function);天窗函数举例;作业