计算复杂性理论（四）

由于 BHP 是 NP 完全的，从 NP 在 ≤P 下的闭包可知，仅当 P=NP 时，该问题才属于 P。由于人们普遍认为事实并非如此，这提供了一些证据表明 BHP 本质上是一个困难的计算问题。但由于 BHP 与计算模型 N 本身密切相关，这似乎没有多大实际意义。因此，更令人感兴趣的是，许多看似不相关的问题源自许多不同的数学领域，也是 NP 完全的。

证明给定问题 X 是 NP 难的一种方法是证明 BHP 可以归结为它。但由于大多数数学上自然的问题与图灵机无关，因此这种归结的存在并不明显。在 NP 完全性研究之初，Cook (1971) 和 Levin (1973) 就规避了这个问题，他们独立证明了以下内容：[17]

定理 3.4 SAT 是 NP 完全的。

我们已经看到 SAT 属于 NP。为了证明定理 3.4，只需证明所有问题 X∈NP 都可以在多项式时间内归结为 SAT。假设 X∈NP，则一定存在一个非确定性图灵机 N=⟨Q,Σ,Δ,s⟩ 以多项式时间复杂度 p(n) 接受 X。定理 3.4 的证明如下：对于 N 的所有长度为 n 的输入 x，我们可以构造一个命题公式 ϕN,x，当且仅当 N 在 p(n) 步内接受 x 时，该公式才是可满足的。[18]

尽管 SAT 仍然是一个关于特定逻辑系统的问题，但它比 BHP 更具组合性。鉴于此，定理 3.4 为证明许多其他问题为 NP 完全问题打开了大门，因为它表明 SAT 可以有效地归结为这些问题。例如，上面介绍的 TSP 问题和整数规划问题都是 NP 完全问题。以下是其他一些 NP 完全问题的示例：

3-SAT 给定一个 3-合取范式 (3-CNF) 中的命题公式 ϕ - 即 ϕ 是包含三个否定或非否定命题变量的析取子句的合取 - 是否存在令人满意的 ϕ 赋值？

汉密尔顿路径给定一个有限图 G=⟨V,E⟩，G 是否包含汉密尔顿路径（即访问每个顶点一次的路径）？

独立集 给定一个图 G=⟨V,E⟩ 和一个自然数 k≤|V|，是否存在一个顶点集 V′⊆V，其基数 ≥k，使得 V′ 中没有两个顶点通过边连接？

顶点覆盖 给定一个图 G=⟨V,E⟩ 和一个自然数 k≤|V|，是否存在一个顶点集 V′⊆V，其基数 ≤k，使得对于每条边 ⟨u,v⟩∈E，u 或 v 中至少有一个是 V′ 的成员？

集合覆盖 给定一个有限集 U、一个由 U 的子集组成的有限族 S 和一个自然数 k，是否存在一个子族 S′⊆S，其基数 ≤k，使得 ⋃S′=U？

Cook 的原始论文（Cook 1971）表明 3-SAT 问题是 NP 完全的。[19] 刚刚引用的其他例子取自 21 个问题列表（其中大多数之前已在其他情况下被确定），Karp（1972）已证明它们是 NP 完全的。显示这些问题的完整性所需的归约通常需要构建所谓的小工具 - 即一个问题实例的组成部分，可用于模拟另一个问题实例的组成部分。例如，为了了解如何将 3-SAT 简化为独立集，首先观察 3-CNF 公式的形式为

(ℓ11 ∨ℓ12 ∨ℓ23) ∧ (ℓ21 ∨ℓ22 ∨ℓ23) ∧… ∧ (ℓn1 ∨ℓn2 ∨ℓn3)

其中每个 ℓij 都是文字 - 即对于某个命题变量 pk，ℓij=pk 或 ℓij=¬pk。这种形式的公式 ϕ 是可满足的，只要存在一个值满足所有 1≤i≤n 的文字 ℓi1、ℓi2 或 ℓi3 中的至少一个。另一方面，假设我们考虑图族 G，它可以按照图 3 所示的方式划分为 n 个不相交的三角形。很容易看出，这种图中任何大小为 n 的独立集都必须恰好包含 G 中每个三角形的一个顶点。这反过来又提出了使用这种形式的图作为表示 3-CNF 公式子句的小工具的想法。



图 3. 公式 (p1∨p2∨p3)∧(¬p1∨p2∨¬p3)∧(p1∨¬p2∨¬p3) 的图 Gϕ。

现在可以如下描述将 3-SAT 简化为 INDEPENDENT SET：

设 ϕ 为由 n 个子句组成的 3-CNF 公式，如上所示。

我们构造一个图 Gϕ=⟨V,E⟩，它由 n 个三角形 T1,…,Tn 组成，其中 Ti 的节点分别标有文字 ℓi1,ℓi2,ℓi3，构成 ϕ 的第 i 个子句。此外，G 包含一条边，连接每个三角形中与相反符号的文字相对应的节点，如图 3 所示。[20]

现在定义从 3-SAT 实例到 INDEPENDENT SET 实例的映射为 f(ϕ)=⟨Gϕ,n⟩。由于 Gϕ 包含 3n 个顶点（因此最多有 O(n2) 条边），显然 f(x) 可以在多项式时间内计算出来。要看出 f(ϕ) 是 3-SAT 到 INDEPENDENT SET 的约化，首先假设 v 是一个满足 [[ϕ]]v=1 的估值。那么对于 ϕ 的每个子句中至少一个文字，我们必须有 [[ℓij]]v=1。选取 ϕ 中每个三角形 Ti 中与该文字相对应的节点，从而在 Gϕ 中得到一个大小为 n 的独立集。相反，假设 V′⊆V 是 Gϕ 中大小为 n 的独立集。根据构造，V′ 在每个 Ti 中都恰好包含一个顶点。并且由于 Gϕ 中不同三角形中每对标有相反符号文字的节点之间存在一条边，因此 V′ 不能包含任何矛盾的文字。如果标记为 pi 的节点出现在 V′ 中，则设置 v(pi)=1，否则设置 v(pi)=0，这样可以构造出对 ϕ 的满意估值 v。

由于 ≤P 是传递的，因此将多项式时间归约组合在一起提供了另一种证明各种问题都是 NP 完全的方法。例如，TSP 的完整性最初由 Karp (1972) 通过一系列归约证明

SAT≤P3-SAT≤PINDEPENDENT SET≤PVERTEX COVER≤PHAMILTONIAN PATH≤PTSP。

因此，尽管上面列出的问题在涉及不同类型的数学对象（例如逻辑公式、图形、线性方程组等）的意义上看似无关，但它们是 NP 完全的事实可以表明它们都以与 BHP 相同的方式对 NP 具有计算通用性。[21]

从≤P的传递性还可以看出，即使一个NP完全问题存在多项式时间算法，也意味着所有NP问题都存在多项式时间算法。因此，这种算法的存在与人们为寻找特定NP完全问题（如整数规划或TSP）的有效解决方案所付出的巨大努力背道而驰。因此，这类问题被标准地视为NP中最困难的问题。

只要对开放问题1的回答是肯定的，即P⊊NP，NP完全问题就符合有效可判定问题的描述，这些问题本质上是困难的，正如第1节中描述的。然而，正如我们现在将要看到的，它们绝不是复杂性理论家研究的最难的问题。复杂性理论也不能进一步区分 P 内部或 P 与 NP 之间的问题的难度（假设后者为非空类）。

3.4 其他复杂性类别

3.4.1 NP 和 coNP

与非确定性图灵机模型 N 相比，确定性计算模型（如 T）的接受和拒绝约定是对称的。换句话说，对于确定性机器 T 来说，要接受或拒绝输入 x，存在单个停止计算 C0(x),…,Cn(x) 是必要且充分的。然后，机器的输出由 Cn(x) 是接受还是拒绝配置决定。由此可见，用该模型定义的复杂度类（如 P）在补函数下是封闭的，即，对于所有语言 X⊆{0,1}∗，X 属于 P 当且仅当它的补函数 ¯X=df{x∈{0,1}∗:x∉X} 也属于 P。[22] 如果我们将类 coC 定义为由补函数属于类 C 的问题组成，则 P=coP。

与此相反，没有先验保证用非确定性模型定义的类（如 NP）在补函数下是封闭的。考虑属于此类的 SAT 问题。¯SAT（即 SAT 的补函数）由一组不存在令人满意的估值的公式组成，即命题逻辑的矛盾公式。由此可知，ϕ∈¯SAT 当且仅当 ¬ϕ∈VALID——即有效命题公式集。由于这一观察结果提供了将 ¯SAT 简化为 VALID 的多项式时间简单方法，因此后者不仅是 coNP 的成员，而且对此类而言也是完备的。[23]

但请注意，为了证明 ϕ∈VALID，我们必须证明 ϕ 对所有赋值都为真。由于包含 n 个命题变量的公式存在 2n 个赋值，因此，通过可以实现为非确定性图灵机的算法（相对于上述接受和拒绝约定）在多项式时间内确定任意公式在 VALID 中的成员资格绝非显而易见。事实上，以下是当代复杂性理论中另一个尚未解决的基本问题：

开放问题 2 NP 和 coNP 类是否不同？

人们普遍认为，与开放问题 1 一样，开放问题 2 的答案也是肯定的。但请注意，如果任何 NP 完全问题都可以证明属于 coNP，那么 NP=coNP 也成立。[24] 这反过来表明，已知属于 NP∩coNP 类的问题不太可能是 NP 完全的（并且根据对称考虑，也不太可能是 coNP 完全的）。此类由那些拥有多项式大小的证书来证明成员资格和非成员资格的问题 X 组成。

很容易看出 NP∩coNP 包括 P 中的所有问题。但此类还包含一些目前尚不清楚是否可以判定的问题。一个重要的例子是 FACTORIZATION（如第 1.1 节所定义）。一方面，能整除 n 的数 1＜d≤m 可作为 ⟨n,m⟩ 在 FACTORIZATION 中成员资格的证明。另一方面，为了证明 ⟨n,m⟩ 在 ¯FACTORIZATION 中的成员资格，只需展示 n 的质因数分解，其中没有小于 m 的因子。这是因为质因数分解是唯一的（不同于例如在 VALIDITY 的情况下伪造估值），并且因为各个因子的素数可以通过 AKS 算法在多项式时间内验证。因此，FACTORIZATION 同时属于 NP 和 coNP。

与其他具有实际重要性的计算问题一样，人们已经投入了大量精力来寻找一种有效的 FACTORIZATION 算法。如果我们无法找到有效的分解算法确实表明该问题不在 P 中，那么对开放问题 2 的肯定回答将意味着存在一些自然数学问题，它们不是可判定的，但也不是 NP 完全的。这反过来表明，介于 P 和 NP 之间的问题的程度结构（假设此类非空）可能提供比 Cobham-Edmonds 论题单独提供的更细粒度的内在计算难度分析。[25]

3.4.2 多项式层次结构、多项式空间和指数时间

如果最初尝试找到一种有效算法来解决已知可判定的问题 X 失败，则一种常见的策略是尝试证明 X 是 NP 完全的。假设 P⊊NP，则根据 Cobham-Edmonds 论题，不存在解决 X 的可行算法。

尽管如此，使用离散数学的领域经常会产生可判定问题，这些问题被认为比 NP 完全问题困难得多。回想一下，根据定理 3.1，EXP 和 NEXP 类（即指数时间和非确定性指数时间）都适当地扩展了 P。因此，无论如何解决开放问题 1，这些类别的完全问题目前都可以归类为不可行的。这类问题包括一阶逻辑决策问题的几个子案例（将在第 4.2 节中讨论）以及本节中考虑的一些博弈论问题的版本。[26]

一个可能被适当地包含在 EXP 中的复杂性类，但仍包含许多在计算实践中出现的看似不可行的问题，那就是 PSPACE。可以使用量化布尔公式 [QBF] 的概念来表述 PSPACE 中问题的典型例子，即形式为 Q1xi…Qnxnψ 的语句，其中 Qi=∃ 或 ∀，ψ 是包含命题变量 x1,…,xn 的命题逻辑公式，这些变量被视为受这些量词的约束。如果当 Qixi 被解释为分配给 xi 的真值的存在量词或全称量词时，ψ 对于由相关量词前缀确定的所有估值都为真，则称 QBF 公式为真，例如∀x1∃x2(x1∨x2) 是一个真正的量化布尔公式，而 ∀x1∃x2∀x3((x1∨x2)∧x3) 不是。我们现在可以定义问题

TQBF  给定一个量化布尔公式 ϕ，ϕ 是否为真？

Stockmeyer 和 Meyer (1973) 证明了以下内容：

定理 3.5 TQBF 是 PSPACE 完全的。[27]

该结果表明，可以使用无限时间但可行内存空间解决的问题与可以通过在两种查询之间进行有限数量的交替来一步回答某些类型的存在性或通用查询的问题之间存在密切联系。这一观察结果可用于对我们考虑过的几种复杂性类别进行另一种表征。例如，回想一下，NP 可以非正式地描述为一组问题 X，通过提供适当类型的证书可以为其建立成员资格——例如，ϕ∈SAT 可以通过展示令人满意的评价来建立。类似地，coNP 也可以类似地描述为一组问题，通过存在这样的证书可以为其建立非成员资格——例如，ϕ∉VALID 也可以通过展示令人满意的评价来建立。

基于这些观察，不难证明以下内容：

命题 3.1 如果 {⟨x,y⟩∣R(x,y)}∈P，则称关系 R(x,y) 为多项式可判定的。

问题 X 属于 NP 范畴，仅当存在多项式可判定关系 R(x,y) 和多项式 p(x)，使得 x∈X 当且仅当 ∃y≤p(|x|)R(x,y)。

问题 X 属于 coNP 范畴，仅当存在多项式可判定关系 R(x,y) 和多项式 p(x)，使得 x∈X 当且仅当 ∀y≤p(|x|)R(x,y)。

命题 3.1 为基于计算问题的逻辑表示定义复杂性类的层次结构（即所谓的多项式层次结构 [PH]）提供了基础。我们首先将 ΔP0、ΣP0 和 ΠP0 定义为类 P 的替代名称，即 ΔP0=ΣP0=ΠP0=P。然后，我们将 ΣPn+1 定义为形式为 X={x∣∃y≤p(|x|)R(x,y)} 的问题类，其中 R(x,y)∈ΠPn，将 ΠPn+1 定义为形式为 X={x∣∀y≤q(|x|)S(x,y)} 的问题类，其中 S(x,y)∈ΣPn，p(n) 和 q(n) 均为多项式。ΔPn 是属于 ΣPn 和 ΠPn 的问题集。最后，将类 PH 定义为 ⋃k∈NΣPk。[28]

从命题 3.1 可知 ΣP1=NP 且 ΠP1=coNP。从前述定义还可看出，我们有图 4 所示的包含关系 ΣPn⊆ΔPn+1⊆ΣPn+1 和 ΠPn⊆ΔPn+1⊆ΠPn+1。也不难证明 PH⊆PSPACE。这些关系类似于可计算性理论中研究的算术层次结构中类似定义的 Σ0n 集和 Π0n 集之间的关系（例如，参见 Rogers 1987）。但是，虽然可以通过标准对角线论证证明算术层次结构不会崩溃，但以下问题也是目前尚未解决的基本重要问题：

开放问题 3

PH 是否是适当的层次结构 - 即对于所有 k，ΣPk⊊ΣPk+1 和 ΣPk≠ΠPk 是否如此？

PH 是否适当地包含在 PSPACE 中？



图 4。多项式层次结构。

为了更好地理解为什么开放问题 3a、b) 也有望得到肯定的答案，进一步探索 PSPACE 与 PH 在量词交替方面的表征之间的关系将很有用。为此，我们首先表明，TQBF 问题可以重新定义为一个叫做验证者的玩家与另一个叫做证伪者的玩家之间的博弈，验证者可以被认为是试图证明 QBF 公式 ϕ 为真，而证伪者可以被认为是试图证明 ϕ 不真。[29] 假设 ϕ 的形式为 ∃x1∀x2…Qnψ，ϕ 的验证博弈玩法定义如下：

•在第一轮中，验证者通过选择 v(x1) 的值来移动。

•在第二轮中，证伪者通过选择 v(x2) 的值来移动。

⋮

•在第 n 轮中，验证者或证伪者选择 v(xn) 的值，具体取决于 Qn=∃ 还是 ∀。

•如果 [[ϕ]]v=1，则验证者为赢家，如果 [[ϕ]]v=0，则证伪者为赢家。

在验证游戏中，验证者针对 ϕ 的获胜策略是针对证伪者所有可能的答复和反答复的一系列移动和反击，这保证验证者获胜。我们将决定验证者是否对 ϕ 具有这种获胜策略的问题称为 TWO PLAYER SAT。由于两位玩家的走法反映了 QBF 公式中 ∃ 和 ∀ 的解释，因此不难看出，只要 ϕ∈TQBF，ϕ∈TWO PLAYER SAT 也是成立的。并且对于任何具有 n 个初始量词的 QBF 公式 ϕ，我们可以通过根据需要穿插虚拟量词，有效地构造一个具有最多 2n 个所需交替形式量词的等价公式。因此，与 TQBF 一样，TWO PLAYER SAT 也是 PSPACE 完全的。

尽管 TWO PLAYER SAT 是根据一个非常简单的游戏来定义的，但对于各种熟悉的棋盘游戏的适当变体也可以获得类似的结果。例如，考虑围棋标准规则的以下变体：(i) 游戏在 n×n 的棋盘上进行； (ii) 比赛的获胜者是 n2 轮结束时拥有最多棋子的玩家。Lichtenstein 和 Sipser (1980) 证明了以下问题的 PSPACE 完备性：

GO

给定 n×n 围棋比赛中的棋盘位置，黑方（即先手的玩家）是否存在获胜策略？

对残局规则进行类似修改后，国际象棋（Fraenkel and Lichtenstein 1981）和跳棋（Robson 1984）也得到了类似的结果。[30]

这些游戏的共同点是，先手玩家的获胜策略的定义涉及存在量词和全称量词的交替，其方式类似于构成 PH 的类 ΣPn 和 ΠPn 的定义。考虑到这一点，假设我们将 TWO PLAYER SATn 定义为 TWO PLAYER SAT 的变体，其中 ϕ 中量词的交替次数最多为 n 次（因此，此类公式的所有游戏最多为 n 轮）。可以证明 TWO PLAYER SATn 对于多项式层次结构中的类 ΣPn 是完备的。但请注意，随着 n 值的增加，我们预计决定双人 SATn 的成员资格会变得更加困难，就像确定特定玩家在围棋或国际象棋越来越长的游戏中是否有制胜策略似乎变得更加困难一样。