密码学的计算复杂性理论

1、q 密码学的计算复杂性理论密码学的计算复杂性理论q算法：算法：求解某个问题的一系列具体步骤，可能一个问题求解某个问题的一系列具体步骤，可能一个问题 有多种算法有多种算法 理解为求解该问题的计算机程序）。理解为求解该问题的计算机程序）。q可解与不可解：可解与不可解：如果一个算法能解决该问题的所有实例，如果一个算法能解决该问题的所有实例，则称该则称该算法能解答该问题算法能解答该问题。如果针对一个问题至少存在一。如果针对一个问题至少存在一个算法可以解答该问题，个算法可以解答该问题， 则则称该问题是称该问题是可解的可解的。否则称为。否则称为该问题是该问题是不可解的不可解的。 算法与算法复杂性算法与算法

2、复杂性q算法的复杂性算法的复杂性 一个算法的复杂性是由该算法所需要的最大运算时一个算法的复杂性是由该算法所需要的最大运算时间和存储空间来度量的。它们分别是规模为间和存储空间来度量的。它们分别是规模为n（输入数据（输入数据的长度）的所有实例的时间和空间需求的平均值的函数的长度）的所有实例的时间和空间需求的平均值的函数 和和 。 一个算法的复杂性通常用符号一个算法的复杂性通常用符号“O”表示量级。好表示量级。好处在于它与处理系统无关（如：处理机速度、数据类型处在于它与处理系统无关（如：处理机速度、数据类型及表示）。及表示）。 表示存在常数表示存在常数 c和和 ，对所有，对所有 则称函数f(n)当n

3、充分大时上有界，且g(n)是它的一个上界，记为f(n)=O(g(n)。即f(n)的阶不高于g(n)的阶。 )(nS)(nT)()(ngOnf0n0nn | )(|)(ngcnfq算法按复杂性分类算法按复杂性分类 多项式时间算法多项式时间算法时间复杂性为时间复杂性为 ，k为常数。为常数。 指数时间算法指数时间算法时间复杂性为时间复杂性为 ，t为常数，为常数， 是多项式。是多项式。 当当 大于常数小于线性函数时，称为超多项式时大于常数小于线性函数时，称为超多项式时间算法间算法.()kO n)()(nhtO)(nh)(nh例如：Hanoi塔问题算法的时间复杂度，可以用一个指数函数O(2n)来表示，显

4、然，当n很大（如10000）时，计算机是无法处理的。相反，当算法的时间复杂度的表示函数是一个多项式，如O(n2)时，则可以处理。因此，一个问题求解算法的时间复杂度大于多项式（如指数函数）时，算法的执行时间将随n的增加而急剧增长，以致即使是中等规模的问题也不能求解出来，于是在计算复杂性中，将这一类问题称为难解性问题。人工智能领域中的状态图搜索问题（解空间的表示或状态空间搜索问题）就是一类典型的难解性问题。 64个个盘盘子子 建立计算机的模型理想计算机，并研究模型的性质理想计算机中，研究什么样的问题是可解的可解的问题在实际计算机上计算的资源消耗情况并根据消耗情况对问题进行分类计算机的基本能力和限制

5、是什么？计算机的基本能力和限制是什么？自动机理论可计算性理论复杂性理论NP问题与计算复杂性理论问题与计算复杂性理论图灵在图灵在19361936年提出了著名的图灵机模型年提出了著名的图灵机模型( (计算模型计算模型) )：图灵机由一个无限长的带子（被划分成均匀的方格）图灵机由一个无限长的带子（被划分成均匀的方格） 、一个、一个磁带读磁带读/ /写头和一个有限状态控制器组成。写头和一个有限状态控制器组成。在每一步计算中，图灵机从磁带上读出一个符号，并由有限在每一步计算中，图灵机从磁带上读出一个符号，并由有限状态控制器决定是否在当前的磁带区上写入不同的符号，然后状态控制器决定是否在当前的磁带区上写入

6、不同的符号，然后决定是否需要将磁带读决定是否需要将磁带读/ /写头向前或向后移动一位。写头向前或向后移动一位。当前的计算机，在理论上都是可以被图灵机模拟的，其原理和当前的计算机，在理论上都是可以被图灵机模拟的，其原理和图灵机是相同的，甚至还包含了存储程序的思想。图灵机是相同的，甚至还包含了存储程序的思想。 q图灵机模型图灵机模型b b10100010b b b状态状态q读写头读写头控制器控制器q确定的图灵机确定的图灵机: 有无限读写能力的有限自动机，每有无限读写能力的有限自动机，每一步操作的结果唯一确定一步操作的结果唯一确定.q非确定的图灵机非确定的图灵机: 有无限读写能力的有限自动机，每有无

7、限读写能力的有限自动机，每一步操作的结果有多种选择一步操作的结果有多种选择.q易解问题与难解问题易解问题与难解问题: 在确定图灵机上用多项式时间在确定图灵机上用多项式时间可解的问题，称为全体易解问题可解的问题，称为全体易解问题,集合记为集合记为P。否则，称。否则，称为难解问题。为难解问题。 在计算复杂性理论中，将所有可以在多项式时间内求解的问题称为P问题，而将所有在多项式时间内可以验证的问题称为NP问题。由于P类问题采用的是确定性算法，NP类问题采用的是非确定性算法，而确定性算法是非确定性算法的一种特例，因此，可以断定PNP。或者说：或者说： 在非确定的图灵机上用多项式时间可解的问题，称在非确

8、定的图灵机上用多项式时间可解的问题，称为非确定型多项式时间可解问题，即为非确定型多项式时间可解问题，即NP问题问题。其含义是，。其含义是，若机器猜测一个解，非确定的图灵机就可以在多项式时间若机器猜测一个解，非确定的图灵机就可以在多项式时间内验证它的正确性。（内验证它的正确性。（即：可以在多项式时间内验证某个解是否即：可以在多项式时间内验证某个解是否合法的问题合法的问题） 全体非确定型多项式时间可解类记作全体非确定型多项式时间可解类记作NP类类。 NP难问题：如果对于某个问题X，任意NP问题Y，可以在多项式时间内可以在多项式时间内转换转换为为（归约）到（归约）到X。通俗地通俗地讲讲X至少和至少和

9、Y一样难一样难， 则称X是NP难的问题。 从前，有一个酷爱数学的年轻国王向邻国一位聪明美丽的公主求婚。公主出了这样一道题：求出48 770 428 433 377 171的一个真因子。若国王能在一天之内求出答案，公主便接受他的求婚。国王回去后立即开始逐个数地进行计算，他从早到晚，共算了三万多个数，最终还是没有结果。国王向公主求情，公主将答案相告：223 092 827是它的一个真因子。国王很快就验证了这个数确能除尽48 770 428 433 377 171。公主说：“我再给你一次机会，如果还求不出，将来你只好做我的证婚人了。”国王立即回国，并向时任宰相的大数学家求教，大数学家在仔细地思考后认

10、为这个数为17位，则最小的一个真因子不会超过9位，于是他给国王出了一个主意：按自然数的顺序给全国的老百姓每人编一个号发下去，等公主给出数目后，立即将它们通报全国，让每个老百姓用自己的编号去除这个数，除尽了立即上报，赏金万两。最后，国王用这个办法求婚成功。返 回 在上例中，对公主给出的数进行验证，显然是在多项式时间内可以解决的问题，因此，这类问题属于NP类问题。v国王最先使用的是一种顺序算法，其复杂性国王最先使用的是一种顺序算法，其复杂性表现在时间方面，表现在时间方面，v后面由宰相提出的是一种并行算法，其复杂后面由宰相提出的是一种并行算法，其复杂性表现在空间方面。性表现在空间方面。 下一页直觉上

11、，我们认为顺序算法解决不了的问题直觉上，我们认为顺序算法解决不了的问题完全可以用并行算法来解决，甚至会想，并完全可以用并行算法来解决，甚至会想，并行计算机系统求解问题的速度将随着处理器行计算机系统求解问题的速度将随着处理器数目的不断增加而不断提高，从而解决难解数目的不断增加而不断提高，从而解决难解性问题，其实这是一种误解。性问题，其实这是一种误解。当将一个问题分解到多个处理器上解决时，由于当将一个问题分解到多个处理器上解决时，由于算法中不可避免地存在必须串行执行的操作，从算法中不可避免地存在必须串行执行的操作，从而大大地限制了并行计算机系统的加速能力。而大大地限制了并行计算机系统的加速能力。设

12、f为求解某个问题的计算存在的必须串行执行的操作占整个计算的百分比，p为处理器的数目，Sp为并行计算机系统最大的加速能力，则 设f=1%，p，则Sp=100。（阿达尔定律阿达尔定律）串行执行操作仅占全部操作1%，解题速度最多也只能提高一百倍。对难解性问题而言，提高计算机系统的速度是远远不够的，而降低算法复杂度的数量级才是最关键的问题。几个几个NP问题的例子：问题的例子：1）背包问题（子集和问题）背包问题（子集和问题） 例例1：有一旅行者要从n种物品中选取不超过b公斤重的行李随身携带，要求总价值最大。如：设背包的容量为50千克。物品1重10千克，价值60元；物品2重20千克，价值100元；物品3重

13、30千克，价值120元。求总价值最大。 例例2 2：设有n=8个体积分别为54，45，43，29，23，21，14，1的物体和一个容积为C=110的背包，问选择哪几个物体装入背包可以使其装的最满。 即：由由n个正整数组成的集合个正整数组成的集合A = ，现有整，现有整 数数S，确定是否有子集确定是否有子集 使得使得 。显然，给定一个子集验证其和是否等于显然，给定一个子集验证其和是否等于S是容易的。但试验是容易的。但试验所有子集的时间复杂性为所有子集的时间复杂性为 ，是一个，是一个NP问题问题. , , ,21naaaSxAxA)2(nO2) 2) 皇后问题皇后问题:这是高斯1850年提出的一个

14、著名问题： 国际象棋中的“皇后”在横向、直向、和斜向都能走步和吃子，问在nn 格的棋盘上如何能摆上n个皇后而使她们都不能互相吃。 当n很大时，问题很难。 对于n=8,现已知此问题共有92种解，但只有12种是独立的，其余的都可以由这12种利用对称性或旋转而得到。 设n=4，试一试。 编程试一试，看能解到n多大？3）SAT问题问题 判定一个判定一个n元布尔函数元布尔函数 ，是否存在一组赋值，是否存在一组赋值 使得使得 。称为。称为可满足性问题（Satisfiability），简称SAT,它可以形式化地表示为： SAT= 是可满足的布尔公式),(21nxxxfy),()0()0(2)0(1nxxx1

15、),()0()0(2)0(1nxxxf 一般是：给定一个合取范式CNF，问是否存在变量的某种取值使得CNF的值为真。例如：（AB）（BD）（ACD）n如果SAT问题的CNF中每个子句都恰好只有3项，我们称这类SAT问题为3-SAT，一般的问题可以转化为3SAT问题。2,3SATPSATNP启发式求解：启发式求解：子句检测：如果当前取值使得某个子句为假，则立即回溯纯符号启发：所谓纯符号是指在所有子句中以同样形式出现的变量。例如（AB）（BC）（AC）中，A和B是纯符号。对于所有的纯符号都可以设它们的值为真。因为对于任何一种满足整个CNF的变量取值来说，如果某个纯符号为假，把它变成真不会影响整个C

16、NF的值。特别地，在判断纯符号时可以忽略某些已经为真的子句。单元子句启发：单元子句是指只有一个变量的子句。单元子句的符号取值必须为真。特别地，如果某个子句中除了一个符号之外的所有符号值都为假，则这个子句也是单元子句。作业：找3-SAT的可满足解 在上例中，对公主给出的数进行验证，显然是在多项式时间内可以解决的问题，因此，这类问题属于NP类问题。 现在，PNP是否成立的问题是理论计算机科学中最大的悬而未决的问题之一。?PNP 如果P=NP，则所有在多项式时间内可验证的问题都将是在多项式时间内可求解（或可判定）的问题。大多数人不相信P=NP，因为人们已经投入了大量的精力为NP中的某些问题寻找多项式

17、时间算法，但没有成功。然而，要证明PNP，目前还无法做到这一点。 在P?NP问题上，库克（S.A.Cook）等人于20世纪70年代初取得了重大的进展，他们认为NP类中的某些问题的复杂性与整个类的复杂性有关，当这些问题中的任何一个存在多项式时间算法时，则所有这些NP问题都是多项式时间可解的，这些问题被称为NP完全性问题。（可满足问题就是这类问题） 也可以这样理解，NP完全问题指某个问题是NP难的并且它是一个NP问题。（解难、验证易） NP完全问题在理论和实践两方面都具有重要的研究意义。历史上第一个NP完全性问题是Cook于1971年提出的可满足性问题,SAT问题和NP问题有密切的联系。 NP中的

18、每个问题都可用多中的每个问题都可用多项式时间转化成为可满足问题。若可满足问题是易解的，项式时间转化成为可满足问题。若可满足问题是易解的，则则NP中每个问题都是易解的；若中每个问题都是易解的；若NP中某个问题都是难解中某个问题都是难解的，则可满足问题也是易解的。一个的，则可满足问题也是易解的。一个NP问题称为问题称为“NP完完全的全的”，是指，是指NP中每个问题都可以用多项式时间转化为中每个问题都可以用多项式时间转化为该问题。该问题。NP完全问题的全体记作完全问题的全体记作NPC。Cook定理：CNF-satisfiablity（SAT）问题是NP-完全问题。定理（NPC性质）：性质）：若若NP

19、C中任何一个问题属于中任何一个问题属于P，则所，则所有有NP问题都属于问题都属于P且且P=NP.推论： SATP 当且仅当P=NP下一页 1982年， Cook因其在计算复杂性理论方面（主要是在NP完全性理论方面）的奠基性工作而荣获ACM图灵奖。 在Cook工作的影响下，卡普（R.Karp）随后证明了21个有关组合优化的问题，也是NP完全性问题，从而加强和发展了NP完全性理论。卡普由于在计算复杂性理论、算法设计与分析、随机化算法等方面的创造性贡献，于1985年获ACM图灵奖。 现在，在计算科学、数学、逻辑学以及运筹学领域中已发现有总数多达数千个的NP完全性问题。其中有代表性的有：可满足问题哈密

20、尔顿回路问题、旅行商问题（也称货郎担问题）、划分问题、带优先级次序的处理机调度问题、顶点覆盖问题等。 返 回 证明问题Q是NP-完全问题的步骤： (1)选择一已知的NP-完全问题P。 (2)证明P可多项式地约化为 Q&多项式时间归约是比较两个问题的相对难度的重要手多项式时间归约是比较两个问题的相对难度的重要手段。段。&对于两个问题对于两个问题X和和Y，用用T(X)和和T(Y)表示它们的时间复表示它们的时间复杂度。如果杂度。如果T(Y)=f(T(X)，其中其中f是一个多项式函数，是一个多项式函数，则写作则写作Y=pX，即即Y可以在多项式时间内归约到可以在多项式时间内归约到X。通通

21、俗地讲俗地讲X至少和至少和Y一样难。一样难。&定理定理1：设设Y=pX。如果如果X存在多项式时间解法，则存在多项式时间解法，则Y同样存在多项式时间解法。同样存在多项式时间解法。&定理定理2：设设Y=pX。如果如果Y不存在多项式时间解法，则不存在多项式时间解法，则X同样不存在多项式时间解法。同样不存在多项式时间解法。&定理定理3：设设Z=pY，Y=pX，则则Z=pX所所以以，证明一个问题是，证明一个问题是NP完全的完全的可可以这样做以这样做：&定理：如果Y是一个NP完全问题，X是一个NP问题，并且有Y=pX，则X也是NP完全的。 证明：对于任意NP问题Z，根据NP

22、完全的定义有Z=pY，根据传递性得Z=pX。又X是NP问题，根据定义得X是NP完全问题。&问题问题Q是是NP-难问题。如果：每个难问题。如果：每个NP问问题都可多项式地约化为问题题都可多项式地约化为问题 Q.&问题问题 Q 是是 NP-完全问题完全问题。如果如果:它是它是NP问题，同时它还是问题，同时它还是NP-难问题难问题.&NPC是闭的是闭的(自反自反,对称对称,传递传递)，指所有这，指所有这些问题可互相约化：找到一个问题的多些问题可互相约化：找到一个问题的多项式算法则全部解决。项式算法则全部解决。NP-完全问题例子完全问题例子：q装箱问题： 给定一个整数集合，问是

23、否可以把它划分为最多k个子集，使得每个子集之和均不超过C。 优化问题：求使用最小箱数的装箱方法 判定问题：任意给定k，是否存在一种装箱方法：用k个箱子将这些物品全部装入？q图的k着色 给定一个简单无向图，问是否能够用不超过k种颜色给图的每一个顶点着色，使得相邻顶点的颜色不同。 特别地：图的3着色判定问题也是NP完全问题q团 若完全图G1是图G的子图，称G1是G的团。 团的问题：给定一个简单无向图，问是否存在顶点数为k的团。q哈密尔顿回路 给定一个有向图，问是否存在一条回路经过每个顶点一次且仅有一次。q旅行商问题 给定一张带权完全有向图，问是否存在这样一条路径：它遍历每个顶点一次且仅有一次，并且长度不超过L。q整数子集和 给定一个整数集合，问是否存在某个子集的和等于S。q整数划分 给定一个整数集合，问是否能够把它分成两个集合，使得两部分的和相等。q任务调度 给定一个任务集合以及每个任务相应的最早开始时间、最迟完成时间和执行所需时间，问是