[ALDE 0x01] 复杂度类

在计算机科学中，问题被划分为被称为复杂度类（Complexity Classes）的类别。在复杂度理论中，复杂度类是一组具有相同资源约束（如时间或空间）的计算问题的集合。

复杂度理论涵盖了以下问题：

• 不能被计算机解决的问题（Undecidable Problems）
• 能在多项式时间（Polynomial Time）内解决的问题
• 需要指数时间（Exponential Time）甚至更多时间解决的问题

所谓多项式时间内可以解决的问题，是指这个问题的对应解法的时间复杂度可以表示为输入规模 $n$ 的某个常数次幂的多项式函数，例如 $O(1)$，$O(n)$，$O(n^3)$。而有些算法的时间复杂度，例如归并排序，可能表示为 $O(n\log n)$，这也算多项式时间算法，因为对于任意 $\epsilon > 0$，都有 $n\log n = O(n^{1+\epsilon})$，即它的增长速度不大于 $n$ 的常数次幂函数。

而不能在多项式时间内解决的问题，通常指指数级时间复杂度的问题，即时间复杂度式子中 $n$ 出现在指数位置，例如 $O(2^n)$，$O(n!)$。

接下来我们将介绍具体的复杂度类别。

P问题

P问题是指可在多项式时间内被解决的问题（Polynomial Time Problems），这类问题是可被确定性机器（Deterministic Machines），也就是我们的计算机，在多项式时间内解决的判定问题的集合。

所谓判定问题（Decision Problems），就是指能用 yes/no 回答的问题。虽然一些问题看起来不是判定问题，例如排序或优化问题，但它们能被转换为判定问题。例如排序问题就可以转化为：给定两个序列 $A$ 和 $B$，问 $B$ 是否是 $A$ 的一个有序排列？做这种问题的转换，是为了统一问题的表示形式，方便理论推导。

P问题的解通常被认为是“容易”找到的。P问题通常都是可解（Solvable）且可行（Tractable）的。所谓“可行”，是指这个问题在理论上可解，同时在实际中计算代价是可以接受的。而“不可行（Intractable）”则是指虽然这个问题存在理论上的解法，但在实践中对于大规模输入，计算代价过大以至于无法完成。

NP问题

NP问题（Non-deterministic Polynomial Time Problems）并不是指“Non-Polynomial”（非多项式）问题，而是指能被非确定性机器（Non-deterministic Machines）在多项式时间内解决的判定问题的集合。

由于非确定性机器是一个理论模型，在现实中我们通常使用等价的定义：NP问题是能在多项式时间内被“验证”的问题。

例：假设某公司共有 1000 名员工，每位员工拥有唯一的员工 ID。公司现有 200 间可用房间。需从中选取 200 名员工进行配对，但公司 CEO 掌握着部分员工因个人原因无法在同一房间工作的信息（即存在冲突约束）。问：是否存在一种合法的配对方案？

上面的例子是一个典型的 NP 问题。想从头找到它的解可能很难（可能需要指数级搜索），但验证解的正确性却很简单：如果有人给你一份名单，你只需要检查这 200 对员工是否都没有冲突即可，这是多项式时间内即可的。

为了与下面要提到的 Co-NP 问题做区分，这里必须谈到 NP 问题的另一种定义：如果一个问题的 yes 实例的解法可以在多项式时间内被快速验证，则该问题属于 NP 问题。什么叫“问题的 yes 实例”？首先，什么叫做问题的实例？复杂度理论讨论的都是问题的大类，例如我们说 SAT 问题是 NP 问题，这没问题；但如果我给你一个具体的问题，比如“布尔表达式 $A \land \lnot A$ 是不是可满足的？”，这个问题是 NP 问题吗？注意没有这种说法，这个问题是 SAT 问题的一个实例，而且从这个布尔表达式的结构可以看出它的答案肯定为 no，所以这个问题是 SAT 问题的一个 no 实例。NP 问题要求，对于问题的 yes 实例，肯定存在一个证据能证明它是 yes。以 SAT 问题的 yes 实例为例，我们肯定能找到一组赋值，使给出的布尔表达式满足，这样就证明了答案为 yes；但是对于它的 no 实例，我们无法通过单单举一组赋值来证明它的答案是 no，而是必须穷举所有可能性，显然我们无法在多项式时间内穷举所有情况，验证 no 实例的答案是否真的为 no。NP 问题只对 yes 实例做出了限制，而没有对 no 实例做出要求，之后要提到的 Co-NP 问题则正好相反。

需要注意 NP 问题的全称是 Non-deterministic Polynomial Time Problems，显然 P 问题由于更加简单，所以也是一种 NP 问题，因此存在 $\text{P} \subseteq \text{NP}$。理想中，我们当然都希望所有问题都能在多项式时间内解决，即去证明 $\text{P=NP}$，但可惜目前这还是一个尚未被证明的千禧难题。注意不能把 $\text{P} \subseteq \text{NP}$ 写成 $\text{P} \subset \text{NP}$，因为当前也没有证明出 $\text{P} \neq \text{NP}$，因此不确定 $\text{P}$ 是不是 $\text{NP}$ 的真子集。常见的 NP 问题有 SAT 问题、哈密顿回路问题、图着色问题等。

Co-NP问题

Co-NP问题是NP问题的补问题（The Complement of NP）。

我们回顾一下 NP 问题。在 NP 问题中，我们关注的是问题的 yes 实例：如果一个问题实例的答案是 yes，那么这里肯定存在一个证据可以快速验证它。但是，对于 no 实例，NP 问题没有做出限制。Co-NP 问题则相反：如果一个问题实例的答案是 no，存在一个方法可以在多项式时间内验证它到底是不是 no。

我们以 SAT 问题引出 Co-NP 问题的定义。SAT 问题是指：给定一个布尔表达式，问这个表达式是否是可满足的（即是否存在一组赋值使其为真）。

• 当 SAT 问题的解为 yes 时，我们只需要展示出一组赋值即可，验证它是多项式时间的。所以 SAT $\in$ NP。
• 当 SAT 问题的解为 no 时（即表达式无法被满足），我们要想证明它是 no，似乎只能穷举每一种赋值，证明它们都不行。这意味着 SAT 问题的 no 实例很难被快速验证。

因此，SAT 问题属于 NP，但目前普遍认为它不属于 Co-NP（尚未证明 $\text{SAT}\in\text{Co-NP}$）。

然而，SAT 问题的补问题，即 UNSAT 问题，却是 Co-NP 问题。UNSAT 问题的表述为“给定一个布尔表达式，判断这个表达式是否是不可满足的”。

• 当 UNSAT 问题的解为 no 时（即它是可满足的），我们只需要给出一个满足的赋值，就能证明它“不”是不可满足的。这意味着 no 实例好验证。
• 根据定义，no 实例好验证的问题，其补问题（yes 实例好验证）就是 NP。所以 UNSAT 的补问题（SAT）是 NP，那么 UNSAT 本身就是 Co-NP。

由上我们可以得到结论：如果一个问题 $L$ 属于 NP，那么它的补问题 $\overline{L}$ 属于 Co-NP。

值得注意的是，Co-NP 问题是 NP 问题的补问题集合，而不是补集！$\text{NP} \cap \text{Co-NP}$ 可能不为空。一个例子就是素数的判定问题（PRIMES）：给定一个数，判定这个数是否为素数。这既属于 NP，也属于 Co-NP。事实上，后来证明 PRIMES 判定问题属于 P。

另外，如果有一天证明了 SAT 问题也是 Co-NP 问题（即存在快速验证“不可满足”的方法），那么就意味着 $\text{NP} = \text{Co-NP}$。这是复杂度理论中的另一个重要猜想。

NP-hard问题

NP-hard问题（NP-困难问题）是指比 NP 问题中最难的问题还要难（或至少一样难）的问题的集合。它们不一定是 NP 问题。

NP 问题中所有问题都可以多项式时间归约（Polynomial-time Reduce）为 NP-hard 问题。这意味着，如果某个 NP-hard 问题能在多项式时间内解决，那么所有 NP 问题也都能在多项式时间内解决，从而证明 $\text{P=NP}$。

形式化定义：假设对于任意问题 $L \in \text{NP}$，都存在一个多项式时间归约算法，将 $L$ 转化求解问题 $A$，那么问题 $A$ 就是 NP-hard 问题。

NP-hard 问题未必是判定问题，它可以是优化问题。举个例子，经典的 TSP 问题（旅行商问题）：

• 判定版本：“是否存在一条长度不超过 $k$ 的巡回路径？” 这是 NP 问题。
• 优化版本：“求一条最短的巡回路径。” 这个问题比判定版本更难或至少一样难。因为如果你能解出优化版本，你就自动解出了判定版本（只需看最短路径是否 $\le k$）。因此，TSP 的优化版本是 NP-hard 问题。

对于 NP-hard 问题，由于通常无法在多项式时间内找到精确解（除非 $\text{P=NP}$），我们往往使用近似算法、启发式算法来寻找次优解。常见的 NP-hard 问题有停机问题（这是不可判定的，当然也是 NP-hard）、优化版 TSP 等。

NP-complete问题

NP-complete问题（NP-完全问题，简称 NPC 问题）是 NP 问题中最难的那一部分。

一个问题 $L$ 被称为 NPC 问题，必须同时满足两个条件：

1. $L \in \text{NP}$（它本身是一个 NP 问题，解易于验证）。
2. $L \in \text{NP-hard}$（所有 NP 问题都能归约到它）。

为什么要区分 NPC 问题？NPC 问题处于 P、NP 和 NP-hard 的交汇点，具有重要意义：

1. 统一了问题的难度：如果你解决了任意一个 NPC 问题（找到了多项式时间算法），你就解决了所有的 NP 问题。
2. 验证简单：因为属于 NP，yes 实例容易被验证，这使得它们适合用 SAT/SMT求解器处理。
3. 转化的桥梁：证明一个新问题是 NPC 的标准方法是：先证明它是 NP 的，再证明一个已知的 NPC 问题能归约到它。

关于 $\text{P}$ 与 $\text{NP}$ 的关系，最关键的推论是：如果存在一个 NPC 问题属于 P（即 $\text{NPC} \cap \text{P} \neq \varnothing$），那么 $\text{P} = \text{NP}$。

反之，如果 $\text{P} \neq \text{NP}$（这是目前主流的猜想），那么 NPC 问题就是那些虽然解容易验证，但根本不存在多项式时间求解算法的问题。我们只能对它们使用指数级时间的搜索算法或近似算法。

一件有意思的事情是：$\text{NP=NPC}\Leftrightarrow\text{P=NP}$。解释：如果 $\text{NP=NPC}$，又 $\text{P}\subseteq\text{NP}$，有 $\text{P}\subseteq\text{NPC}$，说明存在某个 NP-complete 问题可以在多项式时间内被解决，那么由于所有 NP 问题都可以规约到该问题，就可以推出所有 NP 问题都可以在多项式时间内解决，即 P = NP。另一方面，如果 P = NP，那么所有 NP 问题都可以在多项式时间内解决，从而每一个 NP 问题都同时满足“属于 NP”与“NP-hard”，因此 NP = NPC。

第一个被证明是 NPC 的问题是 SAT 问题（库克-列文定理）。

证明题

旅行商问题（TSP）：给定个无向完全图 $G=(V,E)$ 和正数 $K$，每一对结点 $(v_{i},v_{j})$ 之间有一个非负距离值 $d(v_{i},v_{j})$，请问图中是否包含一条经过所有结点 $v_{1},v_{2},\dots,v_{n}$ 一次并且总距离不超过 $K$ 的简单回路？

哈密顿回路问题（HC）：给定一个无向图 $G=(V,E)$，请问图中是否包含一条经过所有结点 $v_{1},v_{2},\dots,v_{n}$ 一次的简单回路？

已知哈密顿回路问题是 NP 完全的，请证明旅行商问题也是 NP 完全的。

要证明旅行商问题是 NP 完全的，需要证明旅行商问题既是 NP 问题，又是 NP-hard 问题。

下面证明旅行商问题属于 NP 问题：

旅行商问题属于 NP 问题，因为如果给出图中的一条路径 $v_{1},v_{2},\dots,v_{n}$，我们可以在多项式时间内验证：

1. 路径合法性验证：验证路径是否合法，即对于路径中每对相邻节点 $v_{i},v_{j}$，是否都存在 $\langle v_{i},v_{j} \rangle \in E$。
2. 回路验证：验证路径是否是回路，只需验证 $\langle v_{1},v_{n} \rangle$ 是否存在于 $E$ 中。
3. 节点全覆盖验证：路径是否覆盖了图中全部节点，只需与原图中节点进行对比。
4. 简单路径验证：路径是否是简单路径，只需检查中途是否经过了重复节点。
5. 开销验证：路径开销是否小于等于 $K$，只需累计所有路径开销即可。

输入路径的长度为 $n$，要完成以上验证，只需扫描路径一遍，时间复杂度为 $O(n)$，相对于输入规模而言是多项式时间。因此，旅行商问题属于 NP 问题。

下面证明旅行商问题属于 NP-hard 问题：

令哈密顿回路问题中输入的无向图为 $G^{\prime}=(V^{\prime},E^{\prime})$。将一个哈密顿回路问题的实例规约到一个旅行商问题的实例：

1. 图 $G$：令 $G=(V,E)$，其中 $V=V^{\prime}$，$E=\{ \langle v_{i},v_{j} \rangle \mid \forall v_{i},v_{j} \in V^{\prime} \land i \neq j \}$
2. 距离 $d$：$\forall e (e \in E \land e \notin E^{\prime} \to d(e)=2)$，$\forall e (e \in E \land e \in E^{\prime} \to d(e)=1)$。
3. 正数 $K$：令 $K=n$。

现在需要证明，哈密顿回路存在，当且仅当旅行商问题有解。

• 正向：如果 $G^{\prime}$ 中哈密顿回路存在，那就是存在一条经过所有结点 $v_{1},v_{2},\dots,v_{n}$ 一次的简单回路，由于 $V=V^{\prime}$，$E^{\prime} \subseteq E$，因此这条路径也是 $G$ 中的一条合法路径，且刚刚好经过 $G$ 中所有结点一次。又由于 $\forall e (e \in E \land e \in E^{\prime} \to d(e)=1)$，所以这条路径的开销为 $n$，不超过上限 $K=n$，因此，它也是旅行商问题的解。

• 反向：如果 $G$ 下的旅行商问题有解，则说明在图 $G$ 中存在一条经过所有结点 $v_{1},v_{2},\dots,v_{n}$ 一次并且总距离不超过 $n$ 的简单回路，并且由于对于所有在 $E$ 中而不在 $E^{\prime}$ 中的边，它们的距离都是 2，而路径开销又不能超过 $n$，所以绝不可能出现在这条路径中，即，所给路径必定是存在于 $G^{\prime}$ 中的合法路径。因此，旅行商问题的解必定是 $G^{\prime}$ 中的哈密顿回路。

综上所述，旅行商问题与哈密顿回路问题等价。

由于上述规约过程可以在多项式时间内完成，且哈密顿回路问题为 NP 完全问题，所以旅行商问题为 NP-hard 问题；同时，又因为旅行商问题是 NP 问题，所以，旅行商问题是 NP 完全的。

---

参考链接：P, NP, CoNP, NP hard and NP complete | Complexity Classes