密码学的计算复杂性理论.ppt

《密码学的计算复杂性理论.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、密码学的计算复杂性理论算法：求解某个问题的一系列具体步骤，可能一个问题有多种算法理解为求解该问题的计算机程序）。可解与不可解：如果一个算法能解决该问题的所有实例，则称该算法能解答该问题。如果针对一个问题至少存在一个算法可以解答该问题，则称该问题是可解的。否则称为该问题是不可解的。算法与算法复杂性算法的复杂性一个算法的复杂性是由该算法所需要的最大运算时间和存储空间来度量的。它们分别是规模为n（输入数据的长度）的所有实例的时间和空间需求的平均值的函数和。一个算法的复杂性通常用符号“O”表示量级。好处在于它与处理系统无关（如：处理机速度、数据类型及表示）。表

2、示存在常数c和，对所有则称函数f(n)当n充分大时上有界，且g(n)是它的一个上界，记为f(n)=O(g(n))。即f(n)的阶不高于g(n)的阶。算法按复杂性分类多项式时间算法——时间复杂性为，k为常数。指数时间算法——时间复杂性为，t为常数，是多项式。当大于常数小于线性函数时，称为超多项式时间算法.例如：Hanoi塔问题算法的时间复杂度，可以用一个指数函数O(2n)来表示，显然，当n很大（如10000）时，计算机是无法处理的。相反，当算法的时间复杂度的表示函数是一个多项式，如O(n2)时，则可以处理。因此，一个问题求解算法的时间复杂度大于多项式（如

3、指数函数）时，算法的执行时间将随n的增加而急剧增长，以致即使是中等规模的问题也不能求解出来，于是在计算复杂性中，将这一类问题称为难解性问题。人工智能领域中的状态图搜索问题（解空间的表示或状态空间搜索问题）就是一类典型的难解性问题。建立计算机的模型——理想计算机，并研究模型的性质理想计算机中，研究什么样的问题是可解的可解的问题在实际计算机上计算的资源消耗情况并根据消耗情况对问题进行分类计算机的基本能力和限制是什么？自动机理论可计算性理论复杂性理论NP问题与计算复杂性理论图灵在1936年提出了著名的图灵机模型(计算模型)：图灵机由一个无限长的带子（被划分成

4、均匀的方格）、一个磁带读/写头和一个有限状态控制器组成。在每一步计算中，图灵机从磁带上读出一个符号，并由有限状态控制器决定是否在当前的磁带区上写入不同的符号，然后决定是否需要将磁带读/写头向前或向后移动一位。当前的计算机，在理论上都是可以被图灵机模拟的，其原理和图灵机是相同的，甚至还包含了存储程序的思想。图灵机模型bb10100010bbb……状态q读写头控制器确定的图灵机:有无限读写能力的有限自动机，每一步操作的结果唯一确定.非确定的图灵机:有无限读写能力的有限自动机，每一步操作的结果有多种选择.易解问题与难解问题:在确定图灵机上用多项式时间可解的问

5、题，称为全体易解问题,集合记为P。否则，称为难解问题。在计算复杂性理论中，将所有可以在多项式时间内求解的问题称为P问题，而将所有在多项式时间内可以验证的问题称为NP问题。由于P类问题采用的是确定性算法，NP类问题采用的是非确定性算法，而确定性算法是非确定性算法的一种特例，因此，可以断定PNP。或者说：在非确定的图灵机上用多项式时间可解的问题，称为非确定型多项式时间可解问题，即NP问题。其含义是，若机器猜测一个解，非确定的图灵机就可以在多项式时间内验证它的正确性。（即：可以在多项式时间内验证某个解是否合法的问题）全体非确定型多项式时间可解类记作NP类。

6、NP难问题：如果对于某个问题X，任意NP问题Y，可以在多项式时间内转换为（归约）到X。通俗地讲X至少和Y一样难，则称X是NP难的问题。从前，有一个酷爱数学的年轻国王向邻国一位聪明美丽的公主求婚。公主出了这样一道题：求出48770428433377171的一个真因子。若国王能在一天之内求出答案，公主便接受他的求婚。国王回去后立即开始逐个数地进行计算，他从早到晚，共算了三万多个数，最终还是没有结果。国王向公主求情，公主将答案相告：223092827是它的一个真因子。国王很快就验证了这个数确能除尽48770428433377171。公主说：“我再给你一次机会

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

8、杂性表现在空间方面。下一页直觉上，我们认为顺序算法解决不了的问题完全可以用并行算法来解决，甚至