计算复杂性理论

信息安全数学2017.2北京工业大学信息学部课程简介为了解决信息通信系统信息的非授权访问，密码技术被广泛的用于通信系统的各个层面。现代密码技术是以数学为基础发展起来的，其中数论和代数结构是解决现代密码关键技术的理论基础。而现有各学科教学体制中缺乏专门介绍密码以及信息安全所涉及的数学知识的课程。因此，为了适应信息技术发展的需求，将信息安全相关的数学作为一门独立的基础课程，为解决信息安全理论与实践问题提供数学基础。课程地位本课程为信息安全专业以及与通信相关的各专业的本科生奠定一定的数学基础，提高他们认识、分析和解决信息安全问题的能力。本课程是学科基础课，系统的介绍与信息安全理论与技术相关的数学知识以及一些常用的计算方法，并通过一些应用实例使学生了解数学知识在信息安全中的应用，同时通过这些实例帮助学生更好的理解抽象的数学知识，为进一步应用数学知识解决信息安全领域的理论与实践问题奠定扎实的数学基础。绪论信息系统安全包含以下四个方面：设安备全：设备的稳定性、可靠性、可用性数据安全：数据的秘密性、完整性、可用性内容安全：信息内容在政治上是健康的，符合国家法律法规、符合中华民族优良的道德规范行为安全：行为的秘密性、行为的完整性、行为的可控性（以确保信息安全）信息安全的内涵信息系统的硬件系统安全和操作系统安全是信息系统安全的基础，密码和网络安全等技术是信息系统安全的关键技术。为了表述简单直接将信息系统安全简称为信息安全。信息安全学科是研究信息获取、信息存储、信息传输和信息处理中的信息安全保障问题的一门新兴学科。信息安全学科的性质信息安全学科是综合计算机、通信、电子、数学、物理、生物、管理、法律和教育等学科，并发展演绎而形成的交叉学科。信息安全学科已经独立，并形成了自己的理论、技术和应用，正服务于信息社会。信息安全的主要研究方向密码学网络安全信息系统安全信息内容安全信息对抗信息安全的理论基础数学密码学——代数、数论、概率统计。安全协议——逻辑学信息对抗——博弈论信息论、控制论和系统论计算理论：可计算理论和计算复杂性理论主要内容及时间安排计算复杂性（6课时）因式分解困难问题及其所涉及的数论基础（28课时）离散对数问题及其现代数学基础（10课时）逻辑学基础（6课时）量子力学基础（2课时）总复习（2课时）闭卷考试：平时20%+试卷80%答疑：每周三下午2-4点，信西404A。第一讲：计算复杂性计算复杂性的概念计算量的表示算法与计算量计算复杂性影响计算复杂性的因素计算复杂性的概念（1）

计算复杂性理论（Computationalcomplexitytheory）是计算理论的一部分，研究计算问题时所需的资源，比如时间和空间，以及如何尽可能的节省这些资源。

计算复杂性理论所研究的资源中最常见的是时间（要通过多少步才能解决问题）和空间（在解决问题时需要多少内存）。其他资源亦可考虑，例如在并行计算中，需要多少并行处理器才能解决问题。计算复杂性的概念（2）时间复杂度是指在计算机科学与工程领域完成一个算法所需要的时间，是衡量一个算法优劣的重要参数。时间复杂度越小，说明该算法效率越高，则该算法越有价值。空间复杂度是指计算机科学领域完成一个算法所需要占用的存储空间，一般是输入参数的函数。它是算法优劣的重要度量指标，一般来说，空间复杂度越小，算法越好。我们假设有一个图灵机来解决某一类语言的某一问题，设有X个字（word）属于这个问题，把X放入这个图灵机的输入端，这个图灵机为解决此问题所需要的工作带格子数总和称为空间。计算复杂性的概念（3）复杂度理论和可计算性理论不同，可计算性理论的重心在于问题能否解决，不管需要多少资源。而复杂性理论作为计算理论的分支，某种程度上被认为和算法理论是一种“矛”与“盾”的关系，即算法理论专注于设计有效的算法，而复杂性理论专注于理解为什么对于某类问题，不存在有效的算法。历史回顾在20世纪50年代，Trahtenbrot和Rabin的论文被认为是该领域最早的文献。而一般说来，被公认为奠定了计算复杂性领域基础的是Hartmanis和Stearns的1960年代的论文Onthecomputationalcomplexityofalgorithms。在这篇论文中，作者引入了时间复杂性类TIME(f(n))的概念，并利用对角线法证明了时间层级定理（TimeHierarchyTheorem）。在此之后，许多研究者对复杂性理论作出了贡献。期间重要的发现包括：对随机算法的去随机化（derandomization）的研究，对近似算法的不可近似性（hardnessofapproximation）的研究，以及交互式证明系统（Interactiveproofsystem）理论和零知识证明（Zero-knowledgeproof）等。特别的复杂性理论对近代密码学的影响非常显著，而最近，复杂性理论的研究者又进入了博弈论领域，并创立了“算法博弈论”（algorithmicgametheory）这一分支。计算模型和计算资源计算复杂性理论的研究对象是算法在执行时所需的计算资源，而为了讨论这一点，我们必须假设算法是在某个计算模型上运行的。常讨论的计算模型包括图灵机（Turingmachine）和电路（circuit），它们分别是一致性（uniform）和非一致性（non-uniform）计算模型的代表。而计算资源与计算模型是相关的，如对图灵机我们一般讨论的是时间、空间和随机源，而对电路我们一般讨论电路的大小。由邱奇-图灵论题（Church-Turingthesis），所有的一致的计算模型与图灵机在多项式时间意义下是等价的。而由于我们一般将多项式时间作为有效算法的标志，该论题使得我们可以仅仅关注图灵机而忽略其它的计算模型。例1：可满足性（Satisfiability）问题布尔变量集合布尔变量和称为文字子句集合子句是一些文字的析取（逻辑或）真值赋值给定U和C，是否存在满足C的真值赋值？可满足：C中所有的子句在t下为真计算复杂度：例2：货郎担问题

（Travelingsalesmanproblem)给定n个城市，任意两个城市间有路相连，一个货郎从一个城市出发，不重复的遍历所有的城市并回到起点，求一条路程最短的路径。加权完全图，，，求Hamilton圈

，使得计算复杂度：用有限時間可以求解，但计算时间太长，成本太高优化技术与方法計算量(1)＋,－,×,÷比較：≠，≤，≥，＜，＞5种基本演算都是用1step

可以实现.实际上,×比＋多占用時間.「四舍五入」不算基本演算.

計算量(2)｛a1,a2,...,an｝：n個整数Q1.

求和（1）：

a1+a2+･･･+an.

n-1steps→O(n)算法.Q2.

求和（2）：

(1)2×a1+･･･+2×an,2n-1steps→O(n)算法.(2)2×(a1+･･･+an)

,nsteps→O(n)算法.計算量(3)Q3.

計算：a1b1+･･･+anbn.

2n-1steps.Q4.2个ｎ×ｎ阶矩阵相乘.

n2(2n-1)steps（n2(n+n-1)）.計算量(4)Q5.｛a1,a2,...,an｝：n個整数

求其和为最大的部分集合.

所有的部分集合的和进行比較2n(n-1)+(2n-1)→O(n2n)算法.计算量的膨胀(1)10行×10列棋盘上米粒的数量（第1格内放1粒米，以后每格顺次增加1倍……)格序号米粒数重量(kg)112.0×10-592565.1×10-3181310722.6×10027671088641.3×10336343597383686.9×10545175921860444163.5×1085490071992547409921.8×10116346116860184273879049.2×10137223611832414348226068484.7×10168112089258196146291747061762.4×10202.4×108亿吨计算量的膨胀(2)100MIPS(megainstructionspersecond)1秒間100万回的計算＝1step用10-6秒光速3.0×1010cm/秒(10-6秒

行进300m)n101001,00010,000n10-5秒10-4秒10-3秒0.01秒n210-4秒0.01秒1秒100秒n30.001秒

1秒16.6分277時間2n0.001秒1014世紀10284世紀n!0.036秒10141世紀102551世紀宇龄：

宇宙的年齢1.5×108世紀（１５０億年）计算机速度增加的效果（1）10秒間的計算量？100MIPS10倍100倍1000倍

n1071081091010n23千1万

3万

10万n3215462

1千

2千2n2327

30

33

n!101112131000倍⇒1step用10-9秒⇒

10-9秒光可以行进30cm计算机速度增加的效果（2）计算速度1秒可以求解问题的规模

O(2n)O(n)O(n2)O(n5)O(n10)100100100100100101200141115107103100031615812610710000100025115811010000031623982001131000000100006312511000001171000000031623100031610000001201000000001000001585398平行（并列）計算的场合0.5cm见方小碎片，覆盖地球表面需要2.0×1019個.与100MIPS的单个計算機相比，能加速多少？n1001,000.2n1014世紀→0.85秒10284世紀→10263世紀n!10141世紀→10120世紀102551世紀→102530世紀问题与算法每个問題都可能有多个算法存在．每个算法的计算量（速度）都不同。例：赝品金币問題：问题：9個外观完全一样的金币.，有一个是假的（重量轻）．提问：用天秤来鉴别真伪，天秤需要使用几次？贋品金币問題算法使用2次天秤,就可以鉴别出假币.789１23456左边軽右边軽平衡１23中有偽币789中有偽币456中有偽币左边軽１32右边軽平衡１32456789计算量的表示法:上界值表示法O記号：(BigONotation)定义:O(f(n))读作orderf(n),或阶f(n)即：g(n)=O(f(n))表示对于任意定数c和m，以及对所有n＞m，有下式成立：g(n)＜cf(n)计算量的表示法——例n２+1000n→O(n２)logn+n3+1000n2→O(n3)判断：n!→O(nn)？10n2→

O(n3)？logn→

O(n)？思考：O()?优化问题的规模表示优化問題大小的参数例如：旅行商问题：都市的个数;背包问题：物品的个数注：参数的个数并不仅限于1个InputSize多项式时间算法与指数时间算法指数時間算法=用问题规模的指数函数来表示計算時間的算法非有效算法的代名詞多項式時間算法=能用问题规模的多项式函数来表示計算時間的算法高效率算法的代名詞多项式时间算法的计算时间问题规模計算時間1020304050100100010000100MIPS(millioninstructionspersecond)计算机的情形指数时间算法的计算时间100MIPS(millioninstructionspersecond)计算机的情形问题规模計算時間10203040501001宙齢=150億年指数灾难：计算量的指数增长指数灾难能否避免？SAT问题，货郎担问题，背包问题，图着色问题，最长路径问题，……是否对于每个问题都有好的算法？什么是好的算法？什么是算法？算法的定义为实现某个任务而构成的简单指令集有穷的计算良过程通过有限多次运算可以决定的过程正确直观，非形式算法的定义希尔伯特第十问题（1900）设计一个算法来判断多项式是否有整数根算法：通过有限多次运算可以决定的过程AlanTuring&AlonzoChurch（1936）图灵机程序算法：图灵机程序形式化的，精确的图灵机（TuringMachine)带子可读可写无限长的带子读写头可左移右移

有限状态控制器1111110000000BBB1…………图灵机（TuringMachine)TM运行由确定:当前状态为q，所读字符为s

，读写头不变，，，读写头左移一格，s不变，，读写头右移一格，s不变，无定义，则停机Church-Turing论题：凡是可计算的过程都可用图灵机实现；旅行商问题的计算量（1）n個都市訪問的可能的巡回路线：n!的Stirling近似公式BigOh記法

的定数倍的大小可以忽略≈旅行商问题的计算量（2）根据Stirling公式以及O（）表示法O（nn）排序问题的计算量（1）：排序問題：S=｛a1,a2,...,an｝，n個整数列，按数值大小排列dataS输入

需O(n)時間；可能的排列種類数n!种；算法中每一个比較,都增加2倍的情形数2分树的高度（比较的次数）,

log2(n!)=O(nlog

n)x＞y?yesnon!种可能的排列排序问题计算量（2）总计算时间的复杂性：O(nlog

n)dataS输入時間(或赋值时间)：O(n)

比较时间：O(nlog

n)上位取整计算量的确定例：背包问题的贪婪算法（greedyalgorithm）的计算量确定计算量的确定计算量的确定计算量的确定计算量的确定计算量的确定计算量的确定计算的复杂度时间复杂度：

计算量:计算各基本操作的实行回数（timecomplexity）空间复杂度各计算时点内存中保持数据个数的最大值（spacecomplexity）两者的总称：计算的复杂度计算复杂度的影响因素探索空间1---解的近似度、满意度例：0—10之间的整数解：1-9共9个可行解（一维）0—10之间的实数解：精确到小数点后6位共有107个可行解（一维）；107n个可行解（n维）探索空间2---解空间大小例：桌子上有6根火柴，要求构建出4个三角形。计算复杂度的影响因素探索策略的选取计算复杂度的影响因素问题本身P问题NP问题（NP-hard，NP困难问题）NP完全问题

P类 （Polynomial) 判定问题：只有肯定和否定两种答案优化问题可以化作判定问题处理P类具有多项式时间算法的判定问题形成的计算复杂性类猜测TSP（Travelingsalesmanproblem)不属于P（J.Edmonds1965）

Pclassproblem:能用多項式時間算法求解的问题的集合称为P（polynomial）问题某一个问题属于P问题的証明某一个问题不属于P问题的証明如能够找到一个多項式時間算法

（簡単）不存在？没找到？（困难）优化问题的分类（1）NP类(NondeterministicPolynomial)NP问题：在非确定型图灵机上多项式时间可解的问题在确定型图灵机上多项式时间可验证的问题P类包含于NP类中NP类问题在确定图灵机上指数时间可解非确定型图灵机和确定型图灵机的计算能力相当优化问题的分类（2）

NPclassproblem:尚未确信能否用多項式時間算法求解的问题的集合称为NP（non-deterministicpolynomial）问题某一个问题不属于NP问题的証明某一个问题属于NP问题的証明如能够找到一个多項式時間算法

（簡単）可以归结为某一类既知的NP类问题（现阶段7类））优化问题的分类（3）（根据算法）

NP-completeproblem:集合NP中的問題=NP問題如果某个NP問題能够求解，则因所有NP問題都可以经过归结，转化为该问题，从而可以求解所有NP問題。这样的NP問題=NP完全問題——集合NP中的最难的问题=

NP完全问题计算难度比较的标准难易是比较而言的多项式时间归约（Karp归约1972)定义问题A多项式时间内转化为问题B的特殊情况，则称A可多项式归约于B，记为转化时间为多项式对于A的输入I的回答与其对应的B的输入f(I)一致NP完全与NP-hardNP完全问题：NP-hard问题：NP完全问题第一个NP完全问题（Cook定理1971）可满足性问题是NP完全问题六个NP完全问题（Karp1972)3SAT，3DM，VC，团，HC，划分更多的NP完全问题1979年：300多个1998年：2000多个P、NP、NP完全的包容关系NPNP完全旅行商問題背包問題。。。P最短路問題线性规划問題。。。NP=PNP完全大多数研究者认可的包容关系这种可能性也存在（现阶段无法证明）悬赏$100万求证NP完全问题第一个NP完全问题（Cook定理1971）可满足性问题是NP完全问题六个NP完全问题（Karp1972)3SAT，3DM，VC，团，HC，划分更多的NP完全问题1979年：300多个1998年：2000多个现在的估计如果，则指数灾难无法避免P=?NP（P-NP问题）P=NPPNPCNP如何处理NP完全问题

实际的问题不会消失油井勘探问题移动通讯中的频率分配问题并行计算以硬件设备换取时间存在着很多种并行计算模型理想模型PRAM可多项式时间解NP完全问题实际中效果不好处理器数目是受限的现实的代价：通讯，同步，……分布式计算算法的研究随机算法判定问题：以较大概率得到正确输出输出正确，但计算时间不定优化问题：输出解的性能不稳定