如何证明一个问题属于 NP-Complete

1. 简介

目前尚无确凿证据证明 $\mathcal{P} = \mathcal{NP}$ 是否成立。但大多数研究者倾向于答案是否定的，即 $\mathcal{P} \neq \mathcal{NP}$ 。

本文假设 $\mathcal{P} \neq \mathcal{NP}$ ，我们将学习如何证明一个问题是 $\mathcal{NP}$ -Complete（NP-Complete）。我们还将使用一些真实算法问题来演示其 NP-Complete 性质的证明过程。

我们也会使用 Big-O 表示法来描述时间复杂度。

2. NP-Hard 与 NP-Complete 问题

我们先来对 决策问题（Decision Problems）进行分类 —— 即那些答案为“是”或“否”的问题。

2.1 P 与 NP

P 类问题：能在多项式时间内求解的问题。
NP 类问题：能在非确定性多项式时间内求解的问题。通俗地说，这类问题通常被认为是“困难”的，但我们无法在多项式时间内求解。不过它们的“运行时间”可能仍是多项式级别的。

2.2 归约（Reduction）

✅ 归约是指将问题 X 的输入转换为问题 Y 的输入，记作 $\mathcal{X} \leqslant_{p} \mathcal{Y}$ ，其中转换过程本身是一个多项式时间算法。

⚠️ 关键点：

归约是可传递的：如果 $\mathcal{A} \leqslant_{p} \mathcal{B}$ 且 $\mathcal{B} \leqslant_{p} \mathcal{C}$ ，那么 $\mathcal{A} \leqslant_{p} \mathcal{C}$ 。
归约保持“是”与“否”输入的对应关系。

2.3 NP-Hard

✅ 一个问题是 NP-Hard，如果所有 NP 中的问题都能归约到它。这意味着它至少与 NP 中的问题一样难，甚至更难。但 NP-Hard 问题不一定属于 NP。

2.4 NP-Complete

✅ 一个问题是 NP-Complete，如果它同时满足两个条件：

属于 NP；
所有 NP 中的问题都能归约到它。

⚠️ 所有 NP-Complete 问题都是 NP-Hard，但并非所有 NP-Hard 问题都是 NP-Complete。例如，停机问题（Halting Problem） 是 NP-Hard 但不属于 NP。

3. 证明问题为 NP-Complete 的步骤

要证明一个问题是 NP-Complete，我们需要证明它：

属于 NP；
是 NP-Hard。

3.1 如何证明问题属于 NP？

✅ 使用“证书验证”策略：

证书（Certificate）：即问题的答案（如一个解）。
验证器（Verifier）：一个多项式时间算法，用于验证该解是否有效。

示例：哈密顿回路问题

证书：顶点顺序（一个可能的哈密顿回路）。
验证器：遍历该路径，检查是否每个顶点只访问一次且构成回路。
时间复杂度：线性时间。

因此，哈密顿回路问题属于 NP。

3.2 如何证明问题属于 NP-Hard？

✅ 选择一个已知的 NP-Hard 或 NP-Complete 问题，将其归约到我们的问题。

⚠️ 注意：

由于归约具有传递性，只需归约一个已知的 NP-Hard 问题即可；
保证归约过程保持“是”与“否”输入的对应关系。

3.3 证明策略流程图

graph TD
    A[问题属于NP?] -->|是| B[问题属于NP-Hard?]
    B -->|是| C[NP-Complete]
    A -->|否| D[不是NP-Complete]

4. 3SAT → 4SAT 归约示例

4.1 4SAT 问题定义

✅ 4SAT 问题是：给定一个布尔公式，其中每个子句包含 4 个文字（变量或其否定），是否存在一个变量赋值使得所有子句都被满足？

4.2 4SAT 属于 NP

证书：变量赋值。
验证器：遍历每个子句检查是否满足。
时间复杂度：线性时间。

✅ 所以 4SAT 属于 NP。

4.3 3SAT 归约到 4SAT

✅ 选择 3SAT（已知是 NP-Complete）归约到 4SAT。

归约方法：

将每个 3SAT 子句 $(x \vee y \vee z)$ 转换为两个 4SAT 子句：

(x \vee y \vee z) \rightarrow (x \vee y \vee z \vee h) \wedge (x \vee y \vee z \vee \neg h)

其中 h 是新增的变量。

正确性分析：

如果 3SAT 子句满足，无论 h 是 true 还是 false，对应的两个 4SAT 子句都满足；
如果两个 4SAT 子句都满足，说明原 3SAT 子句也必须满足。

✅ 归约过程可在多项式时间内完成，因此 4SAT 是 NP-Hard。

✅ 综上，4SAT 是 NP-Complete。

5. 3SAT → 独立集（Independent Set）归约示例

5.1 独立集问题定义

✅ 在图论中，独立集（Independent Set）问题是：给定一个图和整数 k，是否存在一个大小为 k 的顶点集合，使得集合中任意两顶点之间没有边相连。

5.2 独立集属于 NP

证书：一个大小为 k 的顶点集合。
验证器：检查集合中任意两个顶点是否有边相连。
时间复杂度：多项式时间。

✅ 所以独立集问题属于 NP。

5.3 3SAT 归约到独立集

✅ 构造一个图：

每个子句构造一个三角形（3 个顶点）；
每个顶点代表一个文字（变量或其否定）；
如果两个顶点互为否定（如 x 和 ¬x），则添加一条边。

示例：

3SAT 公式：

(x_1 \vee \neg x_3 \vee \neg x_4) \wedge (\neg x_2 \vee x_3 \vee x_4) \wedge (\neg x_1 \vee x_2 \vee x_3)

构造的图如下（图略）：

✅ 如果公式可满足，则每个子句中至少有一个变量为 true，我们可以从每个三角形中选出一个 true 的顶点组成独立集。

✅ 如果图中存在大小为 k 的独立集，则说明公式可满足。

✅ 归约过程可在多项式时间内完成，因此独立集是 NP-Hard。

✅ 综上，独立集是 NP-Complete。

6. 总结

本文介绍了复杂度理论中的几个核心概念：

概念	含义
P	多项式时间可解
NP	多项式时间可验证
NP-Hard	所有 NP 问题都可归约到它
NP-Complete	同时属于 NP 且 NP-Hard

✅ 证明 NP-Complete 的核心步骤：

证明问题属于 NP；
证明问题属于 NP-Hard（通过归约）。

✅ 示例问题：

4SAT
独立集问题

通过这两个例子，我们展示了如何使用归约法来证明问题的 NP-Completeness。

Persistence

REST

Security