密码学的计算复杂性理论

密码学的计算复杂性理论算法：求解某个问题的一系列具体步骤，可能一个问题有多种算法理解为求解该问题的计算机程序）。可解与不可解：如果一个算法能解决该问题的所有实例，则称该算法能解答该问题。如果针对一个问题至少存在一个算法可以解答该问题，则称该问题是可解的。否则称为该问题是不可解的。算法与算法复杂性算法的复杂性一个算法的复杂性是由该算法所需要的最大运算时间和存储空间来度量的。它们分别是规模为n（输入数据的长度）的所有实例的时间和空间需求的平均值的函数和。一个算法的复杂性通常用符号“O”表示量级。好处在于它与处理系统无关（如：处理机速度、数据类型及表示）。表示存在常数c和，对所有则称函数f(n)当n充分大时上有界，且g(n)是它的一个上界，记为f(n)=O(g(n))。即f(n)的阶不高于g(n)的阶。)(nS)(nT))(()(ngOnf0n0nn|)(|)(ngcnf算法按复杂性分类多项式时间算法——时间复杂性为，k为常数。指数时间算法——时间复杂性为，t为常数，是多项式。当大于常数小于线性函数时，称为超多项式时间算法.()kOn)()(nhtO)(nh)(nh例如：Hanoi塔问题算法的时间复杂度，可以用一个指数函数O(2n)来表示，显然，当n很大（如10000）时，计算机是无法处理的。相反，当算法的时间复杂度的表示函数是一个多项式，如O(n2)时，则可以处理。因此，一个问题求解算法的时间复杂度大于多项式（如指数函数）时，算法的执行时间将随n的增加而急剧增长，以致即使是中等规模的问题也不能求解出来，于是在计算复杂性中，将这一类问题称为难解性问题。人工智能领域中的状态图搜索问题（解空间的表示或状态空间搜索问题）就是一类典型的难解性问题。64个盘子建立计算机的模型——理想计算机，并研究模型的性质理想计算机中，研究什么样的问题是可解的可解的问题在实际计算机上计算的资源消耗情况并根据消耗情况对问题进行分类计算机的基本能力和限制是什么？自动机理论可计算性理论复杂性理论NP问题与计算复杂性理论图灵在1936年提出了著名的图灵机模型(计算模型)：图灵机由一个无限长的带子（被划分成均匀的方格）、一个磁带读/写头和一个有限状态控制器组成。在每一步计算中，图灵机从磁带上读出一个符号，并由有限状态控制器决定是否在当前的磁带区上写入不同的符号，然后决定是否需要将磁带读/写头向前或向后移动一位。当前的计算机，在理论上都是可以被图灵机模拟的，其原理和图灵机是相同的，甚至还包含了存储程序的思想。图灵机模型bb10100010bbb……状态q读写头控制器确定的图灵机:有无限读写能力的有限自动机，每一步操作的结果唯一确定.非确定的图灵机:有无限读写能力的有限自动机，每一步操作的结果有多种选择.易解问题与难解问题:在确定图灵机上用多项式时间可解的问题，称为全体易解问题,集合记为P。否则，称为难解问题。在计算复杂性理论中，将所有可以在多项式时间内求解的问题称为P问题，而将所有在多项式时间内可以验证的问题称为NP问题。由于P类问题采用的是确定性算法，NP类问题采用的是非确定性算法，而确定性算法是非确定性算法的一种特例，因此，可以断定PNP。或者说：在非确定的图灵机上用多项式时间可解的问题，称为非确定型多项式时间可解问题，即NP问题。其含义是，若机器猜测一个解，非确定的图灵机就可以在多项式时间内验证它的正确性。（即：可以在多项式时间内验证某个解是否合法的问题）全体非确定型多项式时间可解类记作NP类。NP难问题：如果对于某个问题X，任意NP问题Y，可以在多项式时间内转换为（归约）到X。通俗地讲X至少和Y一样难，则称X是NP难的问题。从前，有一个酷爱数学的年轻国王向邻国一位聪明美丽的公主求婚。公主出了这样一道题：求出48770428433377171的一个真因子。若国王能在一天之内求出答案，公主便接受他的求婚。国王回去后立即开始逐个数地进行计算，他从早到晚，共算了三万多个数，最终还是没有结果。国王向公主求情，公主将答案相告：223092827是它的一个真因子。国王很快就验证了这个数确能除尽48770428433377171。公主说：“我再给你一次机会，如果还求不出，将来你只好做我的证婚人了。”国王立即回国，并向时任宰相的大数学家求教，大数学家在仔细地思考后认为这个数为17位，则最小的一个真因子不会超过9位，于是他给国王出了一个主意：按自然数的顺序给全国的老百姓每人编一个号发下去，等公主给出数目后，立即将它们通报全国，让每个老百姓用自己的编号去除这个数，除尽了立即上报，赏金万两。最后，国王用这个办法求婚成功。返回在上例中，对公主给出的数进行验证，显然是在多项式时间内可以解决的问题，因此，这类问题属于NP类问题。国王最先使用的是一种顺序算法，其复杂性表现在时间方面，后面由宰相提出的是一种并行算法，其复杂性表现在空间方面。下一页•直觉上，我们认为顺序算法解决不了的问题完全可以用并行算法来解决，甚至会想，并行计算机系统求解问题的速度将随着处理器数目的不断增加而不断提高，从而解决难解性问题，其实这是一种误解。–当将一个问题分解到多个处理器上解决时，由于算法中不可避免地存在必须串行执行的操作，从而大大地限制了并行计算机系统的加速能力。•设f为求解某个问题的计算存在的必须串行执行的操作占整个计算的百分比，p为处理器的数目，Sp为并行计算机系统最大的加速能力，则设f=1%，p→，则Sp=100。（阿达尔定律）串行执行操作仅占全部操作1%，解题速度最多也只能提高一百倍。对难解性问题而言，提高计算机系统的速度是远远不够的，而降低算法复杂度的数量级才是最关键的问题。几个NP问题的例子：1）背包问题（子集和问题）例1：有一旅行者要从n种物品中选取不超过b公斤重的行李随身携带，要求总价值最大。如：设背包的容量为50千克。物品1重10千克，价值60元；物品2重20千克，价值100元；物品3重30千克，价值120元。求总价值最大。例2：设有n=8个体积分别为54，45，43，29，23，21，14，1的物体和一个容积为C=110的背包，问选择哪几个物体装入背包可以使其装的最满。即：由n个正整数组成的集合A=，现有整数S，确定是否有子集使得。显然，给定一个子集验证其和是否等于S是容易的。但试验所有子集的时间复杂性为，是一个NP问题.},,,{21naaaSxAxA)2(nO2)皇后问题:这是高斯1850年提出的一个著名问题：国际象棋中的“皇后”在横向、直向、和斜向都能走步和吃子，问在n×n格的棋盘上如何能摆上n个皇后而使她们都不能互相吃。当n很大时，问题很难。对于n=8,现已知此问题共有92种解，但只有12种是独立的，其余的都可以由这12种利用对称性或旋转而得到。设n=4，试一试。编程试一试，看能解到n多大？3）SAT问题判定一个n元布尔函数，是否存在一组赋值使得。称为可满足性问题（Satisfiability），简称SAT,它可以形式化地表示为：SAT=是可满足的布尔公式),,,(21nxxxfy),,,()0()0(2)0(1nxxx1),,,()0()0(2)0(1nxxxf一般是：给定一个合取范式CNF，问是否存在变量的某种取值使得CNF的值为真。例如：（A∨B）∧（~B∨D）∧（~A∨C∨~D）如果SAT问题的CNF中每个子句都恰好只有3项，我们称这类SAT问题为3-SAT，一般的问题可以转化为3SAT问题。2,3SATPSATNP启发式求解：•子句检测：如果当前取值使得某个子句为假，则立即回溯•纯符号启发：所谓纯符号是指在所有子句中以同样形式出现的变量。例如（A∨~B）∧（~B∨~C）∧（A∨C）中，A和~B是纯符号。对于所有的纯符号都可以设它们的值为真。因为对于任何一种满足整个CNF的变量取值来说，如果某个纯符号为假，把它变成真不会影响整个CNF的值。特别地，在判断纯符号时可以忽略某些已经为真的子句。•单元子句启发：单元子句是指只有一个变量的子句。单元子句的符号取值必须为真。特别地，如果某个子句中除了一个符号之外的所有符号值都为假，则这个子句也是单元子句。作业：找3-SAT的可满足解在上例中，对公主给出的数进行验证，显然是在多项式时间内可以解决的问题，因此，这类问题属于NP类问题。现在，P＝NP是否成立的问题是理论计算机科学中最大的悬而未决的问题之一。?PNP如果P=NP，则所有在多项式时间内可验证的问题都将是在多项式时间内可求解（或可判定）的问题。大多数人不相信P=NP，因为人们已经投入了大量的精力为NP中的某些问题寻找多项式时间算法，但没有成功。然而，要证明P≠NP，目前还无法做到这一点。在P＝?NP问题上，库克（S.A.Cook）等人于20世纪70年代初取得了重大的进展，他们认为NP类中的某些问题的复杂性与整个类的复杂性有关，当这些问题中的任何一个存在多项式时间算法时，则所有这些NP问题都是多项式时间可解的，这些问题被称为NP完全性问题。（可满足问题就是这类问题）也可以这样理解，NP完全问题指某个问题是NP难的并且它是一个NP问题。（解难、验证易）NP完全问题在理论和实践两方面都具有重要的研究意义。历史上第一个NP完全性问题是Cook于1971年提出的可满足性问题,SAT问题和NP问题有密切的联系。NP中的每个问题都可用多项式时间转化成为可满足问题。若可满足问题是易解的，则NP中每个问题都是易解的；若NP中某个问题都是难解的，则可满足问题也是易解的。一个NP问题称为“NP完全的”，是指NP中每个问题都可以用多项式时间转化为该问题。NP完全问题的全体记作NPC。Cook定理：CNF-satisfiablity（SAT）问题是NP-完全问题。定理（NPC性质）：若NPC中任何一个问题属于P，则所有NP问题都属于P且P=NP.推论：SATP当且仅当P=NP下一页1982年，Cook因其在计算复杂性理论方面（主要是在NP完全性理论方面）的奠基性工作而荣获ACM图灵奖。在Cook工作的影响下，卡普（R.Karp）随后证明了21个有关组合优化的问题，也是NP完全性问题，从而加强和发展了NP完全性理论。卡普由于在计算复杂性理论、算法设计与分析、随机化算法等方面的创造性贡献，于1985年获ACM图灵奖。现在，在计算科学、数学、逻辑学以及运筹学领域中已发现有总数多达数千个的NP完全性问题。其中有代表性的有：可满足问题、哈密尔顿回路问题、旅行商问题（也称货郎担问题）、划分问题、带优先级次序的处理机调度问题、顶点覆盖问题等。返回–证明问题Q是NP-完全问题的步骤：(1)选择一已知的NP-完全问题P。(2)证明P可多项式地约化为Q多项式时间归约的概念多项式时间归约是比较两个问题的相对难度的重要手段。对于两个问题X和Y，用T(X)和T(Y)表示它们的时间复杂度。如果T(Y)=f(T(X))，其中f是一个多项式函数，则写作Y=pX，即Y可以在多项式时间内归约到X。通俗地讲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完全的定义有Z=pY，根据传递性得Z=pX。又X是NP问题，根据定义得X是NP完全问题。问题Q是NP-难问题。如果：每个NP问题都可多项式地约化为问题Q.问题Q是NP-完全问题。如果:它是NP问题，同时它还是NP-难问题.NPC是闭的(自反,对称,传递)，指所有这些问题可互相约化：找到一个问题的多项式算法则全部解决。NP-完全问题例子：装箱问题：•给定一个整数集合，问是否可以把它划分为最多k个子集，使得每个子集之和均不超过C。–优化问