计算复杂性理论（二）
1.3 区分复杂性概念
有了这些约定，我们现在可以记录计算复杂性理论中赋予“复杂性”一词的含义与其他几个领域赋予该术语的含义不同的几个方面。在计算复杂性理论中，问题 – 即自然数、公式、图等有限组合对象的无限集 – 被赋予了“复杂性”。正如我们刚刚看到的，这种分配基于最有效算法的时间或空间复杂度，通过该算法可以确定问题的成员资格。柯尔莫哥洛夫复杂性理论 (例如 Li and Vitányi 1997) 研究了一种独特的复杂性概念。本主题不是研究数学对象集的复杂性，而是试图发展一种适用于单个组合对象 – 例如特定的自然数、公式、图等的复杂性概念。例如，有限字符串 x∈{0,1}∗ 的柯尔莫哥洛夫复杂度被定义为对于一个固定的通用图灵机，当给定空字符串作为输入时，输出 x 的最小程序的大小。在这种情况下，对象的“复杂性”被视为衡量其描述在算法上可压缩程度的标准。
描述复杂性理论 (例如 Immerman 1999) 研究了另一个复杂性概念。与计算复杂性理论一样，描述复杂性理论也试图对无限组合对象集的复杂性进行分类。然而，问题的“复杂性”现在是根据定义其实例相对于所有有限结构类所需的逻辑资源来衡量的，以获得适当的签名。正如我们将在第 4.4 节中看到的那样，这种方法通常会产生计算复杂性理论中研究的相同类别的替代特征。
与计算复杂性理论相关的另一个主题是算法分析 (例如 Knuth (1973)、Cormen、Leiserson 和 Rivest 2005)。与计算复杂性理论一样，算法分析研究问题的复杂性，也使用上面定义的时间和空间度量 tM(n) 和 sM(x)。算法分析的方法论不同于计算复杂性理论，因为它主要强调衡量特定算法解决给定问题的效率。另一方面，在寻求根据问题的内在难度对其进行分类时，复杂性理论必须考虑所有算法解决问题的效率。因此，复杂性理论家更多地使用复杂性类别，例如 P、NP 和 PSPACE，这些类别的定义在不同的参考模型选择中都是稳健的。另一方面，在算法分析中，算法通常相对于 P 内的运行时间 log2(n)、n、n⋅log2(n)、n2、n3、… 的更细粒度层次结构来表征。[7]
2. 复杂性理论的起源
2.1 丘奇论题和有效可计算性
计算复杂性理论的起源在于可计算性理论和算法分析的早期发展。前者始于 20 世纪 30 年代哥德尔、丘奇、图灵、克莱恩和波斯特的工作，他们最初试图回答希尔伯特的判定问题——即确定给定的一阶逻辑公式是否有效可判定的问题是否有效？当时，可判定性的概念是原则上有效可判定性——即通过规则控制的方法（或有效程序）的可判定性，其每个基本步骤都可以由有限数学代理单独执行，但其执行可能需要无限数量的步骤或内存空间。
我们现在知道，判定问题已经由 Church (1936a) 和 Turing (1937) 给出了否定的答案。他们提供的解决方案可以重构如下：1) 给出计算模型 M 的数学定义；2) 给出非形式化论证以表明 M 包含所有有效程序的代表；3) 然后给出形式化论证以表明没有机器 M∈M 能够判定 FO-VALID。Church (1936b) 将 M 视为无类型 lambda 演算中的项 Λ 类，而 Turing 则将 M 视为与图灵机的 T 类对应的类。丘奇还证明了 lambda 可定义函数类 FΛ 与一般递归函数类 FR（由 Gödel 1986b 和 Kleene 1936 定义）在外延上是一致的。图灵随后证明了图灵机可计算的函数类 FT 与 FΛ 在外延上是一致的。
FΛ、FR 和 FT 类的外延一致性为克莱恩 (1952) 后来称之为丘奇论题的第一个证据，即(CT) 函数 f:Nk→N 当且仅当 f(x1,…,xk) 是递归的，才是有效可计算的。
CT 可以被理解为为丘奇和图灵对判定问题的否定回答赋予了精确的认识论意义。因为如果承认 FR（因此 FΛ 和 FT 也一样）包含所有有效可计算函数，那么就可以通过证明 X 的特征函数 cX(x) 不是递归的，证明问题 X 是有效不可判定的——即无论其效率如何，任何算法都无法判定。因此，CT 允许我们从可以证明 cX(x) 是非递归的问题 X 中推断出来——例如停机问题（图灵 1937）或半群的字问题（1947 年后）——无法有效判定。
然而，很明显，我们对这种分类的论证并不比我们对 CT 本身的论证更有力。一种经常被引用来支持该论点的证据是，Λ、R 和 T 成员计算的函数类的重合指向递归函数类的数学稳健性。两种相关的归纳证据形式如下：（i）随后定义了许多其他独立驱动的计算模型来描述同一类函数；（ii）该论点通常被认为产生了一种函数分类，这种分类迄今为止与我们在相关的“原则上”意义上计算它们的能力相吻合。
但即使承认 CT 的正确性，我们也必须牢记，它试图分析的可计算性概念是一种理想化的概念，在某些方面与我们日常的计算实践脱节。请注意，即使 f(x) 只能由图灵机 T 计算，其时间和空间复杂度函数 tT(n) 和 sT(n) 的值即使对于较小的输入也可能大得惊人，CT 也会将其归类为有效可计算的。[8]
尽管有这样的例子，但人们经常声称，图灵对有效可计算性的原始描述为更一般地分析一个函数可被机械设备计算意味着什么提供了一个模板。例如，Gandy (1980) 和 Sieg (2009) 认为，图灵最初得出图灵机定义的过程可以推广为对机械计算设备的抽象描述。反过来，这种特性可以理解为描述物理系统必须遵循的属性，以便具体实现。例如，图灵机只能访问或修改其读写头当前正在扫描的磁带单元，这一要求可以推广为允许在距离一个或多个计算位置一定距离处修改机器状态。反过来，这种要求可以理解为反映了古典物理学不允许超距作用的可能性。
在此基础上，CT 有时也被理解为对哪些函数是物理可计算的做出预测——即，它们的值可以通过测量我们希望用作实际计算设备的物理系统的状态来确定。因此，我们可能希望对 Gandy-Sieg 条件的进一步细化（可能与第 4.5 节中讨论的 Leivant (1994) 或 Bellantoni 和 Cook (1992) 的提议一致）最终将提供洞察力，说明为什么某些数学计算模型似乎比其他模型更准确地解释了复杂性理论试图分析的具体体现计算的迫切需要。
2.2 Cobham-Edmond 的论点和可行的可计算性
Church 的论点经常被引用为一个典型案例，其中数学方法已被成功地用于对一个非正式概念（即有效可计算性）进行精确分析。我们也很自然地会问，第 1 节中描述的可行可计算性概念本身是否允许与 Church 的论点类似的数学分析。
我们在上面看到，因式分解是一个先前的数学和实际问题的例子，历史上人们一直在寻求更有效的算法。由于 TSP、整数规划和完美匹配等组合问题在科学、工业和文职应用中的作用，有效解决这些问题的任务在 20 世纪 50 年代和 60 年代变得越来越重要。与此同时，数字计算机的出现首次使许多此类问题能够大规模机械解决。
这个时代也经历了几个理论步骤，预示着人们试图发展一种可行可计算性的一般理论。图灵机模型的时间和空间复杂度的基本定义最早由 Hartmanis 和 Stearns (1965) 在题为“论算法的计算复杂性”的论文中系统地表述。这篇论文也是所谓的层次定理（见第 3.2 节）的起源，该定理表明，图灵机计算的时间或空间界限足够大地增加，可以解决更多问题。
在此期间，还对不同计算模型之间的关系进行了系统探索。这包括传统图灵机模型的变体，带有附加磁头、磁带和辅助存储设备（如堆栈）。大约在这个时候引入的另一个重要模型是随机存取（或 RAM）机器 A（例如，参见 Cook 和 Reckhow 1973）。该模型提供了当代数字计算机所基于的所谓冯·诺依曼架构的简化表示。具体来说，RAM 机器 A 由有限序列的指令（或程序）⟨π1,…,πn⟩ 组成，这些指令（或程序）表示如何将数值运算（通常是加法和减法）应用于寄存器序列 r1,r2,…，其中可以通过索引直接存储和检索值。
要证明这些模型之一 M1 确定与某个参考模型 M2（例如 T）相同的函数类，需要证明对于所有 M1∈M1，都存在一个机器 M2∈M2，它计算与 M1 相同的函数（反之亦然）。这通常通过构造 M2 来实现，使得 M1 的每个基本步骤都由 M2 的一个或多个基本步骤模拟。因此，证明模型 M1 和 M2 计算的函数类的一致性通常会产生关于它们相对效率的额外信息。例如，通常可以从 M1 和 M2 之间的模拟定义中提取时间和空间开销函数 ot(x) 和 os(x)，使得如果函数 f(x) 的值可以由机器 M1∈M1 在时间 t(n) 和空间 s(n) 中计算出来，那么它也可以由某台机器 M2∈M2 在时间 ot(t(n)) 和空间 os(s(n)) 中计算出来。
对于一大类模型，一个重大发现是可以找到有效的模拟。例如，乍一看，模型 A 可以比模型 T 更有效地实现熟悉的算法，因为 RAM 机可以在一个步骤中访问其任意寄存器，而图灵机每次只能移动其头部一个单元。尽管如此，可以证明图灵机模型可以模拟 RAM 模型，具有立方时间开销和常数空间开销 - 即 ot(t(n))∈O(t(n)3) 和 os(s(n))∈O(s(n)) (Slot and Emde Boas 1988)。基于此和相关结果，Emde Boas (1990) 提出了以下建议，以描述可用于定义时间和空间复杂度的参考模型之间的关系：
不变性论点“合理的”计算模型可以在多项式有界的时间开销和常数因子的空间开销内相互模拟。
20 世纪 60 年代还见证了适用于图论和线性代数等领域问题的算法方法的许多进展。其中一个例子是一种称为动态规划的技术。这种方法有时可用于找到优化问题的有效解决方案，优化问题要求我们从一系列可能的解决方案中找到最小化或最大化某个量的对象。基于动态规划的算法通过递归地将此类问题分解为子问题来解决此类问题，然后计算并以可以有效地重新组合的方式存储这些子问题的最优值，以实现最佳整体解决方案。
Bellman (1962) 证明，通过使用动态规划，TSP 的简单时间复杂度 O(n!) 可以改进为 O(2nn2)。因此，问题来了，是否有可能进一步改进此类算法，不仅针对 TSP，还针对其他问题（例如 SAT），人们一直在寻找有效的算法，但不知道是否存在。为了理解这个问题的利害关系，请注意 TSP 的简单算法的工作原理如下：1) 枚举 G 中所有可能行程的集合 SG，并计算它们的权重；2) 检查这些行程中的任何一条的费用是否≤b。但请注意，如果 G 有 n 个节点，则 SG 可能包含多达 n! 条行程。
这就是所谓强力算法的一个例子，即通过穷举所有可能的解决方案，然后依次测试其中是否正确来解决问题。更准确地说，如果存在一个可判定关系 RX 和一组均匀定义的有限集 Sx，使得 x∈X 当且仅当存在一个可行大小的见证 y∈Sx 使得 RX(x,y)，则称问题 X 允许强力解。这样的 y 通常被称为 x 在 X 中成员身份的证书。通过穷举搜索所有证书 y0,y1,…∈Sx 并在每一步检查 RX(x,y) 是否成立来确定 x∈X 的过程称为强力搜索。例如，可以通过搜索类型为 v:{0,…,n−1}→{0,1} 的可能估值函数集 Sϕ 来确定问题 SAT 中具有原子字母的命题公式 ϕ 在 P0,…,Pn−1 中的成员资格，以确定是否存在 v∈Sϕ 使得 [[ϕ]]v=1。但请注意，由于 Sϕ 中有 2n 个函数，因此这只能产生指数时间决策算法。
20 世纪 60 年代和 70 年代出现了许多其他问题，如 SAT 和 TSP，很容易看出它们具有指数时间强力算法，但没有多项式时间算法。在此基础上，人们逐渐接受了这样一个观点：可判定问题难以解决的充分条件是，解决该问题的最有效算法最多具有指数时间复杂度。相应的积极假设是，拥有多项式时间决策算法应被视为将问题视为可判定的充分理由，这一假设最早由 Cobham (1965) 和 Edmonds (1965a) 提出。
Cobham 首先引用了激发不变性论题的证据，表明问题是否接受多项式时间算法与使用哪种计算模型来衡量广泛替代方案的时间复杂度无关。此外，他还提出了一种与机器无关的 FP 类（即可在多项式时间内计算的函数 f:Nk→N）的表征，其形式为原始递归定义的受限形式，称为符号上的有界递归（参见第 4.5 节）。
Edmonds (1965a) 首次提出多项式时间复杂度可以作为可行性的积极标准——或者用他的话来说，拥有“好的算法”——他在一篇论文中表明，一个可能先验地被认为只能通过强力搜索（上述完美匹配的概括）解决的问题可以通过多项式时间算法判定。与苏联对强力搜索的类似研究相似，Edmonds (1965b) 在随后的一篇论文中也对复杂度类 NP 进行了非正式描述。具体来说，他将这类描述为包含那些存在“良好描述”的问题 X——即 X 使得实例 x 的成员资格可以通过使用强力搜索找到可行大小的证书 y 来验证，该证书 y 证明 x 在 X 中的成员资格。[9]
这些观察为后来被称为 Cobham-Edmonds 论题的论点奠定了基础（例如，参见 Brookshear 等人 2006；Goldreich 2010；Homer 和 Selman 2011）：
（CET）函数 f:Nk→N 是可计算的当且仅当 f(→x) 由某个机器 M 计算，使得 tM(n)∈O(nk)，其中 k 是固定的，M 是从合理的计算模型 M 中得出的。
CET 提供了第 1 节中讨论的可计算函数概念的特征，其形式类似于 Church 的论题。决策问题的相应论题认为，只要问题属于 P 类，它就是可判定的。然而，正如刚刚表述的那样，CET 依赖于合理计算模型的非正式概念。可以通过用来自第一个机器类的特定模型（例如 T 或 A）替换此概念来给出更精确的公式，如下面第 3.1 节中讨论的。
CET 现在在理论计算机科学中被广泛接受，其原因与传统上支持丘奇论题的原因大致相同。例如，FP 类的定义不仅在不同的基于机器的计算模型中是稳定的，就像不变性论题所强调的那样，而且还有几种与机器无关的此类特征，我们将在第 4 节中讨论这些特征。这些结果证明了多项式时间可计算性定义的稳健性。
也可以为 CET 提出一个与 CT 的准归纳论证相似的论证。因为在我们可以为我们在实践中关注的实例类统一计算函数值（或解决问题）的情况下，这通常正是因为我们已经发现了一种可以在当前计算硬件上实现的多项式时间算法（因此也可以作为图灵机）。在我们目前无法统一地计算我们感兴趣的所有参数的函数值（或解决一个问题）的情况下，通常是因为我们还没有发现多项式时间算法（而且在许多情况下，也可能有间接证据表明这种算法不存在）。
尽管如此，CET 的几个特点表明它应该被认为不如 CT 完善。其中最重要的是，我们目前还不知道 P 是否正确包含在复杂度类中，例如 NP，而 NP 似乎包含高度棘手的问题。对于我们在实践中可以决定的计算问题类别与使用传统确定性图灵机在多项式时间内可判定的问题完全一致的说法，还经常提出以下额外警告。[10]
CET 将那些最有效算法对任意大的标量因子 c 和指数 k 具有时间复杂度 c⋅nk 的函数归类为可行。这意味着，如果一个函数只能通过时间复杂度为 21000⋅n 或 n1000 的算法来计算，它仍然会被归类为可行函数。尽管我们无法在实践中为大多数或所有输入计算其值，但情况仍然如此。
CET 将最有效算法的时间复杂度为超多项式增长级（包括例如 2.000001n 或 nlog(log(log(n)))）的函数归类为不可行函数。但是，当应用于我们可能关注的输入类型时，此类算法的运行效率会比时间复杂度为（例如）O(n2) 的算法更高。
