复杂性理论（Complexity Theory）
目录 |
复杂性理论是理论计算机科学和数学的一个分支，它致力于将可计算问题根据它们本身的复杂性分类，以及将这些类别联系起来。一个可计算问题被认为是一个原则上可以用计算机解决的问题，亦即这个问题可以用一系列机械的数学步骤解决，例如算法。
在20世纪50年代，Trahtenbrot和Rabin的论文被认为是该领域最早的文献。而一般说来，被公认为奠定了计算复杂性领域基础的是Hartmanis和Stearns的1960年代的论文On the computational complexity of algorithms。在这篇论文中，作者引入了时间在20世纪50年代，Trahtenbrot和Rabin的论文被认为是该领域最早的文献。而一般说来，被公认为奠定了计算复杂性领域基础的是Hartmanis和Stearns的1960年代的论文On the computational complexity of algorithms。在这篇论文中，作者引入了时间复杂性类TIME(f(n))的概念，并利用对角线法证明了时间层级定理（Time Hierarchy Theorem）。
在此之后，许多研究者对复杂性理论作出了贡献。期间重要的发现包括：对随机算法的去随机化（derandomization）的研究，对近似算法的不可近似性（hardness of approximation）的研究，以及交互式证明系统理论和零知识证明（Zero-knowledge proof）等。特别的复杂性理论对近代密码学的影响非常显著，而最近，复杂性理论的研究者又进入了博弈论领域，并创立了“算法博弈论”（algorithmic game theory）这一分支。
所谓复杂性理论，从根本上说就是研究哪些工作可以很容易地用计算机完成，哪些工作不能的理论。在复杂性理论中，最关键的事情是搞清楚随着输入数据的增长，解决一个问题所需的步骤会以什么样的方式增加。
如果一个问题的求解需要相当多的资源（无论用什么算法），则被认为是难解的。计算复杂性理论通过引入数学计算模型来研究这些问题以及定量计算解决问题所需的资源（时间和空间），从而将资源的确定方法正式化了。其他复杂性测度同样被运用，比如通信量（应用于通信复杂性），电路中门的数量（应用于电路复杂性）以及中央处理器的数量（应用于并行计算）。计算复杂性理论的一个作用就是确定一个能或不能被计算机求解的问题的所具有的实际限制。
在理论计算机科学领域，与此相关的概念有算法分析和可计算性理论。两者之间一个关键的区别是前者致力于分析用一个确定的算法来求解一个问题所需的资源量，而后者则是在更广泛意义上研究用所有可能的算法来解决相同问题。更精确地说，它尝试将问题分成能或不能在现有的适当受限的资源条件下解决这两类。相应地，在现有资源条件下的限制正是区分计算复杂性理论和可计算性理论的一个重要指标：后者关心的是何种问题原则上可以用算法解决。
复杂性理论所研究的资源中最常见的是时间（要通过多少步演算才能解决问题）和空间（在解决问题时需要多少内存）。其他资源亦可考虑，例如在并行计算中，需要多少并行处理器才能解决问题。时间复杂度是指在计算机科学与工程领域完成一个算法所需要的时间，是衡量一个算法优劣的重要参数。时间复杂度越小，说明该算法效率越高，则该算法越有价值。空间复杂度是指计算机科学领域完成一个算法所需要占用的存储空间，一般是输入参数的函数。它是算法优劣的重要度量指标，一般来说，空间复杂度越小，算法越好。我们假设有一个图灵机来解决某一类语言的某一问题，设有X个字（word）属于这个问题，把X放入这个图灵机的输入端，这个图灵机为解决此问题所需要的工作带格子数总和称为空间。
复杂度理论和可计算性理论不同，可计算性理论的重心在于问题能否解决，不管需要多少资源。而复杂性理论作为计算理论的分支，某种程度上被认为和算法理论是一种“矛”与“盾”的关系，即算法理论专注于设计有效的算法，而复杂性理论专注于理解为什么对于某类问题，不存在有效的算法。