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

Chap 10 复杂性理论中的高级专题 本章提纲 10.1 近似算法、 10.2 概率算法 10.3 交错式 10.4 交互证明， 10.5 并行计算 10.6 密码学 近似算法 在最优化问题中，通常试图在可行解中寻找最好的解，即最优解。 在实践中，可能并不一定非要最优解不可，一个接近最优的解可能是足够好的，而且可能更容易找到。 近似算法是为了求近似最优解而设计的。 顶点覆盖问题 若G是无向图，则G的顶点覆盖是节点的一个子集，使得G的每条边都与子集中的节点之一相关联。 最小顶点覆盖的一个近似算法 下述多项式时间算法近似地解这个最优化问题，它给出一个顶点覆盖，其大小不超过最小顶点覆盖的大小的2倍。 A＝ “对于输入G，这里G是一个无向图： 重复下述操作直至G中所有的边都与有标记的边相邻。 在G中找一条不与任何有标记的边相邻的边。 给这条边作标记。 输出所有有标记边的顶点。 ” 定理1０.1 定理11.1：A是一个多项式时间算法，它给出G的一个顶点覆盖，其大小不超过最小顶点覆盖的大小的2倍。 证明思路: A的运行时间显然是多项式界限的。 设X是它输出的顶点集合，H是有标记的边的集合。因为G的每一条边要么属于H，要么与H中的一条边相邻，因此X与G的所有边关联，因此X是一个顶点覆盖。 证明X的大小不超过最小顶点覆盖Y的大小的2倍。 X的大小是H的2倍 H不大于Y k-优算法 如果一个最小化问题的近似算法总能找到不超过最优解k倍的可行解，则称这个算法是k-优的。 对于最大化问题，一个k-优近似算法总能找到不小于最优解大小的1/k的可行解。 最大割集的近似算法 把顶点集V划分成两个不相交的子集S和T，称为无向图中的割。顶点分别在两个子集 中的边称为割边，割边的数目称为割的大小。 B＝ “对于输入G，这里G是顶点集为V的无向图： 令S＝?和T＝V。 如果把一个顶点从S移到T或者从T移到S，使割的大小变大，则做这样的移动，并且重复这一步。 如果不存在这样的顶点，则输出当前的割X并且停止。” 定理1０.2 定理11.2：B是最大割集的2-优的多项式近似算法。 证明： 割的大小不超过G的边数，故B是多项式时间的。 证明B输出的割X至少包含G中的所有边的一半。 G的每个顶点的割边=非割边。 G的所有顶点的割边数和＝ X的割边总数×2。 G的所有顶点的非割边数和＝ 非割边总数×2。 X的割边数和= 非割边数和 X的割边数 = G的所有边数/2 G的所有边数=最大割边数 概率算法 概率算法使用随机过程的结果。典型包含一条“扔硬币”的指令，并且扔硬币的结果可能影响算法后面的执行和输出。 BPP类 素数性 只读一次的分支程序 概率图灵机 概率图灵机M是一种非确定型图灵机，它的每一非确定步，称作掷硬币步，并且有两个合法的下次动作。定义分支b的概率如下，其中k是在分支b中出现的掷硬币步的步数。 定义M接受ω的概率为 BPP类 对于0=ε1/2，如果满足下面的条件则称M以错误概率ε识别语言A。 BPP是多项式时间的概率图灵机以错误概率1/3识别的语言类。 引理10.5 引理11.5：设ε是一个固定常数，且0ε1/2。又设M1是一台错误概率为ε的多项式时间概率图灵机，则对于任意的多项式poly(n)，存在与M1等价的错误概率为 的多项式时间概率图灵机M2。 证明思路：M2用如下方式模拟M1：运行M1多项式次，并且取这些运行结果中的多数作为计算结果。错误概率将随M1的运行次数指数下降。 素数性 定理11.6： 例子： p通过在a的费马测试是指 如果一个数能通过所有关于小于它且与它互素的数的费马测试，则称这个数为伪素数，其中可能包含卡米切尔数和素数。 测试伪素数的多项式概率算法 如果p是伪素数则能通过全部测试，如果p不是伪素数则至多能通过全部测试的一半。于是它通过全部k个随机选择的测试的概率不大于 ，因此该算法以错误概率 识别所有伪素数组成的语言。 避免卡米切尔数的算法PRIME 基本原理是：对于任意素数p，1恰好有两个模p的平方根：1和-1。而对于许多合数，包括卡米切尔数在内，1有4个或更多的平方根。 引理11.7：如果p是一个奇素数，则 引理11.8：如果p是一个奇合数，则 RP类 定理11.9： 单侧错误：当算法输出拒绝时，输入一定是合数，当输出接受时，只能知道输入可能是素数。 RP是多项式时间概率图灵机识别的语言类，在这里，在语言中的输入以不小于1/2的概率被接受；不在语言中的输入以概率1被拒绝。 只读一次的分支程序 分支程序是一个无圈有向图，除两个输出顶点标记0和1外，其他顶点（询问顶点）都标记变量，并引出两条边，一条标记0、一条标记