资源描述
2019/12/24,1/59,Chap10复杂性理论中的高级专题(同学报告）,可以从下列文件获得PT素材：13_10-复杂理论高级专题-同学报告素材.doc本章提纲10.1近似算法、10.2概率算法10.3交错式10.4交互证明，10.5并行计算10.6密码学,2019/12/24,2/59,Chap10复杂性理论中的高级专题(同学报告）,可根据提供的PT素材+参考以前同学的报告，修改成为有自己见解的讨论报告建议：底色用浅色（象牙白，浅黄，白色等）适合色盲色弱观众字体颜色选择余地大在投影机效果差时也还能能看见,2019/12/24,3/59,近似算法,在最优化问题中，通常试图在可行解中寻找最好的解，即最优解。在实践中，可能并不一定非要最优解不可，一个接近最优的解可能是足够好的，而且可能更容易找到。近似算法是为了求近似最优解而设计的。,2019/12/24,4/59,顶点覆盖问题,若G是无向图，则G的顶点覆盖是节点的一个子集，使得G的每条边都与子集中的节点之一相关联。,2019/12/24,5/59,最小顶点覆盖的一个近似算法,下述多项式时间算法近似地解这个最优化问题，它给出一个顶点覆盖，其大小不超过最小顶点覆盖的大小的2倍。A“对于输入，这里G是一个无向图：重复下述操作直至G中所有的边都与有标记的边相邻。在G中找一条不与任何有标记的边相邻的边。给这条边作标记。输出所有有标记边的顶点。”,2019/12/24,6/59,定理1.1,定理11.1：A是一个多项式时间算法，它给出G的一个顶点覆盖，其大小不超过最小顶点覆盖的大小的2倍。证明思路:A的运行时间显然是多项式界限的。设X是它输出的顶点集合，H是有标记的边的集合。因为G的每一条边要么属于H，要么与H中的一条边相邻，因此X与G的所有边关联，因此X是一个顶点覆盖。证明X的大小不超过最小顶点覆盖Y的大小的2倍。X的大小是H的2倍H不大于Y,2019/12/24,7/59,k-优算法,如果一个最小化问题的近似算法总能找到不超过最优解k倍的可行解，则称这个算法是k-优的。对于最大化问题，一个k-优近似算法总能找到不小于最优解大小的1/k的可行解。,2019/12/24,8/59,最大割集的近似算法,把顶点集V划分成两个不相交的子集S和T，称为无向图中的割。顶点分别在两个子集中的边称为割边，割边的数目称为割的大小。B“对于输入，这里G是顶点集为V的无向图：令S和TV。如果把一个顶点从S移到T或者从T移到S，使割的大小变大，则做这样的移动，并且重复这一步。如果不存在这样的顶点，则输出当前的割并且停止。”,2019/12/24,9/59,定理1.2,定理11.2：B是最大割集的2-优的多项式近似算法。证明：割的大小不超过G的边数，故B是多项式时间的。证明B输出的割X至少包含G中的所有边的一半。X的每个顶点的割边=非割边。X的所有顶点的割边数和X的割边总数2。X的所有顶点的非割边数和X的非割边总数2。X的割边数和=X的非割边数和X的割边数=G的所有边数/2G的所有边数=最大割边数,2019/12/24,10/59,概率算法,概率算法使用随机过程的结果。典型包含一条“扔硬币”的指令，并且扔硬币的结果可能影响算法后面的执行和输出。BPP类素数性只读一次的分支程序,2019/12/24,11/59,概率图灵机,概率图灵机M是一种非确定型图灵机，它的每一非确定步，称作掷硬币步，并且有两个合法的下次动作。定义分支b的概率如下，其中k是在分支b中出现的掷硬币步的步数。定义M接受的概率为,2019/12/24,12/59,BPP类,对于0=1/2，如果满足下面的条件则称M以错误概率识别语言A。BPP是多项式时间的概率图灵机以错误概率1/3识别的语言类。,2019/12/24,13/59,引理10.5,引理11.5：设是一个固定常数，且0=1,NCi是能够用多项式规模和O(Login)深度的一致布尔电路识别的语言类；用这种电路族计算的函数叫NCi可计算和NC可计算的。,2019/12/24,47/59,NC类,定理10.35：NC1LL是确定型图灵机在对数空间内可判定的语言定理10.36：NLNC2NL是非确定型图灵机在对数空间内可判定的语言定理10.37：NCPP是确定型单带图灵机在多项式时间内可判定的语言类，P大致对应计算机上实际可解的问题类证明：将多项式时间用于运行对数空间转换器，生成电路Cn（对数空间可归约，对数空间转换器参见9.16P194）,2019/12/24,48/59,P的完全性,定义10.38：BP，P中每个A对数空间可归约到B，则B是P完全的；定理101.40（电路计算问题是否是P完全的）CIRCUIT-VALUE是P完全的证明：P中任意语言A可对数空间归约到CIRCUIT-VALUE，生成模拟A的电路,2019/12/24,49/59,10.6：密码学,报告人：XXX,2019/12/24,50/59,密码技术的起源和发展,1949年，ClaudeShannon在贝尔系统技术杂志上发表论文保密系统的通信理论为单钥密码系统奠定了理论基础。1976年，W.Diffie和M.E.Hellman发表了密码学的新方向，建立了公钥密码系统，引发了密码学一次革命性的变革。随着密码学理论和技术的探索和实践，人们逐渐认识到认证和保密是两个独立的密码属性。G.J.Simmons系统地研究了认证问题，并建立了一套与香农保密理论平行的认证理论。,2019/12/24,51/59,对称密码（单钥）,对称密码技术原理对称密码系统加密算法数据加密标准DES三重DES国际数据加密算法IDEA高级加密标准AES,2019/12/24,52/59,密码安全性,密钥长度增加：一次性衬垫数学上不能证明密码不可破译NP完全问题规约到密码破译问题：平均复杂度破译密码与因式分解对应,2019/12/24,53/59,公钥密码,公钥密码基本原理：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在计算上也是不可行的,2019/12/24,54/59,公钥密码系统加密算法,密钥交换RSA算法,2019/12/24,55/59,单向函数,单向函数满足下面条件：它将一个定义阈映射到值域，使得每个函数值有一个唯一的原象；同时，函数值容易计算，而逆计算不可行。例子11.42(P248)单向函数构造私钥密码系统。(P248),2019/12/24,56/59,天窗函数,天窗函数（单向陷门函数）：除非知道某种附加的信息，否则这样的函数在一个方向上容易计算而在另一个方向上要计算不可行。有了附加信息，函数的逆就可以在多项式时间内计算出来。例子11.44（P249)天窗函数构造公钥密码系统,2019/12/24,57/59,混沌密码学,参考文章混沌保密通信的若干问题及混沌加密新方案。混沌编码在信息加密中的应用。,2019/12/24,58/59,章小结,10.1近似算法、10.2概率算法10.3交错式10.4交互证明，10.5并行计算10.6密码学,2019/12/24,59/59,AnyQuestion?,Thankyou!,
展开阅读全文