计算复杂性的回顾

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

2、：f比g更难计算是什么意思？Rabin提供了抽象复杂性理论的基础，这个理论被Blum和其他人所发展。第三篇论文是Alan Cobham写的内在的计算难度。Alan Cobham强调“内在”，换句话说，他对独立机器理论感兴趣。他想知道乘法是否比加法难，并且他相信直到这个理论完全发展了，这个问题才能解决。Cobham也定义了和刻画了函数的重要的类：这些函数在自然数内和有限时间内是可计算的，时间限制是输入的十进制长度的多项式。另外三篇论文影响着以上作者和其他研究复杂性的工作者，他们是Yamada，Bennett，Ritchie。有趣的是Rabin，Stearns，Bennett和Ritchie同时都

3、是普林斯顿大学的学生。2早期的观点和概念几个早期的作者关心这个问题：什么是正确的复杂性度量？大多数人认为复杂性时间和空间是明显的选择，但是不能确定这些是唯一的或者正确的。比如，Cobham说和物理相关的概念的工作的一些测量可指导最满意的分析。Rabin引入了可以使复杂性度量可满足的公理。根据20多年的经验观点，我现在认为时间和空间，尤其是时间是最重要的复杂性度量。评价一个算法的效率，第一个能体现算法价值的应该是算法的运行时间。然而，近年来，并行时间和硬件资源越来越是度量复杂性的重要手段。另一个重要的复杂性度量是组合复杂性。这里假定函数f是把有限的位字符串转化为有限的位字符串，对于所有长度为n的

4、输入，f的复杂度C（n）是所有组合中最小的复杂度。这个普通的测量和计算时间紧紧相关，也发展成为理论。Cobham提出的另外一个问题是在计算问题中，“步”由什么组成？对于度量一个算法的可计算时间，哪种计算机模型是正确的模型？多图灵机在这篇文献中经常被用到，但是他们被算法的执行效率所局限。比如，没有强制性的原因说存储介质必须是线性磁带。为什么不是平坦的矩阵或是树型？为什么不允许随机存储记忆？事实上，自1960年来，好多计算模型被提出。因为真实的计算机有随机存储记忆，很自然的被用到这个模型中。但是怎么用是一个很棘手的问题。如果机器在一个步内能存储整型，对他们的大小必须要限制。（如果2被平方100次，

5、结果将有2的100次方位，这些位能存储世界上所有已存在的存储介质。）我在文献19里面提出了RAMs，每次logx的代价都能得到，x可以存储也可以查找。一个流行的随机存储模型是Aho，Hopcroft和Ullman在文献3里面提出的，每次涉及到整型的操作都有一个单元的代价，但是不能达到不合理的大小（比如，这些数字的大小被固定多项式限制，这些多项式是输入的长度）。或许最满意的计算模型是舍恩洛克的存储修正机器，这个机器可以被看成是图灵机，它有自己的存储机构，或者被看做一个单元代价RAM，它在每一个步只能复制，增加或存储或查找。舍恩洛克的机器。对于我来说意味着大多数机器都能在每一步做有限制的工作。困难

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

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

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

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

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

11、结论要么乘法是比我们想象的更容易或Sch6nhage的机器作弊。（3）矩阵乘法。最明显的方法需要）算术操作，将两个nxn的矩阵，并尝试进行了证明，这在1950年和1960年最佳方法的。当Strassen的81(1969年)发布了他的方法只需要4.7Tm运算时间。相当多的工作一直致力于减少2.81指数，目前已知的最佳时间是O（112496）操作，是科珀和Winograd 24做出的。还有很多改进的空间，因为众所周知的下界是2n2 - 1（见13）（4）一般无向图的最大匹配。这也许是第一个问题明确的显示谁的成员在P中的算法比较复杂。Edmonds有影响力的论文27给出了结果并讨论了多项式的时间算法

12、（参见第二部分）。他指出简单的满足双边的情况并不适用一般的无向图。（5）确认素数。现在主要问题是确定这个问题是不是在P中。换句话说，是否有一个算法总能告诉我们输入的n位数字是不是一个素数，一个固定的有界n项多项式是否停止？Gary Miller 53 (1976年)表明，有这样的算法，其有效性取决于扩展的黎曼算法。Solovay 和Strassen 77发明了一种快速的蒙特卡罗素数识别算法，但是如果输入的数字是合成的那么有一定的小概率会误判。现在知道的最好的证明算法是Adleman, Pomerance, and Rumely 2提出的，时间复杂度为，稍微差于多项式算法。由于这方面的变化，H.

13、 Cohen 和 H.W. Lenstra Jr. 17经常可以处理多达一百个十进制数大约需时45秒钟。最近，在类P中三个重要的问题已经被证明了。第一个问题是线性规划问题由Khachian 43（参见55）于1979年证明。第二个问题是判定两个图的度数之多d是同构的，由Luks 50 于1980年证明（该算法是多项式的顶点固定d，但是指数在d）。第三个问题是考虑有理系数多项式因子，这被Lenstra,Lenstra, and Lovasz 48 在1982年，证明是含一个变量的多项式。Kaltofen's result 39, 40证明它可以被化为一般的变量固定的多项式。所有重要时间复

14、杂度或者空间复杂度的下界都是基于“对角线的理论”。图灵和与他同期的人使用对角线理论去证明些问题而不是通过算法可解。他们也用1960年之前确定的多层次可计算0-1函数。在1960年，Rabin 60证明了任何合理的复杂性措施，如计算时间或空间（内存），允许充分增加时间、空间等条件，也允许更多的0-1计算。大约在同一时间，Ritchie在他的论文65中在空间允许的数量内，定义一个特定的功能层次结构（他证明了0-1函数的平凡性）。之后，Rabin的结论被Hartmanis 和 Stearns 37更详细研究用于时序多带图灵机，被Stearns, Hartmanis, and Lewis 78用于空间

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

16、|+|y|)2 个步骤的计算，功能为基于输入y计算x从而给出输出的第一个数字的函数f(x,y)，显然不可能在 (|x|+|y|)2 的时间内完成计算。直到1972年，Albert Meyer和Larry Stockmeyer证明了对于带有平方的正则表达式需要指数级的空间和指数级的时间，即发现了对“自然的”问题计算的一般模型的重要下界（自然的指的是感兴趣的感觉，而不是指计算机）。在那之后不久，Meyer找到了在时间方面非常确定的下界，这个下界需要利用一种叫做WSIS确定的形式可解方法（弱一元二阶继承理论）来判断其正确性。他证明了任何一台运行时间在某个确定的指数时间（2n，22n，222n等）以内

17、的计算机不能正确地判断WSIS。Meyer的博士生，Stockmeyer继续计算，得出结论：如果一种逻辑电路（可以理解为计算机）想要正确判断任意一个长度为616个字符的WSIS公式的正确与否，那么它需要拥有超过10123个门电路。如果把10123这个数字想像成10123个质子，那么这些质子将填满目前人类已知的宇宙。这是一个对不可解性很有说服力的证明。从Meyer和Stockmeyer开始，涌现出大量关于可解的形式理论的复杂性的下界的讨论（相见参考文献29和80）。其中最值得关注的一种理论是由Fischer和Rabin提出的，需要双指数级的时间作为下界，用以解决Presburger算术问题（一种

18、自然数相加的理论）的理论。这与利用这种方法得到的已知最佳时间上界，三指数级时间，相差不多。最佳的空间上界是双指数级的。除了上面的一些成绩，证明更小规模复杂性问题的下界的记录，同样令人震惊。事实上，对于通常意义上的自然界存在的NP问题模型并没有非线性时间的降低，特别是对列出的300个问题。当然，我们可以从反面证明，现有的NP问题，当给定k时，它的解时间是nk。然而，对于降低解空间下界，我们甚至不知道如何证明现有的NP问题在O(logn)的空间当中可以通过非线性图灵机解决。这里讨论的不包括那些自然界中许多问题的已知最好解空间是n的线性。 4.2 结构化的下界尽管我们对于证明有价值的通用计算机模型上

19、的具体问题的下界，几乎没有取得成绩，但我们任然得到了关于“结构”模型的有价值结果。“结构”这个表述是由Borodin引入的是用来描述在计算机环境下，对我们碰到问题的相应的操作。一个简单的例子是n个数的排序问题。我们可以毫不费力的证明，如果假定计算机一次只能对一对数进行比较，那么解决这个问题至少需要nlogn次比较。这个下界的得到同图灵机或者布尔循环无关；但是，假定除法是不被允许的，这个问题的结论能够被扩展到任意的以随机代价进入的机器。第二个比较巧妙的结构下界是由Strassen（1973）提出的，他在研究多项式插值时发现：假定只有算术运算是允许的，那么计算通过给定n个点的n-1维多项式的系数，

20、需要至少（nlogn）次乘法。有趣的是，Strassen的初始证明是依据一个有很深的代数几何背景的Bezout的理论。直到最近，Baur和Strassen拓展了下界来说明，甚至计算通过n个点的多项式插值的中间系数，也需要至少（nlogn）次乘法。所有这些结构性结果的一些引人注目的地方是：结构下界接近已知的最好上界，并且已知的最好算法能够通过结构模型得到的下界来完善。（注：例如基数排序，有些说法说它线性时间可解，解决它需要nlogn步，但是如果假定输入的数字有足够的数位，那么两种说法却是截然不同的）。4.3 时空复杂度下界另一个陷入僵局的对时间和空间的下界的证明是：如何证明时间下界在一个小的范围

21、之内。Cobham在1966第一个证明了类似的结论，当时他得出的结论是，用非线性图灵机求解n位完全平方的时空复杂度，至少是n2。（求解有n个符号的回文也是同样的情况。）这里，输入是通过一个双向的只读磁带，而扫描图灵机可用的工作磁带的数目的平方作为空间。因此，假如空间被限定在log3n（足够使用）内，那么时间一定至少是（n2/log3n）步。Cobham的结论的缺陷是，尽管非线性图灵机是一个分别衡量计算时间复杂性和空间复杂性的好的模型，但当把时间和空间一起考虑的话，它的限制太多了些。例如，如果允许可以从两端同步的扫描输入磁带，那么回文问题显然可以在2n步和常数的空间内被解决。通过证明对从1到n2

22、范围内的n个数进行排序，至少需要(n2/log n)的时空复杂度，Borodin和我部分的修正了这一缺陷。这个证明适用于任何“一般时序机”，其中“一般时序机”包括多输入端甚至包括可以随机进入输入磁带的非线性图灵机。不幸的是我们的证明需要许多输出位，而且是否存在适用于相似的一系列问题的一个近似的下界，仍然是一个值得探讨的开放性课题。例如，是否所有的n输入数是不同的。（最近，我们对于排序问题的下界获得了微小的改进。）4.4 NP完全问题可以肯定NP完全理论是算法复杂性理论中最重大的进步。由于该理论已经很有名，并且已被写入教科书，所以在此我不再赘述。Garey和Johnson的著作是了解该理论的上佳

23、选择。NP问题包括所有利用非确定性图灵机在多项式时间内可被认知的集合。据我所知，1962年James Bennett在他的博士论文4中第一次定义了数学等价类的概念。Bennett使用了“基本的积极扩展关系”定义这种归类，并且在他的定义中使用了逻辑量词，而不是计算机器。我读过他的论文的这部分之后意识到，他的分类方法和现在为人们所熟悉的NP问题的定义在本质上是相同的。在我1971年发表的论文18中，我使用了符号 +（在Cobham的 分类之后），而Karp在他1972年发表的论文42中给出了现在对该分类的称呼：NP。同时，完全独立于形式方面的发展，早在1965年Edmonds就对于有着“完善描述”

24、的问题进行了非正式的讨论，即给出一个本质上等同于NP的概念。在1971年，我提出了NP完全的概念并且证明了3个可满足性条件和子图问题是NP完全的。一年后，Karp证明了21个问题是NP完全的，从而有力地证明了这一理论的重要性。在前苏联，独立于这一理论，Leonid Levin（现在任教于波士顿大学）在稍晚一些定义了一个相似的（更严格的）概念，并且证明了在他的理论中6个问题是完全的。“搜索问题”这一非正式的概念是苏联文学中的标准，并且Levin称他研究的问题为“通用搜索问题”。NP这类问题包括了大量商业和工业中的实际应用问题（参见31）。证明一个NP问题是NP完全的就是证明这个问题是非P的（不存

25、在一个在多项式时间内可解的算法）除非每个NP问题都是P的。因为后面的条件将会引起计算机科学的改革，所以NP完全的实际效果就是下界。这就是我在下界这部分介绍这一理论的原因。4.5 #P完全问题NP完全是和集合有关的概念。通常情况下，欲证明一个集合是NP完全的可以理解为证明这个集合是不可解的。但是存在着大量与非NP完全的证明可能相关的不可解的函数。于是Leslie Valiant 86,87定义了#P完全的概念来补救这个问题。一个函数被证明是#P完全的，则此函数是不可计算的，同样地，一个集合被证明是NP完全的，则此集合是不可识别的；也就是说，如果一个#P完全的函数可以在多项式时间内被计算，那么P=

26、NP。Valiant 给出了很多#P完全函数的例子，其中最有趣的应该是整数矩阵的永久式。永久式的定义和行列式的定义很相近，但是行列式可以利用高斯消去法轻松得到结果，而在过去的一百多年里很多对永久式计算的可行方法的探索都以失败告终。当Valiant证明永久式问题是#P完全问题之后，对于上述探寻失败的原因，他第一次给出了令人信服的解释。5概率算法在计算实践中使用随机数来模拟或近似随机过程是很自然的，而且已很好地确立起来。然而，随机输入在解决确定的组合问题中非常有用的思想，在渗透到计算机科学界中进展却要慢得多。这里我将把注意力限制于概率(硬币投掷)多项式时间算法，它们(在一个合理的意义下)求解不知道

27、有确定多项式时间算法的问题。第一个这样的算法似乎是由贝勒卡姆普于1970年给出的，该算法用于对p个元素的域GF(p)上的一个多项式f进行因式分解。贝勒卡姆普的算法在关于f的次数以及logp的多项式之下的时间运行，而且它至少以一半的概率找出f的正确因式分解，否则它以失败告终。由于这个算法可以被重复任意次而且出错事件是独立的，因而这个算法实际上总是在一个可行数量的时间中进行因式分解。一个更卓越的例子是由索罗伟和斯特拉森 (1974年投稿)给出的识别质数的算法。这个算法以输入m的长度的多项式时间内运行，输出或者是“质数”或者是“合数”。如果m事实上是质数，则输出肯定是“质数”，但如果m是合数，则以至

28、多一半的概率，答案也可能是“质数”。对于一个输入m，这个算法可以重复任意多次且有独立的结果。因此，如果答案正是“合数”，则用户知道m是“合数”；如果在比如说100运行次之后，答案一致地是“质数”，则用户有m是质数的很好证据，因为任何固定的合数m将以很小的概率(小于2-100)给出这样的结果。拉宾给出了其性质类似于上述之一的一个不同的概率算法，并且发现它在计算机试验时非常快。在几分钟之内，数2400-593就被标识为(大概是)质数。里维斯特(Rivest)、萨米尔(Shamir)和阿德尔曼(Adleman)在他们1978年关于公开钥加密系统里程碑式的论文中，提出了概率质数测试程序的一个有趣应用。

29、他们的系统要求很大的(100位数字)随机质数。他们提出，使用索罗伟斯特拉森的方法测试随机的100位数字，直到发现在上面概述的意义下它大概是质数为止。实际上，通过在第3节中提到的科恩和里斯特拉新的高次幂确定的质数测试程序，一旦发现一个随机的100位数字“大概是质数”，如果确实地知道是重要的话，就可以在大约45秒内进行测试以进行证实。在索罗伟和斯特拉森的意义下具有多项式和概率识别算法的集合类在参考文献中称为R(或有时称为RP)。因此一个集合在R中当且仅当有一个概率识别算法，它总是在多项式时间内停止，而且对于不在R中的输入决不出错，而对于R中的每个输入，它以至少一半的概率每次运行给出正确答案。因此，

30、合数集合在R中，而且一般地PRNP，还有其他在R中的有趣集合，但不知它们是否在P中，例如，施瓦茨(Schwartz)证明，其元素为许多变量的多项式的非奇矩阵集合在P中。该算法以随机小的整数值计算多项式并且计算结果的行列式(行列式显然不能能行地直接加以计算，因为所计算的多项式一般说来将有指数级多的项)。R=P是否成立是个有趣的开放问题。在哲学的基础上猜测答案肯定这一点是有趣的，即随机的硬币投掷当要寻求的答案是明确定义的是或不是时，不应有太多用处。有关的问题是，概率算法(证明一个问题在R中)对于所有实用目的而言是否和一个确定算法一样好。毕竟，概率算法可以使用在大多数计算机上都可利用的拟随机数生成来

31、运行，且2-100的出错概率是可以忽略的，蹊跷之处在于拟随机数生成程序并不产生真正随机的数，因此没有人知道对于一个给定的概率算法它们是否有效.事实上，经验表明它们似乎有效。但如果它们总是有效，则由此得出R=P，因为拟随机数是确定生成的，因此真正的随机性将毫无帮助。另一个可能性是使用一个物理过程例如热噪声来生成随机数。但是在科学原理上，真正会是怎样的随机的本质也是一个开放的问题。现在让我通过提及关于类R的阿德尔曼的一个有趣定理来结束这一节。容易看出，如果一个集合在P中，则对每个n，有一个其大小以n的一个固定多项式为界的布尔线路，它确定长度为n的一个任意的串是否在集合中。阿德尔曼证明的是，对类R来

32、说，同一结果成立。因此，例如，对每个n，有一个小的“计算机线路”，它正确地并迅速地测试n位数字的数是否质数。其蹊跷之处在于这些线路并非对n都一致，而且事实上对于100个数字的情况，想像出如何构造这个线路可能不是能行的。随着VLSI技术（在一块芯片上置入一个或多个处理器）的来临，很自然地就会想到未来的计算机由成千上万个处理器组合而成，并且它们并行地处理简单的问题。尽管这种类型的非常大的通用机没有被建造出来，但建造这样的通用机的项目正在进行。这激发了一个非常可喜的计算复杂性的分支机构的最新发展：大规模同步并行计算的原理，在连续的复杂性理论中处理机的个数用参数H(n)(H指的是硬件)表示；同样空间用

33、S(n)表示。通常H(n)是n的一个固定的多项式。正如有许多相互竞争的顺序模式，有相当数量的并行计算模型被提出。然而，这里有两个主要的竞争者。第一个竞争者是一类通过本身共同持有的随机存取内存将大量的处理器连接在一起，以此来分享内存。许多已经发表的并行算法就是这样的模型，因为真正被建造的并行机器可能就是这样的。然而，根据数学原理这些模型并不令人满意，因为他们很多的详细说明是随意的：如何解决共享内存中的读与写冲突？对于每个处理器的基本操作是什么？一个控制logH(n)时间的单元应该对共同的内存进行存取吗？因此，我比较喜欢由Borodin提出的比较清晰的模型。该模型的并行计算机是由统一的无环布尔电路

34、的逻辑电路组成。例如Bn有n个输入，那么H(n)就是Bn的门数。T(n)（并行计算时间）就是电路Bn的深度（例如，最长路径的长度就是从一个输入到一个输出）。这个模型部分证明了用布尔电路建造真正机器（包括共享内存机）的猜想。此外，最小布尔尺寸和深度需要计算一个函数是一个自然数学问题，并且很早就被认为有并行计算理论存在的影子。幸运的是，该理论的硬件H(n)的最小值和并行时间T(n)并没有广泛用于各种不同的并行计算机模型的竞争中。特别地，这里有一个一般事实对于所有的模型都成立。该事实是有Pratt和Stockmeyer于1974年提出的，并将其称之为“并行计算原理”，也就是一个问题可以在T(n)的多

35、项式时间内有一台并行机（硬件不限）器找到解，当且仅当它可以被一套时序机在T(n)的多项式空间内被解决。并行计算的一个基本问题是：哪些问题在使用多个处理器而不是单个处理器时可以解决的更快？Nicholas Pippenger通过定义可以在并行计算机上得以解决问题的阶（现在被称为NC，即Nick's class）划分出这些问题。并且这台并行计算机的硬件的数量在可接受的范围内。幸运的是NC阶任然与特别是并行计算机模型选择的相同，并且很容易看出NC是FP在多项式时间内计算序列的一个子集。我们上面的问题可以转变为：哪些问题既属于FP也属于NC？可以想象（尽管不可能）NC=FP，因为证明NC!=FP需要在计算复杂性理论上有所突破。由于我们不知道如何去证明函数f在FP中但却不在NC中，接着最好的事就是证明f在log空间中对于FP是完备的。这个问题的模拟证明是一个NP完全问题，并且具有劝阻为函数f寻找超快速并行算法的实际效果。这是因为如果f在log空间中对FP是完备的并且f也在NC中，那么FP=NC，这将是一个巨大的惊喜。相当一部分进展是在FP问题分类上，这些问题是否在NC中，或者在log空间上对于FP是否是完