组合问题中的可归约性(Part I)

Author: Richard Karp(1972)

Abstract

有大量的计算问题涉及到确定无向图、有向图、整数、整数数组、有限集的有限族、布尔公式和其他可数域的元素的性质。通过将这些域简单地编码成有限的字母表上的单词集合，就可以将这些问题转化为语言识别问题，并探究它们的计算复杂度。当一个求解该问题的算法能在关于输入长度的多项式步内结束，那么我们有理由认为这个问题已经圆满地解决了。我们证明了大量经典的、未解决的覆盖问题、匹配问题、背包问题、路径问题、赋值问题和排序问题是等价的——它们要么都具有多项式时间为界的算法，要么都没有。

Introduction

目前所有已知的，用于计算图的色数、判断图是否有 Hamilton 回路或解决 0-1 整数规划的算法，都需要用到组合搜索，最坏情况下时间复杂度是指数级的。在本文中，我们给出了一些定理，它们有力地显示（但并不绝对地证明）了这些问题以及其他许多问题，将永远是棘手的。

我们对多项式时间复杂度的算法的存在非常感兴趣。我们展示了一类著名的组合问题（包括上面提到的那些），它们是等价的——这也就是说，对它们中的任何一个问题的多项式复杂度的算法，都能有效地生成一个对所有问题多项式复杂度的算法。我们还证明了，如果这些问题确实具有多项式有界算法，那么一个出人意料地宽泛的类中的所有问题（粗略地说，可由多项式深度的回溯搜索解决的一类问题）都具有多项式时间的算法。

下面是对论文内容的简要总结。为了使论述明晰，我们用于识别语言的技术是单磁带图灵机，不过其实使用其他任何种类的抽象计算模型都会得出一致的结论。设 $\Sigma^*$ 为所有由 $0$ 和 $1$ 组成的有限二进制字符串的集合，则 $\Sigma^*$ 的一个子集称为一种语言。设 $\mathcal{P}$ 为能在多项式时间内被确定性单磁带图灵机识别的语言的集合，而 $\mathcal{NP}$ 为能在多项式时间内被非确定性单磁带图灵机识别的语言的集合。设 $\Pi$ 为单磁带图灵机可在多项式时间内计算的函数 $f:\Sigma^* \to \Sigma^*$ 的集合。设 $L, \ M$ 为语言。我们称 $L \propto M$ （ $L$ 可规约为 $M$ ）若 $\exists f \in \Pi,\quad f(x) \in M \iff x \in L$ 。若 $L \propto M \ \wedge \ M \propto L$ ，则称 $L$ 和 $M$ 等价。若 $M \in \mathcal{P} \ \wedge \ L \propto M$ ，则 $L \in \mathcal{P}$ 。称 L 为(多项式)完全的，若 $L \in \mathcal{NP}$ ，且 $\mathcal{NP}$ 中所有语言均可规约为 $L$ 。完全的语言要么全部在 $\mathcal{P}$ 中，要么全部不在；前者成立当且仅当 $\mathcal{P}= \mathcal{NP}$ 。

本文的主要贡献在于证明了数学规划、图论、组合数学、计算逻辑和交换理论等领域中出现的大量经典难计算问题，在自然表达为语言识别问题时是完全的（因此是等价的）。

本文受到 Stephen Cook 工作(1971)的启发，基于他论文中提出的一个重要定理。作者还要感谢 Eugene Lawler 和 Robert Tarjan 所作的重大贡献。

The Class P

有大量的计算问题涉及到确定图、有向图、整数、整数数组、有限集的有限族、布尔公式和其他可数域的元素的性质。当且仅当存在多项式时间复杂度的算法时，一个问题才会被认为是“容易解的”，这个合理的假设最初被杰克·埃德蒙兹(1965)赞成采纳于图论和整数规划问题上，现在被广泛接受的。在本节中，我们介绍并开始研究这类多项式时间内可解决的问题。

首先，我们给出一个关于“确定性算法”的非常具有一般性的定义，计算一个函数 $D \to R$ ，其中 $D,\ R$ 均为可数集。

设 $A$ 是一个有限的字符表， $A^*$ 为由 $A$ 中元素组成的有限长度的字符串组成的集合。对于 $x \in A^*$ ，设 $lg(x)$ 为 $x$ 的长度。

确定性算法 $\mathcal{A}$ 由如下五条规定：
1. 可数集定义域 $D$ ；
2. 可数集值域 $R$ ；
3. 有限字符表 $\Delta$ ，且 $\Delta^* \cap R = \varnothing$ ；
4. 编码函数 $E:D\to \Delta^*$ ；
5. 转移函数 $\tau:\Delta^*\to \Delta^* \cup R$ ；

对于每一个输入 $x \in D$ ， $\mathcal{A}$ 的计算为一个独一无二的序列 $y_1, y_2,\cdots$ ，其中 $y_1 = E(x)$ ，而 $y_{i+1} = \tau(y_i),\quad i = 1,2,\cdots$ ，如果这个序列是有限的，且结尾是 $y_k$ ，那么 $y_k \in R$ 。任何一个作为计算中的元素出现的字符串都称为瞬时（instantaneous）描述。如果对于输入 $x$ ，算法 $\mathcal{A}$ （步骤）有限且结束长度为 $t(x)$ ，那么称 $t(x)$ 为 $\mathcal{A}$ 输入 $x$ 时的运行时长。如果 $\mathcal{A}$ 的所有计算都是有限的，那么它就是可终止的（terminating）。可终止的算法 $\mathcal{A}$ 计算函数 $f_{\mathcal{A}}: D \to R$ ，使得 $f_{\mathcal{A}}(x)$ 是 $\mathcal{A}$ 输入 $x$ 时计算时（字符串序列）的最后一个元素。

如果 $R = \{Accept, Reject\}$ ，那么 $\mathcal{A}$ 称为识别算法。若一个识别算法的定义域 $D = \Sigma^*$ ，那么称之为字符串识别算法。若 $\mathcal{A}$ 是一个字符串识别算法，那么被 $\mathcal{A}$ 识别的语言组成集合 $\{x \in \Sigma^* | f_{\mathcal{A}}(x) = Accept\}$ 。如果 $D = R = \Sigma^*$ ，那么 $\mathcal{A}$ 称为字符串映射函数。当对于可终止算法 $\mathcal{A}$ 存在多项式 $p(\cdot)$ 使得 $\forall x \in \Sigma^*,\ t(x) \le p(lg(x))$ 时，其为多项式时间的算法。

要在实际环境中讨论算法，我们必须特化确定性算法的概念。将函数 $E$ 和 $\tau$ 限定为一些非常简单的类型，就能描述出各种著名的字符串识别算法类（马尔科夫算法类、单磁带图灵机类，多磁带和多磁头图灵机类，随机存取计算机类等）。这些标准的定义【Hopcroft & Ullman 1969】这里将不再重复。到目前为止，可以看到许多这样的算法类在识别语言的能力上显然是等价的；对于每一个算法类，被其识别的语言类为递归语言。定义变化时这种不变性，是递归性（recursiveness）可以表述可判定性这一概念的部分证据。

能被多项式时间内运行的字符串识别算法所识别的语言类别，在算法类别的大范围变化下也是不变的。例如，任何由多磁头或多磁带图灵机在时间 $p(\cdot)$ 上可识别的语言，都可以由单磁带图灵机在时间 $p^2(\cdot)$ 上可识别。因此，单磁带图灵机在多项式时间内能识别的语言类，与看起来更强大的多磁头或多磁带图灵机识别的语言类是相同的。这个结论同样适用于随机存取计算机。

【Definition ①】 $\mathcal{P}$ 是可以在多项式时间内被单磁带图灵机识别的语言类。
【Definition ②】 $\Pi$ 是可以在多项式时间内由单磁带图灵机执行的 $\Sigma^* \to \Sigma^*$ 函数类。

读者如果将 $\mathcal{P}$ 视为数字计算机（假设其存储空间无限）可识别的语言，或将 $\Pi$ 视为在数字计算机上可在多项式时间内进行的字符串映射函数，也没什么错。

【Remark】若 $f: \Sigma^*\to \Sigma^* \in \Pi$ ，那么存在多项式 $p(\cdot)$ 使得 $lg(f(x)) \le p(lg(x))$ 。

接下来，我们将介绍一个“可归约性”的定义，这在本文中至关重要。

【Definition ③】设 $L, M$ 为语言，若 $\exists f \in \Pi$ ，使得 $f(x) \in M \iff x \in L$ ，那么称 $L$ 可规约于 $M$ ，记作 $L \propto M$ 。

【Lemma ①】若 $L \propto M$ ，且 $M \in \mathcal{P}$ ，则 $L \in \mathcal{P}$ 。

证明：如下给出识别字符串 $x \in L$ 与否的多项式时间的算法
计算 $f(x)$ ，然后判断 $f(x) \in M$ 是否成立。
该算法分为两步，每一步都是多项式时间内完成的，因而整体为多项式时间的算法。

我们对识别除 $\Sigma^*$ 以外的可数域子集的难度感兴趣。给定一个可数域 $D$ ，一般自然存在一个一对一的编码 $e:D \to \Sigma^*$ 。比如，我们可以用 $0$ 和 $1$ 组成的字符串来二进制表示一个整数，用一个一维数组表示一列整数，用一个矩阵表示一列一维数组，等等。有一些标准的方法，可以把列表编码成有限字母上的字符串，也可以把任意有限字母上的字符串编码成 $0$ 和 $1$ 的字符串。给定编码方式 $e:D\to \Sigma^*$ ，当 $T \subseteq D$ 满足 $e(T)\in \mathcal{P}$ ，我们称 $T$ 可以在多项式时间内被识别；对于 $T \subseteq D_1 , U \subseteq D_2$ ，给定 $e_1:D_1\to \Sigma^*, e_2:D_2 \to \Sigma^*$ ，若 $e_1(T) \propto e_2(U)$ ，则 $T \propto U$ 。

通常，对于一个给定的域，有许多可能的自然编码。例如，图的表示形式可以是邻接矩阵、关联矩阵或边对应的无序节点对列表。即便给定其中一种表示形式，表示的格式和标点符号也仍然存在有很多可能的选择。幸运的是，给定问题的两种“合理”编码 $e_0, e_1$ 几乎显而易见地是等价的；也就是说， $e_0(S)\in \mathcal{P} \iff e_1(S) \in \mathcal{P}$ 。一个重要的例外是正整数的表示：我们规定正整数的编码是用二元（binary）表示，而不是一元（unary）表示。考虑到多项式时间内的可识别性的不变性和合理编码下的可约性，我们可以直接在问题原始的域中讨论问题，而不需要在 $\Sigma^*$ 中特别指定编码。

我们列出一些多项式时间内可解的问题来作为本节的结尾。在下一节中，我们将研究这些问题的一些密切相关的，但不知道在多项式时间内是否是可解的问题。我们使用的符号见附录一。

每个问题都会给出其定义域的元素的一般表示（在“INPUT”下）和输入被 $Accept$ 需要满足的条件（在“PROPERTY”下）。

【SATISFIABILITY WITH AT MOST 2 LITERALS PER CLAUSE】布尔满足性问题 [Cook 1971]
INPUT：子句 $C_1, C_2, \cdots, C_p$ ，每一个都有两个字面值。
PROPERTY：每个输入子句的连接方式是可满足的；即存在 $S \subseteq \left\{x_1,\cdots,x_n,\bar{x}_1,\cdots,\bar{x}_n \right\}$ 使得： $S$ 不能含有一对相反的字面值（翻译注：即不能同时含有 $x_i, \bar{x}_i, \quad i = 1, 2, \cdots n$ ）且 $S \cap C_k \ne \varnothing,\quad k = 1,2,\cdots, p$ 。

【MINIMUM SPANNING TREE】最小生成树问题 [Kruskal 1956]
INPUT： $G, W,w$ 。
PROPERTY：存在一个生成树，总权值小于等于 $W$ 。

【SHORTEST PATH】最短路径问题 [Dijkstra 1959]
INPUT： $G,W,w,s,t$ 。
PROPERTY： $s, t$ 之间有路径小于权值小于 $W$ 。

【MINIMUM CUT】最小割集问题 [Edmonds & Karp 1972]
INPUT： $G,W,w,s,t$ 。
PROPERTY：将 $s$ 和 $t$ 分割开的割集总权值小于等于 $W$ 。

【ARC COVER】最小边覆盖问题 [Edmonds 1965]
INPUT： $G,k$ 。
PROPERTY：存在边覆盖 $Y \subseteq E$ ， $|Y| \le k$ 。

【ARC DELETE】边删除问题
INPUT： $G,k$ 。
PROPERTY：存在包含 $k$ 条边的边集，将它们从图中删除后得到 $G’$ ，使得 $G’$ 中不存在环路。

【BIPARTITE MATCHING】二部图匹配问题 [Hall 1948]
INPUT： $S \subseteq Z_p \times Z_p$ 。
PROPERTY： $S$ 有 $p$ 个元素，且任意两个元素不相等。

【SEQUENCING WITH DEADLINES】 ~~一串串的DDL~~ 最优排序问题
INPUT：工作时长 $(T_1,\cdots, T_n)\in \mathbb{Z}^n$ ，工作截止时间 $(D_1, \cdots, D_n)\in \mathbb{Z}^n$ ， $k$ 。
PROPERTY：从 $0$ 时刻开始，安排工作的顺序，存在一种工作顺序安排使得超过截止时间的工作不超过 $k$ 个。

【SOLVABILITY OF LINEAR EQUATIONS】线性方程的可解性
INPUT： $(c_{ij}),(a_i)$ 。
PROPERTY：存在向量 $(y_j)$ 使得对任意 $i$ ， $\sum_{j}c_{ij}y_j = a_i$ 成立。

组合问题中的可归约性(Part I)

Abstract

Introduction

The Class P

推荐阅读更多精彩内容