计算复杂性类谱图

张杰　周云才

摘要：一个问题的计算复杂性（complexity）是指用计算机解决它的复杂程度，其度量标准：一是计算所需的步数或指令条数（即时间复杂度），二是计算所需的存储单元数（即空间复杂度）。复杂度相似的所有问题构成的集合就是一个复杂性类（complexity class）。该文探讨了在计算复杂性理论中常见的几种比较重要的计算复杂性类，研究了对计算复杂性归类的重要意义，以及复杂性类之间的一些关联。

关键词：计算复杂性；复杂性类；时间复杂性；空间复杂性

中图分类号：TP301.5 文献标识码：A 文章编号：1009-3044（2015）24-0040-03

Class Spectrogram of Computational Complexity

ZHANG Jie，ZHOU Yun-cai

（Computer Science College of Yangtze University，Jingzhou 434023，China）

Abstract：The computational complexity of a problem is the complexity of solving it with a computer.One of its measures is to calculate the required number of steps or instructions （that is， the time complexity），the other is to calculate the number of storage unit （i.e.， space complexity）.The set of all the problems with similar complexity is a complexity class.In this paper，we discussed several common and important computational complexity classes in computational complexity theory，and studied the significance of the classification of computational complexity and some relations between the complexity classes.

Keywords：computational complexity；complexity class；time complexity；space complexity

计算复杂性理论是一门研究求解计算问题所需要的时间、存贮量，或者其它资源的理论[1]。计算复杂性的概念，源于20世纪30年代数学逻辑的一些深刻命题。所谓计算复杂性，通俗说来，就是用计算机求解问题的难易程度。将计算问题按照在不同计算模型下所需资源的不同予以分类，从而得到一个对算法问题“难度”的类别，就是复杂性理论中复杂性类概念的来源[2]。

在计算复杂度理论中，通常情况下，不可能也不必要就一个个具体问题去研究它的计算复杂性，而是依据难度去研究各种计算问题之间的联系，按复杂性把问题分成不同的类，即计算复杂性类[3]。通常我们喜欢用图灵机（Turing）定义复杂性类，图灵机是种抽象计算机[4]。一个典型的复杂度类的定义有以下形式：可以被同一个抽象机器M使用O（f（n））的资源R所解决的问题的集合（n是输入数据的大小）。

1 复杂性分类的起源与意义

算法复杂性分析的一个早期的例子是1844年Gabriel Lamé所做的欧几里得算法的运行时间分析。在实际研究开始明确地致力于算法问题的复杂度之前，各种多样研究奠定了许多基础，其中最有影响力的是1936年图灵（Alan Turing）定义的图灵机，它是一个非常强大且灵活的简化计算机模型。

Fortnow & Homer （2003）表明计算复杂性的系统性研究开始于尤里斯·哈特马尼斯（Juris Hartmanis）和理查德·斯特恩（Richard Stearns）在1965年发表的开创性论文“关于算法的计算复杂性”，它奠定了时间和空间复杂度的定义以及证明了层次结构定理。同时在1965年，埃德蒙兹（Edmonds）定义了一个“好”的算法，运行时间由输入规模的多项式来界定。

据Fortnow & Homer （2003），早期的研究特定有限资源图灵机可以解决的问题的论文包括约翰·迈希尔（John Myhill）的线性有界自动机的定义（Myhill 1960），雷蒙德·史慕扬（Raymond Smullyan）的基本集的研究（1961），以及山田·尚勇（Hisao Yamada）的关于实时计算的论文（1962）。更早一些的时候，来自苏联的该领域的先驱鲍里斯（Boris Trakhtenbrot）（1956）研究了另一种特殊的复杂性度量。

1967年，曼纽尔·布卢姆（Manuel Blum）发表了一个基于他的公理的不言自明的复杂性理论并证明了一个重要的结论，即所谓的加速定理。该领域真正开始蓬勃发展是在1971年的时候，美国的研究员斯蒂芬·库克（Stephen Cook）和苏联的列昂尼德·莱文（Leonid Levin） 独立证明了存在切实相关的问题——NP完全性。1972年，理查德·卡普（Richard Karp）在他的里程碑式的论文“组合问题中的还原性”中给这个想法带来了飞跃 ，他在论文中展示了21个多元组合与图论问题，每一个都因其计算棘手而闻名，即是NP完全性。

自1971年Cook发表了他的著名定理以来，计算复杂性理论发展得相当快。已经形成了错综复杂的许多方向[4]。

研究问题的计算复杂性，可以明确该问题是否存在有效的求解算法[7]，如果它被证明是难解的，就不必将大量精力花费在寻找有效的求解算法上[1]，从而在实际工作中做出理性的抉择。某些计算问题在理论上是可解的，但是解决需要耗费大量的时间或空间，以至于无法在实践中应用[1]。

在计算科学发展的初期，研究空间复杂性有重要的意义。因为那时的电子技术不够发达，计算机的内存资源是宝贵的计算资源。计算过程中所需要的存储资源很容易超出计算机所拥有的资源，因而研究如何降低计算的空间复杂性成为重要的研究课题[5]。

首先将计算复杂性严格地建立在可计算性理论基础上的是Hartmanis和Stearns，他们受形式语言理论的启发，以多带Turing机为计算模型严格地给出了复杂性类P的定义，并且建立了确定型的时间类的分层定理[6]。

2 几种重要的复杂性类

当人们使用计算机解问题时，最关心的参量有两个，即计算时间和存储空间。这两个参量反映到计算复杂性理论中就成为了时间复杂性和空间复杂性的概念[4]。因为算法的精确的运行时间通常是一个复杂的表达式，所以一般只是估计它，只考虑算法运行时间的表达式的最高次项，而忽略该项的系数和其它低次项，这种记法称为大O记法[1]，通常采用大O记法来描述算法运行时所需资源。在图灵机的计算模型中分为确定性图灵机和非确定性图灵机，一些问题可用确定性图灵机来描述，而有些问题更适于采用非确定性图灵机来描述。根据解决问题所需时间和空间资源的层次不同，可将问题归为几种不同的复杂性类，详见表1。

表1中的PSPACE这个类的名字可以看作是由P（多项式）+Space（空间）定义的。具体地说，PSPACE类是在图灵机上用多项式数量的工作比特，在不限制时间的情况下可以求解的问题类[3]。其它类也可依此描述，这里不再赘述。

检查两个数是否互素的问题属于P类；有向图G包含节点s和t，PATH问题要确定是否存在从s到t的有向路径，PATH∈P。判定一个无向图中是否包含指定大小的团属于NP类。判定一个全量词化的布尔公式是真还是假问题属于PSPACE。语言A={0k1k|k≥0}是L的成员。

3 复杂性类之间的关系

事实上，P类是包含在PSPACE类中的，即P?PSPACE。因为在多项式时间内，停机的图灵机只能访问多项式数量的方格（空间或工作比特）[3]。另外，NP也是PSPACE类的子集，NP?PSPACE。P是在确定型图灵机上以多项式时间求解的问题的集合；NP是在非确定型图灵机上以多项式时间求解的问题的集合；NP问题若在确定型图灵机上求解，就需要用确定型图灵机去模拟非确定型图灵机的运行过程，这种模拟所需要的时间是指数级的，因此，普遍认为NP问题要难于P类问题，即P?NP[8]。同P≠NP问题类似，至今为止，仍然不知道P≠PSPACE是否成立，即仍然无法确定PSPACE类中是否包含不在P类中的问题[3]。

根据时间谱系定理DTIME（f（n））?DTIME（f（n）·log2（f（n）））和空间谱系定理DSPACE（f（n））?DSPACE（f（n）·log（f（n）））有：P ?EXPTIME 且NP ?NEXPTIME 且PSPACE ? EXPSPACE。另外，已经证明PSPACE和NL、P、NP、EXPTIME和EXPSPACE的关系为：NL?P?NP?PSPACE?EXPTIME?EXPSPACE，如图1。

4 结束语

计算复杂性理论为许多实际应用中的可解不可解问题提供了很好的理论基础，而计算复杂性类亦为判断求解某一具体问题的难易程度提供了直接的依据，所以研究算法复杂性和计算复杂性类具有十分重要的意义。除了以上提到的常见重要复杂性类之外，还有另外一些依照不同的分类标准而形成的其他复杂性类，例如：BPP、ZPP、RP、AC、NC、BQP、QMA、#P、IP、AM、ALL等，文章在这里就不再详细叙述。此外，在计算复杂性理论中还存在着至今依然悬而未决的问题，例如：还不知道coNP是否与NP不同（coNP包括NP中的语言的补语言），不确定P=NP是否成立，不知道coNL ?P和P ?PSPACE哪一个成立。有兴趣的读者可以自行研究探索上述问题。

参考文献

[1] Sipser M. Introduction to the theory of computation[M].Beijing： China Machine Press， 2000： 147-197.

[2] Wikipedia contributors. Computational complexity theory[G/OL].http：//en.wikipedia.org/w/index.php？title=Computational_ complexity_theory&oldid=649895389，2015-03-04/2015-03-31.

[3] 刘天华， 朱宏峰. 安全协议模型与设计[M]. 北京： 科学出版社， 2012： 21-25.

[4] 堵丁柱. 计算复杂性理论的近况与展望[J]. 贵州大学学报， 1988， 5（1）： 1-7.

[5] 李顺东， 王道顺. 现代密码学： 理论、 方法与研究前沿[M].北京： 科学出版社， 2009： 35-41.

[6] 堵丁柱.计算复杂性对运筹学发展的影响[J]. 运筹学杂志， 1989， 8（1）： 7-11.

[7] 高强， 徐心和. 时间复杂性和空间复杂性研究[J]. 智能系统学报， 2014， 9（5）： 529-535.

[8] Papadimiriou C. Computational Complexity[M]. Reading， Massachusetts： Addison-Wesley， 1994： 491-493.