计算复杂性的回顾

《计算复杂性的回顾》由会员分享，可在线阅读，更多相关《计算复杂性的回顾（14页珍藏版）》请在金锄头文库上搜索。

1、计算复杂性的回顾Stephen A.Cook1 早期的论文算法复杂性问题的前史大概可以追溯到艾伦图灵在 1937 年的这篇论文，论文是论可计算数机器在判定问题中的应用。图灵介绍了他著名的图灵机，提出了使人信服的公式化观点，这个观点是有效的可计算函数。曾经这个想法正好被压制了，对于可计算的不可能证据出现了可能。在同一篇论文中，图灵提出了给定一个可预测的微积分的任意的一个公式，在有限的时间内没有任何一种算法可以证明这个公式是可满足的。在解释什么样的问题能被计算机解决或不能解决这个理论很好的发展之后，很自然的想到可计算函数的相关计算难度在哪。这就是计算复杂性问题。Rabin是第一批详细的从事这类问题

2、人之一：f 比 g 更难计算是什么意思？Rabin 提供了抽象复杂性理论的基础，这个理论被 Blum 和其他人所发展。第二篇早期的有影响力的论文是 J.Hartmanis 和 R.E.Stearns 写的计算复杂性的算法。这篇论文被广泛阅读，给这个领域一个名字。这篇论文引入了复杂性度量的观点，复杂性度量被多图灵机在可计算时间内定义，层次理论被证明。这篇论文还提出了一个至今未解决的有趣的问题：任何无理数在实时内都是可计算的吗？也就是说，图灵机能永远按照每 100 步一个单位的速率把无理数扩展为十进制打印出来吗？第三篇论文是 Alan Cobham 写的内在的计算难度。Alan Cobham 强调

3、“内在”，换句话说，他对独立机器理论感兴趣。他想知道乘法是否比加法难，并且他相信直到这个理论完全发展了，这个问题才能解决。Cobham 也定义了和刻画了函数的重要的类：这些函数在自然数内和有限时间内是可计算的，时间限制是输入的十进制长度的多项式。另外三篇论文影响着以上作者和其他研究复杂性的工作者，他们是Yamada，Bennett，Ritchie。有趣的是 Rabin，Stearns，Bennett 和 Ritchie同时都是普林斯顿大学的学生。2 早期的观点和概念几个早期的作者关心这个问题：什么是正确的复杂性度量？大多数人认为复杂性时间和空间是明显的选择，但是不能确定这些是唯一的或者正确的。

4、比如，Cobham 说和物理相关的概念的工作的一些测量可指导最满意的分析。Rabin 引入了可以使复杂性度量可满足的公理。根据 20 多年的经验观点，我现在认为时间和空间，尤其是时间是最重要的复杂性度量。评价一个算法的效率，第一个能体现算法价值的应该是算法的运行时间。然而，近年来，并行时间和硬件资源越来越是度量复杂性的重要手段。另一个重要的复杂性度量是组合复杂性。这里假定函数 f 是把有限的位字符串转化为有限的位字符串，对于所有长度为 n 的输入，f 的复杂度 C（n）是所有组合中最小的复杂度。这个普通的测量和计算时间紧紧相关，也发展成为理论。Cobham 提出的另外一个问题是在计算问题中，

5、“步”由什么组成？对于度量一个算法的可计算时间，哪种计算机模型是正确的模型？多图灵机在这篇文献中经常被用到，但是他们被算法的执行效率所局限。比如，没有强制性的原因说存储介质必须是线性磁带。为什么不是平坦的矩阵或是树型？为什么不允许随机存储记忆？事实上，自 1960 年来，好多计算模型被提出。因为真实的计算机有随机存储记忆，很自然的被用到这个模型中。但是怎么用是一个很棘手的问题。如果机器在一个步内能存储整型，对他们的大小必须要限制。 （如果 2 被平方 100 次，结果将有 2 的 100 次方位，这些位能存储世界上所有已存在的存储介质。 ）我在文献 19 里面提出了 RAMs，每次 logx

6、的代价都能得到，x 可以存储也可以查找。一个流行的随机存储模型是 Aho，Hopcroft 和 Ullman 在文献 3 里面提出的，每次涉及到整型的操作都有一个单元的代价，但是不能达到不合理的大小（比如，这些数字的大小被固定多项式限制，这些多项式是输入的长度） 。或许最满意的计算模型是舍恩洛克的存储修正机器，这个机器可以被看成是图灵机，它有自己的存储机构，或者被看做一个单元代价 RAM，它在每一个步只能复制，增加或存储或查找。舍恩洛克的机器。对于我来说意味着大多数机器都能在每一步做有限制的工作。困难是可能只有一点强大。 （看第三部分的大数乘法） 。回到 Cobham 的问题，什么是“步” 。

7、我认为在最近的 20 年内没有一个明确的答案。幸运的是，完全的计算模型在可计算时间内都没有很大的区别。总的来说，每一个都能模仿另一个。 （有些这方面的争论在文献 37 中） 。在这些最主要的随机存取模型中，只有 log 计算时间这个重要因素正在被讨论。这导致了在 1965 年形成的最终重要的概念：在输入的多项式时间内可以解决的问题的分类的定义。在多项式时间和指数时间的特征的算法早在 1953 年由von Neumann 提出。然而，这个类别没有被正式定义和研究直到 Cobham 在 1964年提出函数的类（看第一部分） 。Cobham 指出这个类被很好的定义，和选择的计算模型无关，在回归函数理

8、论中给它描述了一个定义。Edmonds 第一次在出版的论文里提出在多项式时间的计算是比较容易的，他认为多项式时间的算法是好的算法。Karp 引入了现在标准符号 P，表示可认识的多项式时间类的字符串集合。从 1970 年早期开始，P 在这个领域代表易处理的问题被人们广泛接受。不是立即很明显的知道这应该是正确的，因为一个算法的运行时间是多项式 n 的1000 次是不可行的，相反的，谁的运行时间是指数 2 的 0.0001n 次在实际上是可行的。这好像是个经验事实，然而，这个狠自然提出的问题在这样一个运行时间内没有最优化的算法。有最坏指数运行时间的最明显实际的算法是线性规划中单一算法。在文献 75

9、和 76 中试图解释展示这个问题，从某种意义上说，平均运行时间很快，但是 Khachian 用其他算法展示了在 P 时间内的线性规划也是值得重视的。因此，我们大部分的论文没有违背 P 相当于可解决的问题这个观点。3.时间上界计算机科学研究的内容包括设计和分析的大规模数据高效算法。（从计算复杂性的角度来看）特别重要的算法必须以某种方式，他们通常提供一个解决一个重要问题，令人惊讶的简单或快速的方法。下面我列出一些更有趣的自1960 年发明。（顺便说一句，猜测是有史以来最重要的算法是件有趣的事；无疑算术运算+， - *和 - 十进制数字是基本的算符，我认为快速排序和查找，高斯消去法及欧几里得算法和单

10、纯形算法是比较重要的自 1960 年以来。）参数 n 是指对输入的大小和时间界限是最坏情况下的时间范围，并适用于一多带图灵机除特别注明（或任何合理的随机存取机） 。快速傅里叶变换，要求为 O（nlogn）的算术运算，是科学计算中最常用的算法之一； （2）大数乘法。最基本的方法需要 O（n 2）的位操作乘以两个 N 位数字。 1962 年 Karatsuba 和 Ofman 41发表的方法只需要为 O（nl.59）复杂度,之后不久 Toom84，展示了如何构建（任意小 0）大小为 O（）布尔电路，1n以开展乘法运算。我是当时在哈佛大学毕业的学生，由 Cobham 的问题启发“是乘法难度比加法大？

11、”我是天真地试图证明乘法，乘法需要一个图灵机（n2）的步骤。Toom 提交的文件给了我很大的惊喜。在 Aanderaa 22帮助下，我减少乘法的复杂性，即使用的“在线”图灵机需要（nlogn /（loglogn）2）步骤；我也指出，Toom 的方法可适应乘法图灵机，需要 O（）的步骤，在这一点上 Toom 与我肯定有相同的看法。1n目前运行速度最快的渐进图灵机在数值乘法中异步运行时间为O（nlognloglogn），是由 Sch6nhage 和 Strassen 70（1971 年）采用快速傅立叶变换的设计。然而，Sch6nhage 69最近由一个复杂的参数修改，他的存储设备（见第 2 节）乘

12、法运行的时间为为 O（n）（线性时间！）。我们不得不得出这样的结论要么乘法是比我们想象的更容易或 Sch6nhage 的机器作弊。（3）矩阵乘法。最明显的方法需要）算术操作，将两个 nxn 的矩) 12(2nn阵，并尝试进行了证明，这在 1950 年和 1960 年最佳方法的。当 Strassen 的81(1969 年)发布了他的方法只需要 4.7Tm 运算时间。相当多的工作一直致力于减少 2.81 指数，目前已知的最佳时间是 O（112496）操作，是科珀和Winograd 24做出的。还有很多改进的空间，因为众所周知的下界是 2n2 - 1（见13）（4）一般无向图的最大匹配。这也许是第一

13、个问题明确的显示谁的成员在P 中的算法比较复杂。Edmonds 有影响力的论文27给出了结果并讨论了多项式的时间算法（参见第二部分） 。他指出简单的满足双边的情况并不适用一般的无向图。（5）确认素数。现在主要问题是确定这个问题是不是在 P 中。换句话说，是否有一个算法总能告诉我们输入的 n 位数字是不是一个素数，一个固定的有界 n项多项式是否停止？Gary Miller 53 (1976 年)表明，有这样的算法，其有效性取决于扩展的黎曼算法。Solovay 和 Strassen 77发明了一种快速的蒙特卡罗素数识别算法，但是如果输入的数字是合成的那么有一定的小概率会误判。现在知道的最好的证明算

14、法是 Adleman, Pomerance, and Rumely 2提出的，时间复杂度为，稍微差于多项式算法。由于这方面的变化，H. (loglog )OnnCohen 和 H.W. Lenstra Jr. 17经常可以处理多达一百个十进制数大约需时45 秒钟。最近，在类 P 中三个重要的问题已经被证明了。第一个问题是线性规划问题由 Khachian 43（参见55）于 1979 年证明。第二个问题是判定两个图的度数之多 d 是同构的，由 Luks 50 于 1980 年证明（该算法是多项式的顶点固定 d，但是指数在 d） 。第三个问题是考虑有理系数多项式因子，这被Lenstra,Lenst

15、ra, and Lovasz 48 在 1982 年，证明是含一个变量的多项式。Kaltofens result 39, 40证明它可以被化为一般的变量固定的多项式。所有重要时间复杂度或者空间复杂度的下界都是基于“对角线的理论” 。图灵和与他同期的人使用对角线理论去证明些问题而不是通过算法可解。他们也用 1960 年之前确定的多层次可计算 0-1 函数。在 1960 年，Rabin 60证明了任何合理的复杂性措施，如计算时间或空间（内存） ，允许充分增加时间、空间等条件，也允许更多的 0-1 计算。大约在同一时间，Ritchie 在他的论文65中在空间允许的数量内，定义一个特定的功能层次结构（

16、他证明了 0-1 函数的平凡性） 。之后，Rabin 的结论被 Hartmanis 和 Stearns 37更详细研究用于时序多带图灵机，被 Stearns, Hartmanis, and Lewis 78用于空间复杂度。上述的层次结构的结果可用来各处计算特定函数所需的时间和空间的下限，但这些函数看起来是“人为的” 。例如，很容易看到函数 f(x,y),在输入 x 后经过计算输出 y，不能再时间内算出。知道 1972 年，Albert 2(+)xy2(+)xyMeyer and Larry Stockmeyer 52证明了正则表达式的等价问题需要指数空间，因此，指数时间，一个对一般模型平凡的更低的下界，一个“自然的”问题被发现（自然指的是有趣，而不是关于计算机的） 。4.1 非人为可决定的问题被证明是不可解的综合考虑到上述因素得出的分层结果，给出了计算特定函数所需时间和空间的下界。但是，所有这样的函数看起来都是“勉强”的。例如，需经过 (|x|+|y|)2 个步骤