计算复杂性理论

计算复杂性理论（Computational complexity theory）是理论计算机科学和数学的一个分支，它致力于将可计算问题根据它们本身的复杂性分类，以及将这些类别联系起来。一个可计算问题被认为是一个原则上可以用计算机解决的问题，亦即这个问题可以用一系列机械的数学步骤解决，例如算法。

如果一个问题的求解需要相当多的资源（无论用什么算法），则被认为是难解的。计算复杂性理论通过引入数学计算模型来研究这些问题以及定量计算解决问题所需的资源（时间和空间），从而将资源的确定方法正式化了。其他复杂性测度同样被运用，比如通信量（应用于通信复杂性），电路中门的数量（应用于电路复杂性）以及中央处理器的数量（应用于并行计算）。计算复杂性理论的一个作用就是确定一个能或不能被计算机求解的问题的所具有的实际限制。

在理论计算机科学领域，与此相关的概念有算法分析和可计算性理论。两者之间一个关键的区别是前者致力于分析用一个确定的算法来求解一个问题所需的资源量，而后者则是在更广泛意义上研究用所有可能的算法来解决相同问题。更精确地说，它尝试将问题分成能或不能在现有的适当受限的资源条件下解决这两类。相应地，在现有资源条件下的限制正是区分计算复杂性理论和可计算性理论的一个重要指标：后者关心的是何种问题原则上可以用算法解决。

计算复杂性理论所研究的资源中最常见的是时间（要通过多少步演算才能解决问题）和空间（在解决问题时需要多少存储器）。其他资源亦可考虑，例如在并行计算中，需要多少并行处理器才能解决问题。

时间复杂度是指在计算机科学与工程领域完成一个算法所需要的时间，是衡量一个算法优劣的重要参数。时间复杂度越小，说明该算法效率越高，则该算法越有价值。

空间复杂度是指计算机科学领域完成一个算法所需要占用的存储空间，一般是输入参数的函数。它是算法优劣的重要度量指针，一般来说，空间复杂度越小，算法越好。我们假设有一个图灵机来解决某一类语言的某一问题，设有${\displaystyle X}$个字（word）属于这个问题，把${\displaystyle X}$放入这个图灵机的输入端，这个图灵机为解决此问题所需要的工作带格子数总和称为空间。

复杂度理论和可计算性理论不同，可计算性理论的重心在于问题能否解决，不管需要多少资源。而复杂性理论作为计算理论的分支，某种程度上被认为和算法理论是一种“矛”与“盾”的关系，即算法理论专注于设计有效的算法，而复杂性理论专注于理解为什么对于某类问题，不存在有效的算法。

在20世纪50年代，Trahtenbrot和Rabin的论文被认为是该领域最早的文献。而一般说来，被公认为奠定了计算复杂性领域基础的是Hartmanis和Stearns的1960年代的论文On the computational complexity of algorithms。在这篇论文中，作者引入了时间复杂性类${\displaystyle \text{TIME}(f(n))}$的概念，并利用对角线法证明了时间层级定理（Time Hierarchy Theorem）。

在此之后，许多研究者对复杂性理论作出了贡献。期间重要的发现包括：对随机算法的去随机化（derandomization）的研究，对近似算法的不可近似性（hardness of approximation）的研究，以及交互式证明系统理论和零知识证明（Zero-knowledge proof）等。特别的复杂性理论对近代密码学的影响非常显著，而最近，复杂性理论的研究者又进入了博弈论领域，并创立了“算法博弈论”（algorithmic game theory）这一分支。

计算复杂性理论的研究对象是算法在执行时所需的计算资源，而为了讨论这一点，我们必须假设算法是在某个计算模型上运行的。常讨论的计算模型包括图灵机（Turing machine）和电路（circuit），它们分别是一致性（uniform）和非一致性（non-uniform）计算模型的代表。而计算资源与计算模型是相关的，如对图灵机我们一般讨论的是时间、空间和随机源，而对电路我们一般讨论电路的大小。

由邱奇-图灵论题（Church-Turing thesis），所有的一致的计算模型与图灵机在多项式时间意义下是等价的。而由于我们一般将多项式时间作为有效算法的标志，该论题使得我们可以仅仅关注图灵机而忽略其它的计算模型。

我们考虑对一个算法问题，什么样的回答是我们所需要的。比如搜索问题：给定数组${\displaystyle A}$，和一个数${\displaystyle s}$，我们要问${\displaystyle s}$在不在${\displaystyle A}$中（判定性问题，decision problem）。而进一步的，${\displaystyle s}$如果在${\displaystyle A}$中的话，${\displaystyle s}$的位置是什么（搜索型问题，search problem）。再比如完美匹配问题（perfect matching）：给定一个二分图${\displaystyle G=(V,E)}$，我们问是不是存在边集${\displaystyle E}$，使得二分图中每个结点恰好属于该边集的一条边（判定型问题）。而进一步的，${\displaystyle E}$存在的话，${\displaystyle E}$具体是什么（搜索型问题）。

自然的，我们会发现对于一般的算法问题${\displaystyle A}$，我们都可以这样来问：首先，解是不是存在的？其次，如果解存在，这个解具体是什么？这就是${\displaystyle A}$的判定型问题和${\displaystyle A}$的搜索型问题（又称函数型问题）区分来源的直观解释。对判定型问题的回答只需是“是”或“否”，而对搜索型问题，需要返回解的具体形式或者“解不存在”。所以一个对${\displaystyle A}$的搜索型问题的算法自然的也是对${\displaystyle A}$的判定型问题的算法。反之，给定了一个${\displaystyle A}$的判定型问题的算法，是否存在${\displaystyle A}$的搜索型问题的算法，在可计算性理论和计算复杂性理论中有着不同的回答，这也是理解计算复杂性理论与它的前身可计算性理论不同的一个基本的观察。

在可计算性理论中，可以说明，判定型问题和搜索型问题在可计算性的意义下是等价的（见Decision problem）。而在计算复杂性中，Khuller和Vazirani在1990年代证明了在P≠NP的假设下，平面图4-着色问题的判定型问题是在P中的，而寻找其字典序第一的着色是NP难的。

所以在可计算性理论中，只关注判定型问题是合理的。在计算复杂性理论中，虽然一些基本的复杂性类（如P，NP和PSPACE），以及一些基本的问题（P和NP关系问题等）是用判定型问题来定义的，但函数型问题复杂性类也被定义（如FP，FNP等），而且一些特别的函数型问题复杂性类，如TFNP，也正在逐渐受到关注。

上面提到计算复杂性理论的研究对象是执行一项计算任务所用的资源，特别的，时间和空间是最重要的两项资源。

我们用时间作例子来讨论算法分析的一些基础知识。如果将输入的长度（设为${\displaystyle n}$）作为变量，而我们关注的是算法运行时间与${\displaystyle n}$的函数关系${\displaystyle T(n)}$。因为一个算法在不同的计算模型上实现时${\displaystyle T(n)}$可能会有常数因子的差别（参见可计算性理论），我们使用大O表达式来表示${\displaystyle T(n)}$，这使得我们可以忽略在不同计算模型上实现的常数因子。

以搜索这个计算任务为例。在搜索问题中，给定了一个具体的数${\displaystyle s}$，和长度为${\displaystyle n}$的数组${\displaystyle A}$（数组中数的位置用1到${\displaystyle n}$作标记），任务是当${\displaystyle s}$在${\displaystyle A}$中时，找到${\displaystyle s}$的位置，而${\displaystyle s}$不在${\displaystyle A}$中时，需要报告"未找到"。这时输入的长度即为${\displaystyle n+1}$。下面的过程即是一个最简单的算法：我们依次扫过${\displaystyle A}$中的每个数，并与${\displaystyle s}$进行比较，如果相等即返回当前的位置，如果扫遍所有的数而算法仍未停止，则返回"未找到"。

如果我们假设${\displaystyle s}$在${\displaystyle A}$中每个位置的几率都相同，那么算法在找到${\displaystyle s}$的条件下需要${\displaystyle \frac{1}{n}(1+2+\cdots <!--\; \cdots \; -->+n)=\frac{n(n+1)}{2n}=\frac{n+1}{2}}$的时间。如果${\displaystyle s}$不在${\displaystyle A}$中，那么需要${\displaystyle (n+1)}$的时间。由大O表达式的知识我们知道算法所需的时间即为${\displaystyle O(n)}$。

而如果我们进一步假设${\displaystyle A}$是已排序的，那么我们有二分查找算法，使得算法的运行时间是${\displaystyle O(\log <!--\; \; -->n)}$。可以看出执行一项计算任务，不同的算法在运行时间上是有很大差异的。

将计算问题按照在不同计算模型下所需资源的不同予以分类，从而得到一个对算法问题“难度”的类别，就是复杂性理论中复杂性类概念的来源。例如一个问题如果在确定性图灵机上所需时间不会超过一个确定的多项式（以输入的长度为多项式的不定元），那么我们称这类问题的集合为P（polynomial time Turing machine）。而将前述定义中的“确定性图灵机”改为“不确定性图灵机”，那么所得到的问题集合为NP（non-deteministic polynomial time Turing machine）。类似的，设${\displaystyle n}$为输入的长度，那我们可以定义“在确定性图灵机上所需空间不超${\displaystyle O(\log <!--\; \; -->n)}$的算法问题的集合”（即为${\displaystyle L}$），“存在深度为${\displaystyle O(\log <!--\; \; -->n)}$，输入的度（fan-in）为${\displaystyle O(1)}$的电路族（circuit family）的算法问题的集合”（即为NC1）等等复杂性类。

定义复杂性类问题的目的是为了将所有的算法问题进行分类，以确定当前算法的难度，和可能的前进方向。这是复杂性理论的一个主线之一：对算法问题进行抽象和分类。例如透过大O表达式，我们可以对忽略因计算模型不同而引入的常数因子。而第二个重要的理论假设，就是将多项式时间作为有效算法的标志（与之对应的是指数时间）。这样，复杂性类使得我们可以忽略多项式阶的不同而专注于多项式时间和指数时间的差别。（对多项式时间作为有效算法的标志这一点是有一定争议的，比如，如果算法的运行时间${\displaystyle n^{10}}$，那它也可以看作是缓慢的，见理论与实践。）在本文的其余章节，“有效算法”等价于“多项式算法”

归约（reduction）是将不同算法问题创建联系的主要的技术手段，并且在某种程度上，定义了算法问题的相对难度。简单来说，假设我们有算法任务${\displaystyle A}$和${\displaystyle B}$，如果我们想说“${\displaystyle A}$比${\displaystyle B}$简单”（记为${\displaystyle A\le <!--\; \le \; -->B}$），它应该是什么意思呢？从归约的观点来看，就是说如果我们有了${\displaystyle B}$的有效算法${\displaystyle M}$，那么我们有一个有效算法${\displaystyle N}$，它可以引用${\displaystyle M}$，最终它要解决${\displaystyle A}$问题。

我们以点集覆盖问题（vertex cover）和独立集问题（independent set）为例来进行说明。这两个问题都是图论中的问题。假设给定了无向图${\displaystyle G=(V,E)}$，和一个自然数${\displaystyle k}$，点集覆盖问题是要找到${\displaystyle V}$的子集${\displaystyle S}$，使得对${\displaystyle \mathrm{\forall <!--\; \forall \; -->}e\in <!--\; \in \; -->E}$，有${\displaystyle s\in <!--\; \in \; -->S}$，使得${\displaystyle s\in <!--\; \in \; -->e}$，且${\displaystyle |S|\le <!--\; \le \; -->k}$；而独立集问题也是要找${\displaystyle V}$的子集${\displaystyle S}$，要求是${\displaystyle \mathrm{\forall <!--\; \forall \; -->}{s}_1,s_2\in <!--\; \in \; -->S,(s_1,s_2)\notin <!--\; \notin \; -->E}$，且${\displaystyle |S|\le <!--\; \le \; -->k}$。

一个简单的观察即是：对${\displaystyle G=(V,E)}$，一个${\displaystyle S\subset <!--\; \subset \; -->V}$是覆盖点集，当且仅当${\displaystyle S}$在${\displaystyle G}$的补图中是独立点集（而且保持集合大小）。利用这个观察，假设我们有了解决覆盖点集问题的算法${\displaystyle M}$，我们设计解决独立点集的算法N如下：

可以看出若产生补图这一步是有效的，那么如果${\displaystyle M}$有效，${\displaystyle N}$也是有效的。一般的，如果我们有一个${\displaystyle B}$有效的算法${\displaystyle M}$，和利用${\displaystyle B}$作为“神谕”（oracle）的解决${\displaystyle A}$问题的算法${\displaystyle N}$，那么如果${\displaystyle N}$是有效的，则我们有有效的解决${\displaystyle A}$问题的算法${\displaystyle N^{\prime }}$——只需将