计算复杂性理论（三）

存在这样的问题，对于这些问题，已知最有效的决策算法在最坏情况下具有指数时间复杂度（事实上，在一般情况下是 NP-hard - 参见第 3.2 节），但在平均情况下或对于实际感兴趣的大量问题实例，其运行时间在多项式时间内。常引用的例子包括 SAT（例如 Cook 和 Mitchell 1997），以及图论中的一些问题（例如 Scott 和 Sorkin 2006）和计算代数（例如 Kapovich 等人 2003）。

复杂性理论中研究的许多问题都是优化问题的决策变体。在这些问题是 NP 完全的情况下，CET（与 P≠NP 一起 - 参见第 4.1 节）的结果是它们不允许可行的精确算法 - 即保证始终找到最大或最小解的算法。尽管如此，众所周知，NP 完全问题的一个重要子类具有多项式时间近似算法——即保证找到在某个最优常数因子范围内的解决方案的算法。例如，下面定义的问题的优化版本 VERTEX COVER 具有一个简单的多项式时间近似算法，该算法使我们能够找到一个解决方案（即一组顶点，包括输入图的每个边中的至少一个），该解决方案的大小不大于最优解决方案的两倍。

存在非经典计算模型，据推测，它们会根据“多项式时间可计算性”的适当定义产生不同的问题分类。一个值得注意的例子是存在一种称为 Shor 算法的程序，它相对于称为量子图灵机的计算模型（参见第 3.4.3 节）在多项式时间内解决了问题 FACTORIZATION。

3. 技术发展

3.1 确定性和非确定性计算模型

根据​​ Cobham-Edmonds 论文，复杂性类 P 描述了可行可判定问题类。正如我们刚刚看到的，这个类是根据参考模型 T 定义的，因为它假设它是一个“合理”的计算模型。复杂性理论还研究了其他几种计算模型，并不是因为它们被认为是具体体现的计算成本的准确表示，而是因为它们有助于我们更好地理解可行可计算性的极限。其中最重要的是非确定性图灵机模型 N。

回想一下，确定性图灵机 T∈T 可以表示为一个元组 ⟨Q,Σ,δ,s⟩，其中 Q 是一组有限的内部状态，Σ 是有限的磁带字母表，s∈Q 是 T 的起始状态，δ 是一个转换函数，将状态符号对 ⟨q,σ⟩ 映射到状态动作对 ⟨q,a⟩。这里 a 是从动作集合 {σ,⇐,⇒} 中选择的，即在当前方格上写入符号 σ∈Σ、将头部向左移动或将头部向右移动。因此，这样的函数类型为 δ:Q×Σ→Q×α。另一方面，非确定性图灵机 N∈N 的形式为 ⟨Q,Σ,Δ,s⟩，其中 Q、Σ 和 s 与之前相同，但 Δ 现在仅要求是关系 - 即 Δ⊆(Q×Σ)×(Q×α)。因此，N 处于状态 q 并读取符号 σ 的机器配置可以导致有限多个不同的后继配置 - 例如，对于不同的状态 q′ 和 q″ 以及动作 a′ 和 a″，Δ 可能将 ⟨q,σ⟩ 与 ⟨q′,a′⟩ 和 ⟨q″,a″⟩ 相关。[11]

确定性机器和非确定性机器定义的差异也要求改变机器决定语言X的定义。回想一下，对于确定性机器T，从初始配置C0开始的计算序列是机器配置C0、C1、C2、…的有限或无限序列。这样的配置包括T的磁带内容、内部状态和头部位置的规范。Ci+1是通过将转换函数δ应用于Ci编码的活动状态-符号对而确定的唯一配置，如果δ本身在该对上未定义（在这种情况下计算序列是有限的，对应于暂停计算），则Ci+1未定义。但是，如果N是非确定性机器，则在当前头部位置可能存在多个与当前配置通过Δ相关的配置。在这种情况下，有限或无限序列 C0,C1,C2,… 被称为从初始配置 C0 开始的针对 N 的计算序列，只要对于所有 i≥0，Ci+1 都是通过 Δ 与 Ci 相关的配置之一（如果不存在这样的配置，则同样未定义）。

我们现在还重新定义了机器 N 决定语言 X 所需的条件：

N 总是停止 - 即对于所有初始配置 C0，N 的计算序列 C0、C1、C2、… 都是有限长度的；

如果 x∈X 且 C0(x) 是将 x 编码为输入的 N 的配置，则存在 N 的计算序列 C0(x)、C1(x)、…、Cn(x)，使得 Cn(x) 为接受状态；

如果 x∉X，则 N 的所有计算序列 C0(x)、C1(x)、…、Cn(x) 都使得 Cn(x) 为拒绝状态。

请注意，此定义对接受和拒绝计算的处理是不对称的。因为如果 x∈X，N 从 C0(x) 开始的某些计算序列仍可能导致拒绝状态，只要它至少导致一个接受状态即可。另一方面，如果 x∉X，则 N 从 C0(x) 开始的所有计算都需要导致拒绝状态。

非确定性机器有时被描述为在计算过程中的各个点在不同的可能后继配置之间做出不确定的“选择”。但前述定义实际上描述的是确定性机器 N 从给定配置 C0 开始的所有可能计算序列的树 TNC0（图 1 中描绘了一个例子）。鉴于刚才提到的不对称性，通常必须调查 TNC0(x) 中的所有分支，以确定 N 对输入 x 的决定。



图 1. 非确定性图灵机 N 从初始配置 C0(x) 开始的潜在计算树 TNC0(x)。接受状态标记为 ⊙，拒绝状态标记为 ∘。请注意，尽管这棵树包含长度为 4 的接受计算序列，但其最大深度 5 仍计入 timeN(n)=max{depth(TNC0(x)) : |x|=n} 的确定。

非确定性机器 N 的时间复杂度 tN(n) 是所有输入 x 的计算树 TNC0(x) 的深度之最大值，使得 |x|=n。相对于此定义，非确定性机器可用于在 n 的时间多项式中实现许多强力算法。例如，SAT 问题可以通过非确定性机器来解决，该机器在输入 ϕ 时使用其磁带的一部分非确定性地构造（或“猜测”）一个表示估值 v 的字符串，为 ϕ 的 n 个命题变量中的每一个分配一个真值，然后使用真值表的方法（关于 n 是多项式的）计算 [[ϕ]]v。由于 ϕ∈SAT 万一存在令人满意的估值，因此这是相对于上述惯例 (i)-(iii) 决定 SAT 的正确方法。这意味着 SAT 可以在相对于 N 的多项式时间内求解。

这个例子还说明了为什么在原始确定性模型 T 中添加非确定性不会扩大可判定问题的类别。因为如果 N∈N 决定 X，那么就有可能构造一个机器 TN∈T，它也决定 X，通过连续模拟 N 在计算过程中可能做出的有限多个非确定性选择序列中的每一个。[12] 显然，如果 N 的时间复杂度为 f(n)，那么 TN 通常必须检查 O(kf(n)) 个选择序列（对于固定的 k），才能确定长度为 n 的输入下 N 的输出。虽然这种模拟的可用性表明 N 决定的语言类别与 T 决定的语言类别相同——即完全是递归的——但它也说明了为什么非确定性图灵机对语言的多项式时间可判定性仅保证确定性图灵机在指数时间内可判定该语言。

为了解释这一观察结果，Emde Boas (1990) 区分了两类计算模型，并将它们称为第一类和第二类机器。第一类机器包含基本图灵机模型 T，以及满足该模型不变性论题的其他模型。如我们所见，这包括多磁带和多头图灵机模型以及 RAM 模型。另一方面，第二类机器被定义为包括那些确定性模型，其成员可用于有效模拟非确定性计算。可以证明这包括许多标准的并行计算模型，例如 PRAM 机，将在第 3.4.3 节中讨论。对于此类模型，多项式时间、非确定性多项式时间和多项式空间的定义是一致的。

经验证明，在制定 Cobham-Edmonds 论题的过程中，我们应该将第一个机器类的成员视为合理的计算模型。人们还普遍认为，第二个机器类的成员不能提供具体体现计算所涉及的复杂性成本的真实表示（Chazelle 和 Monier (1983)、Schorr (1983)、Vitányi (1986)）。然而，正式证明这一点需要证明复杂性类的分离结果，而目前尚未解决。因此，虽然人们普遍认为第二个机器类适当地扩展了第一个机器类，但这目前是一个悬而未决的问题。

3.2 复杂性类和层次定理

回想一下，复杂性类是一组语言，所有这些语言都可以在给定的时间或空间复杂性界限 t(n) 或 s(n) 内根据固定的计算模型确定。为了避免因我们为“非自然”的时间或空间界限（例如非递归界限）定义复杂度类而产生的病态，标准做法是将注意力限制在 t(n) 和 s(n) 是时间或空间可构造的复杂度类上。当存在一个图灵机，它对由 1n（即一串 n 个 1）组成的输入在恰好 t(n) 步之后停止时，我们称 t(n) 是时间可构造的。类似地，当存在一个图灵机，它对输入 1n 在访问了恰好 s(n) 个磁带单元后停止时，我们称 s(n) 是空间可构造的。容易看出，时间和空间可构造函数包括那些作为实践中通常考虑的算法复杂度出现的函数 - log(n),nk,2n,n! 等。

当我们对确定性计算感兴趣时，通常将本节中定义的经典复杂性类的定义基于模型 T。假设 t(n) 和 s(n) 分别是时间和空间可构造函数，则 TIME(t(n)) 和 SPACE(s(n)) 类定义如下：

TIME(t(n))={X⊆{0,1}∗ : ∃T∈T∀n(timeT(n)≤t(n))and T decides X}SPACE(s(n))={X⊆{0,1}∗ : ∃T∈T∀n(spaceT(n)≤s(n))and T decides X}

由于单变量 n 中的所有多项式对于某个 k 都是 O(nk) 阶的，因此分别定义了多项式时间和多项式空间类因为 P=⋃k∈NTIME(nk) 和 PSPACE=⋃k∈NSPACE(nk)。引入类 EXP=⋃k∈NTIME(2nk)（指数时间）和 L=SPACE(log(n))（对数空间）也是标准的。

除了基于确定性模型 T 的类之外，还研究了基于模型 N 的类似非确定性复杂性类。具体来说，类 NTIME(t(n)) 和 NSPACE(s(n)) 定义如下：

NTIME(t(n))={X⊆{0,1}∗ : ∃N∈N∀n(timeN(n)≤t(n))并且 N 决定 X}NSPACE(s(n))={X⊆{0,1}∗ : ∃N∈N∀n(spaceN(n)≤s(n))并且 N 决定 X}

类 NP（非确定性多项式时间）、NPSPACE（非确定性多项式空间）、NEXP（非确定性指数时间）和 NL（非确定性对数空间）的定义类似于 P、NP、EXP 和 L - 例如NP=⋃k∈NNTIME(nk)。

复杂性理论中的许多经典结果和重要未决问题涉及这些类之间的包含关系。其中最核心的是所谓的层次定理，该定理表明，如果 t2(n) 的增长速度足够快于 t1(n)，则 TIME(t2(n)) 类是 TIME(t1(n)) 的适当超集（NTIME(t(n)) 和 SPACE(s(n)) 也是如此）。

定理 3.1 假设 t1(n) 和 t2(n) 是时间可构造的，s1(n) 和 s2(n) 是空间可构造的，t2(n)≥t1(n)≥n，且 s2(n)≥s1(n)≥n。

如果

limn→∞t1(n)log(t1(n))t2(n)=0，

则 TIME(t1(n))⊊TIME(t2(n))。（Hartmanis and Stearns 1965）

如果

limn→∞t1(n+1)t2(n)=0，

则 NTIME(t1(n))⊊NTIME(t2(n))。（Cook 1972）

如果

limn→∞s1(n)s2(n)=0，

则 SPACE(s1(n))⊊SPACE(s2(n))。 （Stearns、Hartmanis 和 Lewis 1965）

这些结果都可以通过对图灵（1937）最初证明经典停机问题的不可判定性的对角线论证的修改来证明。[13] 尽管如此，定理 3.1 已经对上面介绍的复杂性类别之间的关系产生了许多有趣的推论。例如，由于函数 nk 和 nk+1 满足第 i) 部分的假设，我们可以看到 TIME(nk) 始终是 TIME(nk+1) 的真子集。从第 i) 部分还得出，对于任何超多项式增长阶的 f(n)，P⊊TIME(f(n)) - 例如 2n.0001 或 2log(n)2。类似地，第 i) 部分和第 ii) 部分分别意味着 P⊊EXP 和 NP⊊NEXP。同样，从第 iii) 部分可以得出 L⊊PSPACE。

请注意，由于每个确定性图灵机在定义上都是非确定性机器，因此我们显然有 P⊆NP 和 PSPACE⊆NPSPACE。以下经典结果报告了有关时间和空间复杂度之间关系的一些附加信息：

定理 3.2 假设 f(n) 是时间和空间可构造的。然后

NTIME(f(n))⊆SPACE(f(n))

NSPACE(f(n))⊆TIME(2O(f(n)))

第一个结果重现了先前的观察结果，即运行时间为 f(n) 的非确定性机器 N 可以由确定性机器 TN 在时间指数为 f(n) 的条件下模拟。为了获得定理 3.2.i)，请注意，这个过程可以在由 f(n) 界定的空间中进行，前提是我们确保在开始新的模拟之前擦除先前模拟使用过的单元。[14]

Savitch (1970) 的另一个经典结果将 SPACE(f(n)) 与 NSPACE(f(n)) 联系起来：

定理 3.3

对于任何空间可构造函数 s(n)，NSPACE(s(n))⊆SPACE((s(n))2)。

推论是 PSPACE=NPSPACE，这表明非确定性在空间方面的计算能力不如在时间方面。

上述结果在复杂性类别之间建立了以下基本关系，这些关系也在图 2 中进行了描述：

L⊆NL⊆P⊆NP⊆PSPACE⊆EXP⊆NEXP⊆EXPSPACE

正如我们所见，这是定理 3.1 的结果，即 L⊊PSPACE 和 P⊊EXP。因此，前四个显示的包含中至少有一个是正确的，第三、第四或第五个包含中至少有一个是正确的。



图 2。主要复杂性类之间的包含关系。目前已知唯一正确的包含是 L⊊PSPACE 和 P⊊EXP。

然而，目前，这是目前已知的全部——即虽然可以引用各种启发式论据来支持其他显示包含的正确性，但没有一个被证明成立。提供这些主张的无条件证明仍然是复杂性理论的一个主要未实现的目标。例如，以下内容通常被描述为整个理论计算机科学中最重要的未解决的问题：

开放问题 1 P 是否正确包含在 NP 中？

开放问题 1 的重要性以及关于其他复杂性类之间的包含关系的其他几个未解决问题将在第 4.1 节中更详细地讨论。

3.3 归约和 NP 完备性

现在介绍了复杂性理论中研究的一些主要类别，接下来我们来讨论它们的内部结构问题。这可以使用一个问题可归约到另一个问题的概念以及一个问题对于一个类别而言是完备的概念来研究。非正式地说，只要解决 Y 的方法也能得到解决 X 的方法，则称问题 X 可归结为另一个问题 Y。因此，X 可归结为 Y 可以理解为表明解决 Y 至少与解决 X 一样困难。只要 X 是 C 的成员，并且 C 中的所有问题都可以归结为 X，则称问题 X 对于复杂度类 C 是完全的。因此，X 对于 C 的完全性可以理解为表明 X 代表了 C 中最困难的问题。

归结和完全性的概念最初是在可计算性理论中引入的。其中研究了许多不同的归结定义，其中最为人熟知的是多对一和图灵可归结性（例如，参见 Rogers 1987）。复杂性理论中对这两者进行了类似研究，研究名称为多项式时间多一可约性（也称为卡普可约性（Karp 1972））和多项式时间图灵可约性（也称为库克可约性（Cook 1971）。为简单起见，我们在此仅考虑前者。[15]

定义 3.1 对于语言 X,Y⊆{0,1}∗，如果存在一个多项式时间可计算函数 f(x)，则称 X 是多项式时间多一可约化为 Y，并且

对于所有 x∈{0,1}∗，x∈X 当且仅当 f(x)∈Y

在这种情况下，我们写 X≤PY，并称 f(x) 是 X 到 Y 的多项式时间约化。

注意，如果 X 通过 f(x) 在多项式时间内可归结为 Y，那么用于确定 Y 中成员资格的有效算法 A 也将产生用于确定 X 中成员资格的有效算法，如下所示：（i）对于输入 x，计算 f(x)；（ii）使用 A 确定 f(x) 是否∈Y，如果是则接受，如果不是则拒绝。

很容易看出 ≤P 是自反关系。由于两个多项式时间可计算函数的组合也是多项式时间可计算的，因此 ≤P 也是传递的。我们还说如果 Y∈C 且 X≤PY 意味着 X∈C，则类 C 在 ≤P 下封闭。还很容易看出，类 P、NP、PSPACE、EXP、NEXP 和 EXPSPACE 在这个关系下是封闭的。[16]如果对于所有 X∈C，X≤PY，则称问题 Y 对于类 C 来说是困难的。最后，如果 Y 对于 C 来说既是困难的又是 C 的成员，则称 Y 对于 C 来说是完全的。

自 20 世纪 70 年代中期以来，复杂性理论研究的主要重点一直是研究对于 NP 类来说是完全的问题，即所谓的 NP 完全问题。此类问题的一个典型例子是 N 的停机问题的时间受限变体（其无界确定性版本也是可计算性理论中的典型图灵和多一完全问题）：

BHP 给定非确定性图灵机 N∈N 的索引、输入 x 和表示为字符串 1t 的时间限制 t，N 是否在 t 步内接受 x？

显然，BHP 属于 NP，因为在输入 ⟨⌜N⌝,x,1t⟩ 时，一个高效的通用非确定性机器可以在 |x| 和 t 的时间多项式中确定 N 是否接受 x。为了说明 BHP 对于 NP 来说是困难的，请观察如果 Y∈NP，则 Y 对应于某个非确定性机器 N∈N 以多项式运行时间 p(n) 接受的字符串集。如果我们现在定义 f(x)=⟨⌜N⌝,x,1p(|x|)⟩，那么很容易看出 f(x) 是 Y 到 BHP 的多项式时间约化。