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

密码学的计算复杂性理论,幽默来自智慧，恶语来自无能,口密码学的计算复杂性理论,算法与算法复杂性口算法:求解某个问题的一系列具体步骤,可能一个问题有多种算法理解为求解该问题的计算机程序)。口可解与不可解:如果一个算法能解决该问题的所有实例,则称该算法能解答该问题。如果针对一个问题至少存在个算法可以解答该问题,则称该问题是可解的。否则称为该问题是不可解的。,口算法的复杂性个算法的复杂性是由该算法所需要的最大运算时间和存储空间来度量的。它们分别是规模为n(输入数据的长度)的所有实例的时间和空间需求的平均值的函数7(n)和S(n)个算法的复杂性通常用符号“O”表示量级。好处在于它与处理系统无关(如:处理机速度、数据类型及表示)。f(m)=O(g(n)表示存在常数c和n,对所有nnf(n)cl(m)则称函数f(m)当n充分大时上有界,且g(是它的一个上界,记为f(n)=0(g(n)。即f(m)的阶不高于g(n)的阶。,口算法按复杂性分类多项式时间算法时间复杂性为O(n),k为常数。指数时间算法时间复杂性为O(),t为常数,h(n)是多项式。当h(n)大于常数小于线性函数时,称为超多项式时间算法,例如:Hanoi塔问题算法的时间复杂度,可以用一个指数函数O(2)来表示,显然,当n很大(如10000时,计算机是无法处理的。相反,当算法的时间复杂度的表示函数是一个多项式,如O(n2)时,则可以处理。因此,一个问题求解算法的时间复杂度大于多项式(如指数函数)时,算法的执行时间将随n的增加而急剧增长,以致即使是中等规模的问题也不能求解出来,于是在计算复杂性中,将这一类问题称为难解性问题。人工智能领域中的状态图搜索问题(解空间的表示或状态空间搜索问题)就是一类典型的难解性问题。64个盘子,NP问题与计算复杂性理论理自机m计算机,并明究模型的性质一论就的性可单现想计算机中,研究什论算mn可解的问题在实际计算机上理复么计算的资源消耗情况并根据一论杂消耗情况对问题进行分类性,口图灵机模型读写头状态控制器图灵在1936年提出了著名的图灵机模型(计算模型):n图灵机由一个无限长的带子(被划分成均匀的方格)、一个磁带读/写头和一个有限状态控制器组成。在每一步计算中,图灵机从磁带上读出一个符号,并由有限状态控制器决定是否在当前的磁带区上写入不同的符号,然后决定是否需要将磁带读/写头向前或向后移动一位。当前的计算机,在理论上都是可以被图灵机模拟的,其原理和图灵机是相同的,甚至还包含了存储程序的思想,口确定的图灵机:有无限读写能力的有限自动机,每一步操作的结果唯一确定口非确定的图灵机:有无限读写能力的有限自动机,每一步操作的结果有多种选择口易解问题与难解问题:在确定图灵机上用多项式时间可解的问题,称为全体易解问题集合记为P。否则,称为难解问题。在计算复杂性理论中,将所有可以在多项式时间内求解的问题称为P问题,而将所有在多项式时间内可以验证的问题称为NP问题。由于P类问题采用的是确定性算法,NP类问题釆用的是非确定性算法,而确定性算法是非确定性算法的一种特例,因此,可以断定PcNP。,或者说:在非确定的图灵机上用多项式时间可解的问题,称为非确定型多项式时间可解问题,即NP问题。其含义是若机器猜测一个解,非确定的图灵机就可以在多项式时间内验证它的正确性。(即:可以在多项式时间内验证某个解是否合法的问题)全体非确定型多项式时间可解类记作NP类。NP难问题:如果对于某个问题X,任意NP问题Y,可以在多项式时间内转换为(归约)到。通俗地讲X至少和Y一样难,则称X是NP难的问题。,从前,有一个酷爱数学的年轻国王向邻国一位聪明美丽的公主求婚。公主出了这样一道题:求出48770428433377171的一个真因子。若国王能在一天之内求出答案,公主便接受他的求婚。国王回去后立即开始逐个数地进行计算,他从早到晩,共算了三万多个数,最终还是没有结果。国王向公主求情,公主将答案相告:223092827是它的一个真因子。国王很快就验证了这个数确能除尽48770428433377171。公主说:“我再给你一次机会,如果还求不出,将来你只好做我的证婚人了。”国王立即回国,并向时任宰相的大数学家求教,大数学家在仔细地思考后认为这个数为17位,则最小的一个真因子不会超过9位,于是他给国王出了一个主意:按自然数的顺序给全国的老百姓每人编一个号发下去,等公主给出数目后,立即将它们通报全国,让每个老百姓用自己的编号去除这个数,除尽了立即上报,赏金万两。最后,国王用这个办法求婚成功。返回,31、只有永远躺在泥坑里的人，才不会再掉进坑里。黑格尔32、希望的灯一旦熄灭，生活刹那间变成了一片黑暗。普列姆昌德33、希望是人生的乳母。科策布34、形成天才的决定因素应该是勤奋。郭沫若35、学到很多东西的诀窍，就是一下子不要学很多。洛克,