唐常杰翻译的计算理论导引ppt课件.ppt

Chap10复杂性理论中的高级专题 同学报告 可以从下列文件获得 PT素材 13 10 复杂理论高级专题 同学报告素材 doc本章提纲10 1近似算法 10 2概率算法10 3交错式10 4交互证明 10 5并行计算10 6密码学 1 Chap10复杂性理论中的高级专题 同学报告 可根据提供的 PT素材 参考以前同学的报告 修改成为有自己见解的讨论报告建议 底色用浅色 象牙白 浅黄 白色等 适合色盲色弱观众字体颜色选择余地大在投影机效果差时也还能能看见 2 近似算法 在最优化问题中 通常试图在可行解中寻找最好的解 即最优解 在实践中 可能并不一定非要最优解不可 一个接近最优的解可能是足够好的 而且可能更容易找到 近似算法是为了求近似最优解而设计的 3 顶点覆盖问题 若G是无向图 则G的顶点覆盖是节点的一个子集 使得G的每条边都与子集中的节点之一相关联 4 最小顶点覆盖的一个近似算法 下述多项式时间算法近似地解这个最优化问题 它给出一个顶点覆盖 其大小不超过最小顶点覆盖的大小的2倍 A 对于输入 这里G是一个无向图 重复下述操作直至G中所有的边都与有标记的边相邻 在G中找一条不与任何有标记的边相邻的边 给这条边作标记 输出所有有标记边的顶点 5 定理1 1 定理11 1 A是一个多项式时间算法 它给出G的一个顶点覆盖 其大小不超过最小顶点覆盖的大小的2倍 证明思路 A的运行时间显然是多项式界限的 设X是它输出的顶点集合 H是有标记的边的集合 因为G的每一条边要么属于H 要么与H中的一条边相邻 因此X与G的所有边关联 因此X是一个顶点覆盖 证明X的大小不超过最小顶点覆盖Y的大小的2倍 X的大小是H的2倍H不大于Y 6 k 优算法 如果一个最小化问题的近似算法总能找到不超过最优解k倍的可行解 则称这个算法是k 优的 对于最大化问题 一个k 优近似算法总能找到不小于最优解大小的1 k的可行解 7 最大割集的近似算法 把顶点集V划分成两个不相交的子集S和T 称为无向图中的割 顶点分别在两个子集中的边称为割边 割边的数目称为割的大小 B 对于输入 这里G是顶点集为V的无向图 令S 和T V 如果把一个顶点从S移到T或者从T移到S 使割的大小变大 则做这样的移动 并且重复这一步 如果不存在这样的顶点 则输出当前的割并且停止 8 定理1 2 定理11 2 B是最大割集的2 优的多项式近似算法 证明 割的大小不超过G的边数 故B是多项式时间的 证明B输出的割X至少包含G中的所有边的一半 X的每个顶点的割边 非割边 X的所有顶点的割边数和 X的割边总数 2 X的所有顶点的非割边数和 X的非割边总数 2 X的割边数和 X的非割边数和X的割边数 G的所有边数 2G的所有边数 最大割边数 9 概率算法 概率算法使用随机过程的结果 典型包含一条 扔硬币 的指令 并且扔硬币的结果可能影响算法后面的执行和输出 BPP类素数性只读一次的分支程序 10 概率图灵机 概率图灵机M是一种非确定型图灵机 它的每一非确定步 称作掷硬币步 并且有两个合法的下次动作 定义分支b的概率如下 其中k是在分支b中出现的掷硬币步的步数 定义M接受 的概率为 11 BPP类 对于0 1 2 如果满足下面的条件则称M以错误概率 识别语言A BPP是多项式时间的概率图灵机以错误概率1 3识别的语言类 12 引理10 5 引理11 5 设 是一个固定常数 且0 1 2 又设M1是一台错误概率为 的多项式时间概率图灵机 则对于任意的多项式poly n 存在与M1等价的错误概率为的多项式时间概率图灵机M2 证明思路 M2用如下方式模拟M1 运行M1多项式次 并且取这些运行结果中的多数作为计算结果 错误概率将随M1的运行次数指数下降 13 素数性 定理11 6 例子 p通过在a的费马测试是指如果一个数能通过所有关于小于它且与它互素的数的费马测试 则称这个数为伪素数 其中可能包含卡米切尔数和素数 14 测试伪素数的多项式概率算法 如果p是伪素数则能通过全部测试 如果p不是伪素数则至多能通过全部测试的一半 于是它通过全部k个随机选择的测试的概率不大于 因此该算法以错误概率识别所有伪素数组成的语言 15 避免卡米切尔数的算法PRIME 基本原理是 对于任意素数p 1恰好有两个模p的平方根 1和 1 而对于许多合数 包括卡米切尔数在内 1有4个或更多的平方根 引理11 7 如果p是一个奇素数 则引理11 8 如果p是一个奇合数 则 16 RP类 定理11 9 单侧错误 当算法输出拒绝时 输入一定是合数 当输出接受时 只能知道输入可能是素数 RP是多项式时间概率图灵机识别的语言类 在这里 在语言中的输入以不小于1 2的概率被接受 不在语言中的输入以概率1被拒绝 17 只读一次的分支程序 分支程序是一个无圈有向图 除两个输出顶点标记0和1外 其他顶点 询问顶点 都标记变量 并引出两条边 一条标记0 一条标记1 在分支程序中指定一个顶点为起始顶点 只读一次的分支程序是指在它的从起始顶点到输出顶点的每一条有向路径上 每个变量只能被询问一次 18 定理10 12 多项式时间概率算法 19 10 3交错式 20 交错式图灵机的定义 定义 一种特殊的非确定型图灵机 除qaccept和qreject外 它的状态分成全称状态和存在状态 21 交错式语言类 ATIME t n L L是被一台O t n 时间的交错式图灵机判定的语言 ASPACE t n L L是被一台O f n 空间的交错式图灵机判定的语言 22 例10 16永真式是一个布尔公式 对于变量的每一个赋值 它的值都等于1 令TAUT 是一个永真式 对输入 全称的选取对 的变量的所有赋值对一个具体的赋值 计算 的值如果 的值为1 则接受 否则拒绝TAUT AP 23 例 令L 不是一个永真式 对输入 存在的选取对 的变量的所有赋值对一个具体的赋值 计算 的值如果 的值为0 则接受 否则拒绝L NP TAUT coNP 24 引理10 19对于f n n 有ATIME f n SPACE f n 把O f n 时间的交错式图灵机M转换成O f n 空间的确定型图灵机SS如下模拟M 对于输入w S对M的计算树做深度优先搜索 确定哪些顶点接受 如果树根接受 则S接受 25 引理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 26 S的每个分支使用的最大时间 O f n 递归深度 log2df n O f n 因此 算法在交错时间O f2 n 内运行 27 引理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移动一步所得到格局连一条边 28 由于f n logn M关于w的格局数为2O f n 因此 计算图的大小为2O f n 可在2O f n 时间内构造它 扫描时间类似 且扫描总次数不超过顶点数 所以 使用总时间为2O f n 29 引理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 30 综合以上四个引理 有如下定理定理10 18对于f n n 有ATIME f n SPACE f n ATIME f2 n 对于f n logn 有ASPACE f n TIME 2O f n 31 多项式时间层次 定义10 23设i是大于0的整数 i交错式图灵机是以存在步骤开始 最多含有i此全称步骤轮换的交错式图灵机 i交错式图灵机与此类似 只是它以全称步骤开始 32 多项式时间层次 下述语言类集合称作多项式时间层次 显然有 NP 1PcoNP 1P 33 10 5并行计算 34 并行计算机 能够同时执行多个操作的计算机叫并行计算机 35 并行计算模型 PRAM模型异步APRAM模型BSP模型logP模型 36 PRAM模型 基本概念 由Fortune和Wyllie1978年提出 又称SIMD SM模型 有一个集中的共享存储器和一个指令控制器 通过SM的R W交换数据 隐式同步计算 结构图 37 PRAM模型 优点适合并行算法表示和复杂性分析 易于使用 隐藏了并行机的通讯 同步等细节 缺点不适合MIMD并行机 忽略了SM的竞争 通讯延迟等因素 38 一致布尔电路 主要思想 将布尔电路模型用于描述并行计算优点 描述简单 证明容易缺点 不灵活 不便于编程 39 一致布尔电路 门电路 X1 X2 X3 40 两种复杂度 处理器复杂度 布尔电路的规模 即布尔电路中门电路的数目并行时间复杂度 输入变量到输出门的最长距离规模 深度复杂度 f n g n 41 电路族 c1 c2 c3 cn 42 例子 例10 31 识别奇数个1X1X2X3X4 O n O n 43 例子 例10 31 识别奇数个1X1X2X3X4 规模深度复杂度 O n O Logn 44 例子 例10 32 布尔矩阵乘法 mXm 例11 33 矩阵A mXm 的传递闭包AVA2V VAm 规模 深度复杂度 O n3 2 O Logn n 2m2 规模 深度复杂度 O n5 2 O Log2n n 2m2 45 NC类 定义10 34 i 1 NCi是能够用多项式规模和O Login 深度的一致布尔电路识别的语言类 用这种电路族计算的函数叫NCi可计算和NC可计算的 46 NC类 定理10 35 NC1 LL是确定型图灵机在对数空间内可判定的语言定理10 36 NL NC2NL是非确定型图灵机在对数空间内可判定的语言定理10 37 NC PP是确定型单带图灵机在多项式时间内可判定的语言类 P大致对应计算机上实际可解的问题类证明 将多项式时间用于运行对数空间转换器 生成电路Cn 对数空间可归约 对数空间转换器参见9 16P194 47 P的完全性 定义10 38 B P P中每个A对数空间可归约到B 则B是P完全的 定理101 40 电路计算问题是否是P完全的 CIRCUIT VALUE是P完全的证明 P中任意语言A可对数空间归约到CIRCUIT VALUE 生成模拟A的电路 48 10 6 密码学 报告人 XXX 49 密码技术的起源和发展 1949年 ClaudeShannon在 贝尔系统技术杂志 上发表论文 保密系统的通信理论 为单钥密码系统奠定了理论基础 1976年 W Diffie和M E Hellman发表了 密码学的新方向 建立了公钥密码系统 引发了密码学一次革命性的变革 随着密码学理论和技术的探索和实践 人们逐渐认识到认证和保密是两个独立的密码属性 G J Simmons系统地研究了认证问题 并建立了一套与香农保密理论平行的认证理论 50 对称密码 单钥 对称密码技术原理对称密码系统加密算法数据加密标准DES三重DES国际数据加密算法IDEA高级加密标准AES 51 密码安全性 密钥长度增加 一次性衬垫数学上不能证明密码不可破译NP完全问题规约到密码破译问题 平均复杂度破译密码与因式分解对应 52 公钥密码 公钥密码基本原理 Diffie和Hellman设想公钥密码系统满足如下条件 通讯双方A和B容易通过计算产生出一对密钥 公钥KU 私钥KR 在知道公钥KU和待加密报文M的情况下 对于发送方A 很容易通过计算产生对应密文C EKU M 接受方B使用私钥容易恢复原来的报文M DKR C D EKU M 除A B以外其他人知道公钥KU 要确定私钥KR在计算上式不可行的除A B以外其他人知道公钥KU和密文C 要恢复原来的明文M在计算上也是不可行的 53 公钥密码系统加密算法 密钥交换RSA算法 54 单向函数 单向函数满足下面条件 它将一个定义阈映射到值域 使得每个函数值有一个唯一的原象 同时 函数值容易计算 而逆计算不可行 例子11 42 P248 单向函数构造私钥密码系统 P248 55 天窗函数 天窗函数