计算复杂性理论（综述）

贡献者： 待更新

　　 本文根据 CC-BY-SA 协议转载翻译自维基百科相关文章。

　　 在理论计算机科学和数学中，计算复杂性理论专注于根据资源使用情况对计算问题进行分类，并探索这些分类之间的关系。计算问题是由计算机解决的任务。一个计算问题可以通过机械地应用数学步骤（如算法）来解决。

　　 如果一个问题的解决需要大量资源，无论使用何种算法，都被视为固有的困难问题。该理论通过引入计算模型来正式化这种直觉，以研究这些问题并量化它们的计算复杂性，即解决问题所需的资源量，如时间和存储空间。还使用其他复杂性度量，如通信量（用于通信复杂性）、电路中的门数（用于电路复杂性）以及处理器数量（用于并行计算）。计算复杂性理论的一个重要作用是确定计算机能够做什么以及不能做什么的实际限制。P 与 NP 问题，作为七大千年奖问题之一，是计算复杂性领域的一部分。

　　 在理论计算机科学中，与计算复杂性紧密相关的领域有算法分析和可计算性理论。算法分析与计算复杂性理论之间的一个关键区别是，前者致力于分析特定算法解决问题所需的资源量，而后者则提出一个更为一般的问题，即所有可能用于解决同一问题的算法。更精确地说，计算复杂性理论试图对能够或不能在适当限制的资源下解决的问题进行分类。反过来，施加对可用资源的限制是计算复杂性与可计算性理论的区别所在：后者理论探讨的是哪些类型的问题原则上可以通过算法解决。

1. 计算问题

问题实例

　　 一个计算问题可以视为一个无限的实例集合，每个实例都有一组（可能为空）的解。计算问题的输入字符串称为问题实例，不应与问题本身混淆。在计算复杂性理论中，问题指的是待解决的抽象问题。与此相对，问题的一个实例是一个相对具体的表述，可以作为决策问题的输入。例如，考虑素数测试问题。实例是一个数字（例如，15），如果该数字是素数，解答是 “是”，否则是 “否”（在这种情况下，15 不是素数，答案是 “否”）。换句话说，实例是问题的特定输入，解答是与该输入对应的输出。

　　 为了进一步突出问题和实例之间的区别，考虑旅行商问题的决策版本实例：是否存在一条最多 2000 公里的路线，经过德国的 15 个最大城市？对于这个特定问题实例的定量答案，对解决问题的其他实例帮助不大，例如询问一条在米兰所有景点之间，且总长度不超过 10 公里的环路。因此，复杂性理论关注的是计算问题，而不是特定的问题实例。

表示问题实例

　　 在考虑计算问题时，问题实例通常是一个由字母表组成的字符串。通常，字母表被视为二进制字母表（即{0, 1}集合），因此这些字符串是位字符串。如同实际计算机一样，必须对除位字符串外的数学对象进行适当的编码。例如，整数可以用二进制表示，图形可以通过其邻接矩阵直接编码，或者通过将其邻接表编码为二进制来表示。

　　 尽管一些复杂性理论定理的证明通常假设某种具体的输入编码选择，但讨论通常保持足够抽象，以独立于编码选择。这可以通过确保不同的表示方法可以高效地相互转换来实现。

决策问题作为形式语言

　　 决策问题是计算复杂性理论中研究的核心对象之一。决策问题是一种计算问题，其答案是 “是” 或 “否”（也可以是 1 或 0）。决策问题可以被视为一种形式语言，其中语言的成员是那些输出为 “是” 的实例，而非成员则是那些输出为 “否” 的实例。目标是借助算法来判断给定的输入字符串是否是所考虑的形式语言的成员。如果决定该问题的算法返回 “是” 作为答案，则称该算法接受该输入字符串，否则称其拒绝该输入。

　　 一个决策问题的例子是以下问题：输入是一个任意图。问题的内容是判断给定的图是否是连通的。与此决策问题相关的形式语言是所有连通图的集合——为了精确定义这个语言，需要决定如何将图编码为二进制字符串。

函数问题

　　 函数问题是一种计算问题，其中每个输入期望一个单一的输出（来自一个总函数），但输出比决策问题更复杂——即输出不仅仅是 “是” 或 “否”。著名的例子包括旅行推销员问题和整数分解问题。

　　 人们可能会认为，函数问题的概念比决策问题的概念要丰富得多。然而，事实并非如此，因为函数问题可以转化为决策问题。例如，两个整数的乘法可以表示为一组三元组 $(a,b,c)$，使得 $a\times b=c$ 成立。判断给定三元组是否属于该集合，相当于解决两个数相乘的问题。

衡量实例的大小

　　 为了衡量解决一个计算问题的难度，可能需要了解解决该问题的最佳算法所需的时间。然而，运行时间通常依赖于实例的大小。特别是，较大的实例需要更多时间来解决。因此，解决一个问题所需的时间（或所需的空间，或任何复杂度度量）是作为实例大小的函数来计算的。输入大小通常以比特为单位衡量。复杂度理论研究算法在输入大小增加时的扩展性。例如，在判断一个图是否连通的问题中，对于一个拥有 $2n$ 个顶点的图，相比于一个拥有 $n$ 个顶点的图，解决该问题需要更多的时间吗？

　　 如果输入大小是 $n$，则所需的时间可以表示为 $n$ 的函数。由于对于相同大小的不同输入，所需的时间可能不同，因此定义最坏情况下的时间复杂度 $T(n)$ 为所有大小为 $n$ 的输入所需时间的最大值。如果 $T(n)$ 是 $n$ 的多项式，则称该算法为多项式时间算法。科布汉的论题（Cobham's thesis）认为，如果一个问题能够通过多项式时间算法解决，那么它可以用合理的资源量来解决。

2. 机器模型与复杂度度量

图灵机

　　 图灵机是一种通用计算机的数学模型。它是一个理论设备，能够操作带有符号的磁带。图灵机并非作为一种实际的计算技术出现，而是作为计算机的通用模型——从高级超级计算机到拿着铅笔和纸的数学家都可以视为图灵机的实现。人们相信，如果一个问题可以通过算法解决，那么就存在一个图灵机能够解决该问题。这正是教会-图灵论题的表述。此外，已知任何我们今天所知的其他计算模型（如 RAM 机、康威的生命游戏、元胞自动机、λ演算或任何编程语言）也能在图灵机上进行计算。由于图灵机容易进行数学分析，并且被认为与其他计算模型具有同等的计算能力，因此在复杂度理论中，图灵机是最常用的模型。

　　 有许多类型的图灵机被用来定义复杂度类，例如确定性图灵机、概率图灵机、非确定性图灵机、量子图灵机、对称图灵机和交替图灵机。它们在原则上都是同等强大的，但当资源（如时间或空间）受到限制时，有些可能比其他的更强大。

　　 确定性图灵机是最基本的图灵机，它使用一组固定的规则来确定未来的操作。概率图灵机是一个附加了随机比特的确定性图灵机。做出概率性决策的能力通常有助于算法更高效地解决问题。使用随机比特的算法被称为随机算法。非确定性图灵机是一个带有非确定性特性的确定性图灵机，它允许图灵机在给定状态下有多个可能的未来动作。非确定性的一种看法是，图灵机在每一步都分裂成许多可能的计算路径，如果它在任何这些路径中成功解决问题，那么就认为它已经解决了问题。显然，这个模型并不是为了作为一个物理上可实现的模型，它只是一个在理论上非常有趣的抽象机器，并且它催生了特别有趣的复杂度类。例如，非确定性算法就是这一模型的一个实例。

其他机器模型

　　 在文献中，提出了许多与标准的多带图灵机不同的机器模型，例如随机访问机器。令人惊讶的是，这些模型中的每一个都可以转换为另一个，而不会提供任何额外的计算能力。这些替代模型的时间和内存消耗可能会有所不同。[2] 这些模型的共同点是，它们的操作是确定性的。

　　 然而，一些计算问题在更不寻常的资源模型下更容易分析。例如，非确定性图灵机是一种计算模型，允许它在同一时刻分支出多个不同的可能性。非确定性图灵机与我们物理上如何计算算法几乎没有关系，但它的分支正好捕捉了许多我们想要分析的数学模型，因此非确定性时间在分析计算问题时是一个非常重要的资源。

复杂度度量

　　 为了准确地定义在给定时间和空间内解决一个问题的含义，通常使用像确定性图灵机这样的计算模型。对于确定性图灵机 $M$ 和输入 $x$，所需的时间是机器在停止并输出答案（“是” 或 “否”）之前所做的状态转换或步骤的总数。如果一个图灵机 $M$ 在每个长度为 $n$ 的输入上所需的时间最多为 $f(n)$，则称其在时间 $f(n)$ 内运行。若存在一个在时间 $f(n)$ 内运行的图灵机 $M$ 可以解决决策问题 $A$，则可以说该问题在时间 $f(n)$ 内可解。由于复杂度理论关注的是根据问题的难度对问题进行分类，因此可以根据某些标准定义问题的集合。例如，在确定性图灵机上可以在时间 $f(n)$ 内解决的所有问题集合，记作 $\text{DTIME}(f(n))$。

　　 对于空间需求，可以做类似的定义。尽管时间和空间是最常见的复杂度资源，但任何复杂度度量都可以视为一种计算资源。复杂度度量通常通过布鲁姆复杂度公理进行定义。复杂度理论中使用的其他复杂度度量包括通信复杂度、电路复杂度和决策树复杂度。

　　 算法的复杂度通常使用大 O 符号表示。

最佳、最差和平均情况复杂度

　　 最佳、最差和平均情况复杂度是衡量相同大小的不同输入的时间复杂度（或任何其他复杂度度量）三种不同方式。由于大小为 $n$ 的某些输入可能比其他输入更容易解决，因此我们定义以下几种复杂度：

1. 最佳情况复杂度：这是解决大小为 $n$ 的问题时，针对最佳输入的复杂度。
2. 平均情况复杂度：这是解决问题的平均复杂度。该复杂度仅在输入上有概率分布时定义。例如，如果假设所有相同大小的输入出现的概率相同，则可以根据大小为 $n$ 的所有输入的均匀分布来定义平均情况复杂度。
3. 摊销分析：摊销分析考虑了算法整个操作序列中的昂贵操作和较便宜操作的综合。
4. 最差情况复杂度：这是解决大小为 $n$ 的问题时，针对最差输入的复杂度。

　　 从便宜到昂贵的顺序为：最佳情况、平均情况（离散均匀分布）、摊销、最差情况。

　　 例如，确定性排序算法快速排序解决的是排序整数列表的问题。最差情况是当每次选择的基准值都是列表中的最大或最小值（因此列表从未被分割）。在这种情况下，算法的时间复杂度是 $O(n^2)$。如果假设输入列表的所有可能排列的出现概率相同，则排序的平均时间复杂度为 $O(n\log n)$。最佳情况发生在每次基准分割列表为两半时，这时也需要 $O(n\log n)$ 时间。

问题复杂度的上下界

　　 为了对计算时间（或类似资源，如空间消耗）进行分类，展示求解给定问题的最有效算法所需的最大时间的上界和下界是有帮助的。算法的复杂度通常被认为是其最差情况复杂度，除非另有说明。分析特定算法属于算法分析领域。为了展示一个问题的时间复杂度的上界 $T(n)$，只需要展示某个算法的运行时间最多为 $T(n)$。然而，证明下界要困难得多，因为下界是对所有能够解决给定问题的可能算法作出的声明。这里的 “所有可能的算法” 不仅包括今天已知的算法，还包括未来可能发现的任何算法。要展示问题的下界为 $T(n)$，需要证明没有任何算法能有比 $T(n)$ 更低的时间复杂度。

　　 上下界通常使用大 O 符号表示，这样可以隐藏常数因子和较小的项。这样，复杂度的上下界与所使用的具体计算模型的细节无关。例如，如果 $T(n)=7n^2+15n+40$，在大 O 符号中会写成 $T(n)=O(n^2)$。

3. 复杂度类

定义复杂度类

　　 复杂度类是具有相关复杂度的各种问题的集合。更简单的复杂度类通常由以下因素定义：

• 计算问题的类型：最常用的问题是决策问题。然而，复杂度类也可以基于函数问题、计数问题、优化问题、承诺问题等来定义。
• 计算模型：最常见的计算模型是确定性图灵机，但许多复杂度类是基于非确定性图灵机、布尔电路、量子图灵机、单调电路等定义的。
• 被限制的资源（或资源）和限制条件：这两个属性通常一起陈述，如 “多项式时间”、“对数空间”、“常深度” 等。

　　 有些复杂度类的定义非常复杂，无法适应这一框架。因此，一个典型的复杂度类通常有类似以下的定义：

　　 决策问题的集合：这些问题可以由确定性图灵机在时间 $f(n)$ 内解决。（这个复杂度类被称为 DTIME($f(n)$)）

　　 然而，将计算时间通过某个具体的函数 $f(n)$ 上限化，往往会导致依赖于所选择的机器模型的复杂度类。例如，语言集合 $\{xx\mid x\text{ 是任何二进制字符串}\}$ 可以在多带图灵机上在线性时间内解决，但在单带图灵机模型中则必须使用二次时间。如果我们允许运行时间的多项式变化，Cobham-Edmonds 定理指出，“任何两种合理且通用的计算模型中的时间复杂度是多项式相关的”（Goldreich 2008，第 1.2 章）。这为复杂度类 P 奠定了基础，P 是指那些可以在多项式时间内由确定性图灵机解决的决策问题的集合。相应的函数问题集合是 FP。

重要的复杂度类

　　 许多重要的复杂度类可以通过限定算法使用的时间或空间来定义。以下是以这种方式定义的一些重要决策问题的复杂度类：

　　 对数空间类不考虑表示问题所需的空间。

　　 事实证明，根据萨维奇定理（Savitch's theorem），PSPACE = NPSPACE 和 EXPSPACE = NEXPSPACE。

　　 其他重要的复杂度类包括 BPP、ZPP 和 RP，它们是使用概率图灵机定义的；AC 和 NC 是使用布尔电路定义的；BQP 和 QMA 是使用量子图灵机定义的。#P 是一个重要的计数问题复杂度类（而非决策问题）。像 IP 和 AM 这样的类是使用交互证明系统定义的。ALL 是所有决策问题的类。

层次定理

　　 主条目：时间层次定理和空间层次定理 对于以这种方式定义的复杂度类，证明放宽（例如）计算时间的要求是否确实定义了一个更大的问题集合是值得的。特别地，虽然 DTIME($n$) 包含在 DTIME($n^2$) 中，但了解这个包含关系是否严格是很有意义的。对于时间和空间要求，类似问题的答案分别由时间和空间层次定理给出。它们被称为层次定理，因为它们通过约束相应的资源在定义的类上引入了一个正确的层次结构。因此，有些复杂度类是严格包含于其他类的。在得出这些严格的集合包含关系后，我们可以进一步定量地陈述，为了增加可解问题的数量，需要多少额外的时间或空间。

　　 更精确地说，时间层次定理声明： $$\mathsf{DTIME}(o(f(n)))⊊\mathsf{DTIME}(f(n)\cdot \log (f(n)))$$ 空间层次定理声明： $$\mathsf{DSPACE}(o(f(n)))⊊\mathsf{DSPACE}(f(n))$$ 时间和空间层次定理为大多数复杂度类的分离结果提供了基础。例如，时间层次定理告诉我们 P 严格包含在 EXPTIME 中，而空间层次定理告诉我们 L 严格包含在 PSPACE 中。

归约

　　 许多复杂度类是通过归约的概念定义的。归约是将一个问题转化为另一个问题的过程。它捕捉了一个问题至多和另一个问题一样困难的非正式概念。例如，如果问题 $X$ 可以通过使用 $Y$ 的算法来解决，那么 $X$ 就不比 $Y$ 更难，我们说 $X$ 归约于 $Y$。根据归约的方法，有许多不同类型的归约，例如库克归约、卡普归约和列文归约，以及归约复杂度的界限，例如多项式时间归约或对数空间归约。

　　 最常用的归约是多项式时间归约。这意味着归约过程需要多项式时间。例如，平方一个整数的问题可以归约为两个整数相乘的问题。这意味着可以使用一个用于乘法的算法来计算一个整数的平方。实际上，可以通过将相同的输入传递给乘法算法的两个输入来实现这一点。因此，我们看到平方并不比乘法更困难，因为平方可以归约为乘法。

　　 这促使了 “某个问题对于一个复杂度类是困难的” 这一概念。一个问题 $X$ 如果每个 $C$ 类中的问题都可以归约到 $X$，那么我们就说 $X$ 对于类 $C$ 是困难的。因此，类 $C$ 中没有比 $X$ 更困难的问题，因为 $X$ 的算法可以帮助我们解决 $C$ 类中的任何问题。困难问题的概念取决于使用的归约类型。对于大于 P 的复杂度类，通常使用多项式时间归约。特别地，NP 类中的困难问题集合就是 NP-困难问题的集合。

　　 如果一个问题 $X$ 属于类 $C$ 并且对 $C$ 来说是困难的，那么 $X$ 被称为 $C$ 的完全问题。这意味着 $X$ 是 $C$ 中最困难的问题。（因为许多问题可能同样困难，所以可以说 $X$ 是 $C$ 中最困难的问题之一。）因此，NP 完全问题类包含了 NP 中最难的问题，从某种意义上讲，这些问题最有可能不属于 P 类。由于问题 P = NP 尚未解决，如果能将一个已知的 NP 完全问题 ${\mathrm{\Pi }}_2$ 归约到另一个问题 ${\mathrm{\Pi }}_1$，则说明 ${\mathrm{\Pi }}_1$ 没有已知的多项式时间解决方案。这是因为对 ${\mathrm{\Pi }}_1$ 的多项式时间解决方案将为 ${\mathrm{\Pi }}_2$ 提供多项式时间解决方案。同样，由于所有 NP 问题都可以归约为该集合，如果能找到一个能够在多项式时间内解决的 NP 完全问题，则意味着 P = NP。

4. 重要的未解问题

P 与 NP 问题

　　 复杂度类 P 通常被视为一种数学抽象，模拟那些有高效算法的计算任务。这个假设被称为 Cobham–Edmonds 命题。另一方面，复杂度类 NP 包含了许多人们希望高效解决的，但目前没有已知高效算法的问题，比如布尔可满足性问题、哈密顿路径问题和顶点覆盖问题。由于确定性图灵机是非确定性图灵机的一种特例，因此可以很容易观察到，P 中的每个问题也属于 NP 类。

　　 P 是否等于 NP 的问题是理论计算机科学中最重要的未解问题之一，因为这个问题的解决将具有广泛的影响。如果答案是肯定的，那么可以证明许多重要问题有更高效的解决方案。这些问题包括运筹学中的各种整数规划问题、物流中的许多问题、生物学中的蛋白质结构预测，以及证明纯数学定理的能力。P 与 NP 问题是克莱数学研究所提出的千年大奖难题之一，解决该问题将获得 100 万美元的奖金。

NP 中未知是否属于 P 或 NP 完全问题

　　 Ladner 已经证明，如果 $P\ne NP$，则在 $NP$ 中存在既不在 $P$ 中也不在 $NP$-完全问题中的问题。这类问题称为 NP-中间问题。图同构问题、离散对数问题和整数分解问题就是被认为是 NP-中间问题的例子。它们是少数几个尚未被证明属于 $P$ 或 $NP$-完全问题的 NP 问题。

　　 图同构问题是计算问题，旨在判断两个有限图是否同构。复杂度理论中的一个重要未解问题是图同构问题是否属于 $P$、$NP$-完全，或者是 NP-中间问题。这个问题的答案尚不明确，但普遍认为它至少不是 NP-完全问题。如果图同构问题是 NP-完全的，那么多项式时间层次结构将会坍缩到第二级。由于广泛认为多项式层次结构不会坍缩到任何有限级别，因此图同构问题很可能不是 NP-完全问题。该问题的最佳算法，由 László Babai 和 Eugene Luks 提出，针对具有 $n$ 个顶点的图，其运行时间为 $O(2^{\sqrt{n\log n}})$，尽管 Babai 最近的工作为此问题提供了一些可能的新视角。

　　 整数分解问题是计算问题，旨在确定给定整数的质因数分解。作为一个决策问题，它是判断输入是否有小于 $k$ 的质因数的问题。尚未找到高效的整数分解算法，这一事实构成了现代多个加密系统（如 RSA 算法）的基础。整数分解问题属于 $NP$ 和 $co\text{-}NP$（甚至在 UP 和 co-UP 中）。如果该问题是 $NP$-完全的，那么多项式时间层次结构将会坍缩到第一级（即 $NP$ 将等于 $co\text{-}NP$）。已知的最佳整数分解算法是通用数域筛法，针对奇数整数 $n$，其运行时间为 $O(e^{\left(\sqrt[3]{\frac{64}{9}}\right)\sqrt[3]{(\log n)}\sqrt[3]{(\log \log n{)}^2}})$。然而，已知的最佳量子算法是 Shor 算法，它在多项式时间内运行。不幸的是，这一事实并未揭示该问题在非量子复杂度类中的位置。

其他复杂度类之间的分离

　　 许多已知的复杂度类被怀疑是不相等的，但这一点尚未得到证明。例如： $$P\subseteq NP\subseteq PP\subseteq PSPACE$$ 但也有可能 $P=PSPACE$。如果 $P\ne NP$，则 $P$ 也不等于 $PSPACE$。由于存在许多已知的复杂度类位于 $P$ 和 $PSPACE$ 之间，如 $RP$、$BPP$、$PP$、$BQP$、$MA$、$PH$ 等，因此有可能所有这些复杂度类最终会归结为同一个类。证明这些类之间的不等式将是复杂度理论的重大突破。

　　 同样，$co\text{-}NP$ 是包含 $NP$ 问题的补集问题（即答案是 “是” 或 “否” 相反）的一类。人们普遍认为 $NP$ 不等于 $co\text{-}NP$，但这一点尚未得到证明。显然，如果这两个复杂度类不相等，则 $P$ 不等于 $NP$，因为 $P=co\text{-}P$。因此，如果 $P=NP$，则我们将有： $$co\text{-}P=co\text{-}NP\Rightarrow NP=P=co\text{-}P=co\text{-}NP$$ 同样，目前尚不清楚 $L$（可以在对数空间内解决的所有问题的集合）是否严格包含于 $P$，还是与 $P$ 相等。同样，$P$ 和 $L$ 之间存在许多复杂度类，如 $NL$ 和 $NC$，目前尚不清楚它们是不同的类还是相等的类。

　　 有理由怀疑 $P$ 和 $BPP$ 是相等的。然而，目前仍未解决 $BPP=NEXP$ 的问题。

5. 难解性

　　 一个理论上可以解决，但需要不切实际的有限资源（例如时间）来解决的问题，被称为难解问题。相反，一个在实践中可以解决的问题被称为可解问题，字面意思是 “可以处理的问题”。术语不可行（字面意思是 “无法完成”）有时与难解问题互换使用，[15]，尽管这样做可能会与数学优化中的可行解产生混淆。[16]

　　 可解问题通常与有多项式时间解决方案的问题（P，PTIME）相关联；这被称为Cobham-Edmonds 论文。已知的难解问题包括那些是EXPTIME-hard的问题。如果NP与P不相等，则NP-hard 问题也是难解的。

　　 然而，这种认定并不准确：具有大次数或大主系数的多项式时间解决方案增长迅速，可能在实际大小的问题上变得不切实际；相反，增长较慢的指数时间解决方案在实际输入中可能是可行的，或者一个在最坏情况下需要很长时间的解决方案，在大多数情况下或平均情况下可能需要较短的时间，因此仍然是可行的。说一个问题不在P中并不意味着所有大规模的案例都很难解决，甚至不意味着其中大多数都是困难的。例如，Presburger 算术中的决策问题已知不在P中，但已经有算法能够在大多数情况下以合理的时间解决该问题。类似地，算法可以在不到二次时间的情况下解决 NP 完全背包问题，SAT 求解器也能轻松处理 NP 完全布尔可满足性问题的巨大实例。

　　 为了理解为什么指数时间算法通常在实践中不可用，考虑一个程序，该程序在停止之前执行 $2^n$ 次操作。对于小的 $n$，假设为 100，并且假设计算机每秒执行 ${10}^{12}$ 次操作，那么程序将运行约 $4\times {10}^{10}$ 年，这大致相当于宇宙的年龄。即使有更快的计算机，程序也只能用于非常小的实例，因此问题的难解性在某种程度上与技术进步无关。然而，一个指数时间算法，如果它需要 ${1.0001}^n$ 次操作，直到 $n$ 相对较大时才变得不切实际。

　　 同样，多项式时间算法并不总是可行的。如果它的运行时间是 $n^{15}$，那么考虑它是高效的就是不合理的，并且除非是小规模实例，否则它仍然是无用的。事实上，在实践中，即使是 $n^3$ 或 $n^2$ 的算法，在处理实际大小的问题时也常常不可行。

6. 连续复杂性理论

　　 连续复杂性理论可以指涉及连续函数的问题的复杂性理论，这些函数通过离散化进行近似，如数值分析中所研究的那样。数值分析的复杂性理论的一种方法是基于信息的复杂性。[17]

　　 连续复杂性理论也可以指模拟计算的复杂性理论，模拟计算使用连续的动力系统和微分方程。[18] 控制理论可以看作是一种计算形式，微分方程用于建模连续时间和混合离散-连续时间系统。[19]

7. 历史

　　 算法复杂性分析的早期例子是加布里埃尔·拉梅（Gabriel Lamé）在 1844 年对欧几里得算法运行时间的分析。

　　 在专门研究算法问题复杂性之前，许多基础工作已经由各种研究人员奠定。其中最具影响力的是艾伦·图灵（Alan Turing）在 1936 年对图灵机的定义，这被证明是计算机的一种非常稳健且灵活的简化版本。

　　 系统地研究计算复杂性的开端可追溯到尤里斯·哈特曼尼斯（Juris Hartmanis）和理查德·E·斯特恩斯（Richard E. Stearns）于 1965 年发表的开创性论文《算法的计算复杂性》。该文提出了时间复杂性和空间复杂性的定义，并证明了层次定理。[20] 此外，1965 年埃德蒙兹（Edmonds）建议将 “良好” 的算法定义为运行时间由输入大小的多项式界定的算法。[21]

　　 早期研究图灵机在特定资源限制下能解决的问题的论文包括：约翰·迈希尔（John Myhill）在 1960 年对线性有界自动机的定义，雷蒙德·斯穆利扬（Raymond Smullyan）对初级集的研究（1961），以及山田久男（Hisao Yamada）在 1962 年发表的关于实时计算的论文。[22] 更早一些，苏联领域的先驱鲍里斯·特拉赫滕布罗特（Boris Trakhtenbrot）（1956）研究了另一种特定的复杂性度量。[23] 他回忆道：

　　 然而，[我的]最初兴趣[在自动机理论]方面逐渐被计算复杂性所取代，这是一个令人兴奋的领域，它将来自开关理论的组合方法与算法理论的概念性工具结合在一起。这些想法早在 1955 年就出现在我脑海中，当时我创造了 “信号函数” 这一术语，今天它通常被称为 “复杂性度量”。[24]

　　 1967 年，曼纽尔·布卢姆（Manuel Blum）提出了一组公理（现在被称为布卢姆公理），明确了在可计算函数集上复杂性度量的期望特性，并证明了一个重要的结果——所谓的加速定理。1971 年，当斯蒂芬·库克（Stephen Cook）和列昂尼德·列文（Leonid Levin）证明了 NP 完全问题的实际相关性后，计算复杂性理论开始蓬勃发展。1972 年，理查德·卡普（Richard Karp）通过他的里程碑式论文《组合问题之间的可约性》，将这一思想推向了一个新的高度，在该文中他证明了 21 个各具特色的组合学和图论问题，每个问题因其计算难度而臭名昭著，都是 NP 完全问题。[25]

8. 另见

• 计算复杂性
• 描述性复杂性理论
• 游戏复杂性
• 叶语言
• 计算的极限
• 复杂性类别列表
• 可计算性与复杂性话题列表
• 计算机科学中的未解决问题列表
• 参数化复杂性
• 证明复杂性
• 量子复杂性理论
• 结构复杂性理论
• 超计算问题
• 数学运算的计算复杂性

9. 复杂性研究

• Wuppuluri, Shyam; Doria, Francisco A., 主编（2020），《揭示复杂性：格雷戈里·查伊廷的生活与工作》，世界科学出版社，doi:10.1142/11270，ISBN 978-981-12-0006-9，S2CID 198790362

10. 参考文献

引用

1. "P vs NP Problem | Clay Mathematics Institute". www.claymath.org. 2018 年 7 月 6 日存档自原始页面。于 2018 年 7 月 6 日检索。
2. 参见 Arora & Barak 2009，第 1 章：计算模型及其重要性
3. 参见 Sipser 2006，第 7 章：时间复杂度
4. Ladner, Richard E. (1975), "On the structure of polynomial time reducibility", *Journal of the ACM*, 22 (1): 151–171, doi:10.1145/321864.321877, S2CID 14352974.
5. Berger, Bonnie A.; Leighton, T (1998), "Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete", *Journal of Computational Biology*, 5 (1): 27–40, CiteSeerX 10.1.1.139.5547, doi:10.1089/cmb.1998.5.27, PMID 9541869.
6. Cook, Stephen (2000 年 4 月), *The P versus NP Problem* (PDF), Clay Mathematics Institute, 存档于 2010 年 12 月 12 日，2006 年 10 月 18 日检索。
7. Jaffe, Arthur M. (2006), "The Millennium Grand Challenge in Mathematics" (PDF), *Notices of the AMS*, 53 (6), 存档于 2006 年 6 月 12 日，2006 年 10 月 18 日检索。
8. Arvind, Vikraman; Kurur, Piyush P. (2006), "Graph isomorphism is in SPP", *Information and Computation*, 204 (5): 835–852, doi:10.1016/j.ic.2006.02.002.
9. Schöning, Uwe (1988), "Graph Isomorphism is in the Low Hierarchy", *Journal of Computer and System Sciences*, 37 (3): 312–323, doi:10.1016/0022-0000(88)90010-4
10. Babai, László (2016). "Graph Isomorphism in Quasipolynomial Time". arXiv:1512.03547 [cs.DS].
11. Fortnow, Lance (2002 年 9 月 13 日). "Computational Complexity Blog: Factoring". weblog.fortnow.com.
12. Wolfram MathWorld: Number Field Sieve
13. Boaz Barak's course on Computational Complexity Lecture 2
14. Hopcroft, J.E., Motwani, R. 和 Ullman, J.D. (2007) *Introduction to Automata Theory, Languages, and Computation*, Addison Wesley, 波士顿/旧金山/纽约 (第 368 页)
15. Meurant, Gerard (2014). *Algorithms and Complexity*. Elsevier. 第 4 页. ISBN 978-0-08093391-7.
16. Zobel, Justin (2015). *Writing for Computer Science*. Springer. 第 132 页. ISBN 978-1-44716639-9.
17. Smale, Steve (1997). "Complexity Theory and Numerical Analysis". *Acta Numerica*. 6. 剑桥大学出版社: 523–551. Bibcode:1997AcNum...6..523S. CiteSeerX 10.1.1.33.4678. doi:10.1017/s0962492900002774. S2CID 5949193.
18. Babai, László; Campagnolo, Manuel (2009). "A Survey on Continuous Time Computations". arXiv:0907.3117 [cs.CC].
19. Tomlin, Claire J.; Mitchell, Ian; Bayen, Alexandre M.; Oishi, Meeko (2003 年 7 月). "Computational Techniques for the Verification of Hybrid Systems". *Proceedings of the IEEE*. 91 (7): 986–1001. CiteSeerX 10.1.1.70.4296. doi:10.1109/jproc.2003.814621.
20. Fortnow & Homer (2003)
21. Richard M. Karp, "Combinatorics, Complexity, and Randomness", 1985 年图灵奖讲座
22. Yamada, H. (1962). "Real-Time Computation and Recursive Functions Not Real-Time Computable". *IEEE Transactions on Electronic Computers*. EC-11 (6): 753–760. doi:10.1109/TEC.1962.5219459.
23. Trakhtenbrot, B.A.: Signalizing functions and tabular operators. *Uchionnye Zapiski Penzenskogo Pedinstituta* (Transactions of the Penza Pedagogical Institute) 4, 75–87 (1956) (俄文)
24. Boris Trakhtenbrot, "From Logic to Theoretical Computer Science An Update". In: *Pillars of Computer Science*, LNCS 4800, Springer 2008.
25. Richard M. Karp (1972), "Reducibility Among Combinatorial Problems" (PDF), in R. E. Miller; J. W. Thatcher (eds.), *Complexity of Computer Computations*, New York: Plenum, pp. 85–103, 存档于 2011 年 6 月 29 日，2009 年 9 月 28 日检索

11. 教科书

• Arora, Sanjeev; Barak, Boaz (2009), *Computational Complexity: A Modern Approach*, Cambridge University Press, ISBN 978-0-521-42426-4, Zbl 1193.68112
• Downey, Rod; Fellows, Michael (1999), *Parameterized Complexity*, Monographs in Computer Science, Berlin, New York: Springer-Verlag, ISBN 9780387948836
• Du, Ding-Zhu; Ko, Ker-I (2000), *Theory of Computational Complexity*, John Wiley & Sons, ISBN 978-0-471-34506-0
• Garey, Michael R.; Johnson, David S. (1979). *Computers and Intractability: A Guide to the Theory of NP-Completeness*. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676.
• Goldreich, Oded (2008), *Computational Complexity: A Conceptual Perspective*, Cambridge University Press
• van Leeuwen, Jan, ed. (1990), *Handbook of Theoretical Computer Science (vol. A): Algorithms and Complexity*, MIT Press, ISBN 978-0-444-88071-0
• Papadimitriou, Christos (1994), *Computational Complexity (1st ed.)*, Addison Wesley, ISBN 978-0-201-53082-7
• Sipser, Michael (2006), *Introduction to the Theory of Computation (2nd ed.)*, USA: Thomson Course Technology, ISBN 978-0-534-95097-2

12. 综述

• Khalil, Hatem; Ulery, Dana (1976), "A review of current studies on complexity of algorithms for partial differential equations", *Proceedings of the annual conference on - ACM 76*, pp. 197–201, doi:10.1145/800191.805573, ISBN 9781450374897, S2CID 15497394
• Cook, Stephen (1983), "An overview of computational complexity", *Communications of the ACM*, 26 (6): 400–408, doi:10.1145/358141.358144, ISSN 0001-0782, S2CID 14323396
• Fortnow, Lance; Homer, Steven (2003), "A Short History of Computational Complexity" (PDF), *Bulletin of the EATCS*, 80: 95–133
• Mertens, Stephan (2002), "Computational Complexity for Physicists", *Computing in Science & Engineering*, 4 (3): 31–47, arXiv:cond-mat/0012185, Bibcode:2002CSE.....4c..31M, doi:10.1109/5992.998639, ISSN 1521-9615, S2CID 633346

13. 外部链接

• 复杂性动物园（The Complexity Zoo）
• “计算复杂性类别”，《数学百科全书》，EMS Press，2001 [1994]
• Scott Aaronson: 为什么哲学家应该关注计算复杂性