计算复杂性理论.ppt

信息安全数学信息安全数学2017.2北京工北京工业大学信息学部大学信息学部1.课程简介为了解决信息通信系统信息的非授权访问，密码技术被广泛的用于通信系统的各个层面。现代密码技术是以数学为基础发展起来的，其中数论和代数结构是解决现代密码关键技术的理论基础。而现有各学科教学体制中缺乏专门介绍密码以及信息安全所涉及的数学知识的课程。因此，为了适应信息技术发展的需求，将信息安全相关的数学作为一门独立的基础课程，为解决信息安全理论与实践问题提供数学基础。2.课程地位程地位本课程为信息安全专业以及与通信相关的各专业的本科生奠定一定的数学基础，提高他提高他们认识、分析和解决信息安全分析和解决信息安全问题的能力的能力。本课程是学科基础课，系统的介绍与信息安全理论与技术相关的数学知识以及一些常用的计算方法，并通过一些应用实例使学生了解数学知识在信息安全中的应用，同时通过这些实例帮助学生更好的理解抽象的数学知识，为进一步应用数学知识解决信息安全领域的理论与实践问题奠定扎实的数学基础。3.绪论信息系统安全包含以下四个方面：1.设安备全：设备的稳定性、可靠性、可用性2.数据安全：数据的秘密性、完整性、可用性3.内容安全：信息内容在政治上是健康的，符合国家法律法规、符合中华民族优良的道德规范4.行为安全：行为的秘密性、行为的完整性、行为的可控性（以确保信息安全）4.信息安全的内涵信息系统的硬件系统安全和操作系统安全是信息系统安全的基础，密码和网络安全等技术是信息系统安全的关键技术。为了表述简单直接将信息系统安全简称为信息安全。信息安全学科是研究信息获取、信息存储、信息传输和信息处理中的信息安全保障问题的一门新兴学科。5.信息安全学科的性质信息安全学科是综合计算机、通信、电子、数学、物理、生物、管理、法律和教育 等学科，并发展演绎而形成的交叉学科。信息安全学科已经独立，并形成了自己的理论、技术和应用，正服务于信息社会。6.信息安全的主要研究方向密码学网络安全信息系统安全信息内容安全信息对抗7.信息安全的理论基础数学1.密码学代数、数论、概率统计。2.安全协议逻辑学3.信息对抗博弈论信息论、控制论和系统论计算理论：可计算理论和计算复杂性理论8.主要内容及时间安排计算复杂性（6课时）因式分解困难问题及其所涉及的数论基础（28课时）离散对数问题及其现代数学基础（10课时）逻辑学基础（6课时）量子力学基础（2课时）总复习（2课时）闭卷考试：平时20%+试卷80%答疑：每周三下午2-4点，信西404A。9.第一讲：计算复杂性计算复杂性的概念计算量的表示算法与计算量计算复杂性影响计算复杂性的因素10.计算复杂性的概念（1）计算复算复杂性理性理论（Computational complexity theory）是计算理论的一部分，研究计算问题时所需的资源，比如时间和空间，以及如何尽可能的节省这些资源计算复算复杂性理性理论所研究的资源中最常见的是时间（要通过多少步才能解决问题）和空间（在解决问题时需要多少内存）。其他资源亦可考虑，例如在并行计算中，需要多少并行处理器才能解决问题。11.计算复杂性的概念（2）时间复复杂度度是指在计算机科学与工程领域完成一个算法所需要的时间，是衡量一个算法优劣的重要参数。时间复杂度越小，说明该算法效率越高，则该算法越有价值。空空间复复杂度度是指计算机科学领域完成一个算法所需要占用的存储空间，一般是输入参数的函数。它是算法优劣的重要度量指标，一般来说，空间复杂度越小，算法越好。我们假设有一个图灵机来解决某一类语言的某一问题，设有X个字（word）属于这个问题，把X放入这个图灵机的输入端，这个图灵机为解决此问题所需要的工作带格子数总和称为空空间。12.计算复杂性的概念（3）l复杂度理论和可计算性理论不同，可计算性理论的重心在于问题能否解决，不管需要多少资源。而复杂性理论作为计算理论的分支，某种程度上被认为和算法理论是一种“矛”与“盾”的关系，即算法理论专注于设计有效的算法，而复杂性理论专注于理解为什么对于某类问题，不存在有效的算法。13.历史回顾在20世纪50年代，Trahtenbrot和Rabin的论文被认为是该领域最早的文献。而一般说来，被公认为奠定了计算复杂性领域基础的是Hartmanis和Stearns的1960年代的论文On the computational complexity of algorithms。在这篇论文中，作者引入了时间复杂性类TIME(f(n)的概念，并利用对角线法证明了时间层级定理（Time Hierarchy Theorem）。在此之后，许多研究者对复杂性理论作出了贡献。期间重要的发现包括：对随机算法的去随机化（derandomization）的研究，对近似算法的不可近似性（hardness of approximation）的研究，以及交互式证明系统（Interactive proof system）理论和零知识证明（Zero-knowledge proof）等。特别的复杂性理论对近代密码学的影响非常显著，而最近，复杂性理论的研究者又进入了博弈论领域，并创立了“算法博弈论”（algorithmic game theory）这一分支。14.计算模型和计算资源计算复杂性理论的研究对象是算法在执行时所需的计算资源，而为了讨论这一点，我们必须假设算法是在某个计算模型上运行的。常讨论的计算模型包括图灵机（Turing machine）和电路（circuit），它们分别是一致性（uniform）和非一致性（non-uniform）计算模型的代表。而计算资源与计算模型是相关的，如对图灵机我们一般讨论的是时间、空间和随机源，而对电路我们一般讨论电路的大小。由邱奇-图灵论题（Church-Turing thesis），所有的一致的计算模型与图灵机在多项式时间意义下是等价的。而由于我们一般将多项式时间作为有效算法的标志，该论题使得我们可以仅仅关注图灵机而忽略其它的计算模型。15.例1：可满足性（Satisfiability）问题布尔变量集合布尔变量 和 称为文字子句集合子句 是一些文字的析取（逻辑或）真值赋值给定U和C，是否存在满足C的真值赋值？可满足：C中所有的子句在 t 下为真计算复杂度：16.例2：货郎担问题（Traveling salesman problem)给定n个城市，任意两个城市间有路相连，一个货郎从一个城市出发，不重复的遍历所有的城市并回到起点，求一条路程最短的路径。加权完全图，求Hamilton圈，使得计算复杂度：用有限時間可以求解，但计算时间太长，成本太高优化技术与方法17.計算量計算量(1)l,l比較：，l 5种基本演算都是用1step 可以实现.l实际上,比多占用時間.l 四舍五入不算基本演算.18.計算量(2)a1,a2,.,an：n個整数Q1.求和（1）：a1+a2+an.n-1 steps O(n)算法.Q2.求和（2）：(1)2a1+2an,2n-1 steps O(n)算法.(2)2(a1+an),n steps O(n)算法.19.計算量(3)Q3.計算：a1b1+anbn.2n-1 steps.Q4.2个阶矩阵相乘.n2(2n-1)steps（n2n+n-1)）.20.計算量(4)Q5.a1,a2,.,an：n個整数 求其和为最大的部分集合.所有的部分集合的和进行比較 2n(n-1)+(2n-1)O(n2n)算法.21.计算量的膨胀(1)10行10列棋盘上米粒的数量（第1格内放1粒米，以后每格顺次增加1倍)格序号格序号 米粒数米粒数 重量重量(kg)1 1 2.010-59 256 5.110-318 131072 2.610027 67108864 1.310336 34359738368 6.9 10545 17592186044416 3.5 10854 9007199254740992 1.8 101163 4611686018427387904 9.2101372 2361183241434822606848 4.7 101681 1208925819614629174706176 2.4 10202.4108亿吨22.计算量的膨胀(2)100MIPS(mega instructions per second)1秒間100万回的計算1step 用 10-6秒 光速 3.01010cm/秒 (10-6秒 行进300m)n 10 100 1,000 10,000n 10-5秒 10-4秒 10-3秒 0.01秒n2 10-4秒 0.01秒 1秒 100秒n3 0.001秒 1秒 16.6分 277時間2n 0.001秒 1014世紀 10284世紀 n!0.036秒 10141世紀 102551世紀宇龄：宇宙的年齢 1.5108 世紀（億年）23.计算机速度增加的效果（1）10秒間的計算量？100MIPS 10倍 100倍 1000倍 n 107 108 109 1010 n2 3千 1万 3万 10万n3 215 462 1千 2千2n 23 27 30 33 n!10 11 12 131000倍 1step 用 10-9秒 10-9秒 光可以行进30cm24.计算机速度增加的效果（2）计算速度 1秒可以求解问题的规模 O(2n)O(n)O(n2)O(n5)O(n10)1 100 100 100 100 1002 101 200 141 115 10710 103 1000 316 158 126 100 107 10000 1000 251 1581000 110 100000 3162 398 20010000 113 1000000 10000 631 251100000 117 10000000 31623 1000 3161000000 120 100000000 100000 1585 39825.平行（并列）計算的场合0.5 cm 见方小碎片，覆盖地球表面需要 2.01019個.与100MIPS的单个計算機相比，能加速多少？n 100 1,000 .2n 1014世紀 0.85 秒 10284世紀 10263世紀 n!10141世紀 10120世紀 102551世紀 102530世紀26.问题与算法每个問題都可能有多个算法存在每个算法的计算量（速度）都不同。例：赝品金币問題：问题：9個外观完全一样的金币.，有一个是假的（重量轻）提问：用天秤来鉴别真伪，天秤需要使用几次？27.贋贋品品金金币問題問題算法算法使用2次天秤,就可以鉴别出假币.789 23456左边軽右边軽平衡 23中有偽币789中有偽币456中有偽币左边軽32右边軽平衡3245678928.计算量的表示法:上界值表示法O記号：(Big O Notation)定义:O(f(n)读作order f(n),或阶 f(n)即：g(n)=O(f(n)表示对于任意定数c 和 m，以及对所有 nm，有下式成立：g(n)cf(n)29.计算量的表示法例n+1000nO(n)log n+n3+1000n2 O(n3)判断：n!O(nn)？10n2 O(n3)？log n O(n)？思考：O()?30.优化问题的规模表示优化問題大小的参数例如：旅行商问题：都市的个数;背包问题：物品的个数注：参数的个数并不仅限于1个Input Size31.多项式时间算法与指数时间算法指数時間算法=用问题规模的指数函数来表示計算時間的算法非有效算法的代名詞多項式時間算法=能用问题规模的多项式函数来表示計算時間的算法高效率算法的代名詞32.多项式时间算法的计算时间问题规模計算時間1020304050100100010000100MIPS(million instructions per second)计算机的情形33.指数时间算法的计算时间100MIPS(million instructions per second)计算机的情形问题规模計算時間10203040501001宙齢=150億年34.指数灾难：计算量的指数增长35.指数灾难能否避免？SAT问题，货郎担问题，背包问题，图着色问题，最长路径问题，是否对于每个问题都有好的算法？什么是好的算法？什么是算法？36.算法的定义为实现某个任务而构成的简单指令集有穷的计算良过程通过有限多次运算可以决定的过程正确直观，非形式37.算法的定义希尔伯特第十问题（1900）设计一个算法来判断多项式是否有整数根算法：通过有限多次运算可以决定的过程Alan Turing&Alonzo Church（1936）图灵机程序算法：图灵机程序形式化的，精确的38.图灵机（Turing Machine)带子可读可写无限长的带子读写头可左移右移 有限状态控制器1111110000000BBB139.40.图灵机（Turing Machine)TM运行由 确定:当前状态为q，所读字符为s ，读写头不变，读写头左移一格，s不变，读写头右移一格，s不变，无定义，则停机Church-Turing论题：凡是可计算的过程都可用图灵机实现；41.旅行商问题的计算量（1）n個都市訪問的可能的巡回路线：n!的Stirling近似公式BigOh記法的定数倍的大小可以忽略 42.旅行商问题的计算量（2）根据Stirling公式以及O（）表示法O（nn）43.排序问题的计算量（1）：排序問題：S=a1,a2,.,an，n個整数列，按数值大小排列data S 输入 需O(n)時間；可能的排列種類数 n!种；算法中每一个比較,都增加 2倍的情形数 2分树的高度 （比较的次数）,log2(n!)=O(n log n)xy?yesnon!种可能的排列44.排序问题计算量（2）总计算时间的复杂性：O(n log n)data S 输入 時間(或赋值时间)：O(n)比较时间：O(n log n)上位取整45.计算量的确定例：背包问题的贪婪算法（greedy algorithm）的计算量确定46.计算量的确定47.计算量的确定48.计算量的确定49.计算量的确定50.计算量的确定51.计算量的确定52.计算的复杂度时间复杂度：计算量:计算各基本操作的实行回数 （time complexity）空间复杂度 各计算时点内存中保持数据个数的最大值 （space complexity）两者的两者的总称：称：计算的复算的复杂度度53.计算复杂度的影响因素探索空探索空间1-解的近似度、满意度 例：010之间的整数解：1-9共9个可行解（一维）010之间的实数解：精确到小数点后6位 共有107个可行解（一维）；107n个可行解（n维）探索空探索空间2-解空间大小 例：桌子上有6根火柴，要求构建出4个三角形。54.计算复杂度的影响因素探索策略的选取55.计算复杂度的影响因素问题本身 P问题 NP问题（NP-hard，NP困难问题）NP完全问题 56.P类（Polynomial)判定问题：只有肯定和否定两种答案优化问题可以化作判定问题处理P类具有多项式时间算法的判定问题形成的计算复杂性类猜测TSP（Traveling salesman problem)不属于P（J.Edmonds 1965）57.P class problem:能用多項式時間算法求解的问题的集合称为P（polynomial）问题某一个问题属于P问题的証明某一个问题不属于P问题的証明如能够找到一个多項式時間算法（簡単）不存在？没找到？（困难）优化问题的分类（1）58.NP类(Nondeterministic Polynomial)NP问题：在非确定型图灵机上多项式时间可解的问题在确定型图灵机上多项式时间可验证的问题P类包含于NP类中NP类问题在确定图灵机上指数时间可解非确定型图灵机和确定型图灵机的计算能力相当59.优化问题的分类（2）NP class problem:尚未确信能否用多項式時間算法求解的问题的集合称为NP（non-deterministic polynomial）问题某一个问题不属于NP问题的証明某一个问题属于NP问题的証明如能够找到一个多項式時間算法（簡単）可以归结为某一类既知的NP类问题（现阶段7类）60.优化问题的分类（3）（根据算法）NP-complete problem:集合NP中的問題=NP問題如果某个NP問題能够求解，则因所有NP問題都可以经过归结，转化为该问题，从而可以求解所有 NP問題。这样的NP問題=NP完全問題集合NP中的最难的问题=NP完全问题61.计算难度比较的标准难易是比较而言的多项式时间归约（Karp归约 1972)定义问题A多项式时间内转化为问题B的特殊情况，则称A可多项式归约于B，记为转化时间为多项式对于A的输入I 的回答与其对应的B的输入 f(I)一致62.NP完全与NP-hardNP完全问题：NP-hard问题：63.NP完全问题第一个NP完全问题（Cook定理 1971）可满足性问题是NP完全问题六个NP完全问题（Karp 1972)3SAT，3DM，VC，团，HC，划分更多的NP完全问题1979年：300多个1998年：2000多个64.P、NP、NP完全的包容关系NPNP完全旅行商問題背包問題。P最短路問題线性规划問題。NP=PNP完全大多数研究者认可的包容关系这种可能性也存在（现阶段无法证明）悬赏$100万求证65.NP完全问题第一个NP完全问题（Cook定理 1971）可满足性问题是NP完全问题六个NP完全问题（Karp 1972)3SAT，3DM，VC，团，HC，划分更多的NP完全问题1979年：300多个1998年：2000多个66.现在的估计如果 ，则指数灾难无法避免P=?NP（P-NP问题）P=NPPNPCNP67.如何处理NP完全问题 实际的问题不会消失油井勘探问题移动通讯中的频率分配问题68.并行计算以硬件设备换取时间存在着很多种并行计算模型理想模型PRAM可多项式时间解NP完全问题实际中效果不好处理器数目是受限的现实的代价：通讯，同步，分布式计算69.算法的研究随机算法判定问题：以较大概率得到正确输出输出正确，但计算时间不定优化问题：输出解的性能不稳定以较大概率得到性能好的解70.算法的研究完全算法利用某些策略减少计算量分支界限法（Branch and Bound）最坏情况时间复杂度是指数的近似算法不要最优，只求较优时间复杂度较低71.算法的研究近似算法局部搜索遗传算法模拟退火 72.新的计算模型生物计算DNA计算机量子计算量子计算机73.DNA计算实验处理了7城市Hamilton路径问题 L.Adleman 1994 可以多项式时间解所有的NP问题Lipton R J 1995实验可以建立一个非确定型图灵机Smith W,Schweitzer A.199574.DNA计算的困难操作的复杂性单元操作的时间代价高规模的限制处理的问题规模较小输入输出纠错的问题75.量子计算量子计算思想的提出Richard Feynman 1982量子图灵机模型David Deutsch 1985Shor算法（Peter Shor 1994）多项式时间分解大数质因子Grover 算法（Grover L.K.1996）无序数据库的搜索：76.量子计算的困难操作的复杂性单元操作的时间代价高规模的限制测量输出纠错的问题77.理论与实践(1)计算复杂性的初衷是理解不同算法问题的难度，特别的是一些重要算法问题的困难性。为了确切的描述一个问题的困难性，计算复杂性的第一步抽象是认为多项式时间是有效的，非多项式时间是困难的。78.理论与实践(2)这基于指数函数增长速度的“违反直觉”的特性：如果一个算法的时间复杂性为2n，取输入的规模是100，在运算速度是1012每秒（关于CPU速度，参见Instructions per second，其中报告截止2009年，主流个人电脑的运算速度可以看作是 每秒）的情况下，该程序将会运行 年，几乎是宇宙年龄。这为多项式时间被看作是有效时间提供了直观上的证据。79.理论与实践(3)然而多项式的指数很大的时候，算法在实践中也不能看作是有效的。如n10 的多项式算法，取问题规模大小为1000，那么几乎就是2100 的大小。另一方面，即便一个问题没有多项式算法，它可能会有近似比很好的近似算法（参见近似算法），或有很好的启发式算法（heuristics）。启发式算法的特点是在理论上没有精确的行为的分析，或者可以表明存在很坏的输入，在这些输入上运行很慢。然而在大多数时候，它都能快速解决问题。80.推荐阅读计算机和难解性：NP完全性理论导引（Michael R.Garey&David S.Johnson 1979)可计算性与计算复杂性导引 (张立昂）计算理论导引计算理论基础81.作业 82.谢谢大家！83.