1. 讲义 11B：复杂性复习 - 解答

这是讲义的标题和作者信息。“讲义 11B”表明这是系列讲义中的第11部分的B部分，通常A部分是问题，B部分是解答。“复杂性复习 - 解答”明确了这份文档的核心内容，即关于计算复杂性理论（Computational Complexity Theory）的复习题的官方解答。“William Pires”是这份讲义的作者。计算复杂性理论是理论计算机科学的核心分支，它研究计算问题根据其内在难度（需要多少计算资源）进行分类。

这个问题要求我们判断给出的四个函数增长率是否属于多项式级别。在计算复杂性理论中，一个函数 $f(n)$ 被认为是多项式的，如果它被一个多项式函数所界定，即存在一个常数 $c > 0$ 和一个常数 $k$，使得对于所有足够大的 $n$，$f(n) \le c \cdot n^k$。这个界定通常使用大O符号表示为 $f(n) = O(n^k)$。

1. $n \cdot \log(n)$: 这个函数增长得比 $n$ 快，但比 $n^2$ 慢。我们可以找到一个常数 $k=2$，因为对于足够大的 $n$，$n \cdot \log(n) \le n^2$ 总是成立的。所以 $n \cdot \log(n)$ 的增长率是多项式级别的（严格来说是准多项式时间，但在P类的上下文中，它被认为是高效的，并且被多项式所界定）。
2. $n^{100}+3n^2$: 这是一个真正的多项式函数。它的最高次项是 $n^{100}$。根据大O表示法的规则，我们只关心最高次项，所以这个函数的增长率是 $O(n^{100})$。因为它的增长率可以被 $n^k$（这里 $k=100$）形式的函数界定，所以它是多项式的。
3. $n^{0.001n}$: 这个函数的指数部分包含了变量 $n$。这种形式的函数，如 $n^n$，被称为超多项式或指数级的。它的增长速度远远超过任何多项式函数 $n^k$。随着 $n$ 的增大，$0.001n$ 这一项会变得非常大，使得整个表达式的增长是指数性的。
4. $2^{\sqrt{n}}$: 这个函数是一个指数函数，其底数为常数2，指数为 $n$ 的函数 $\sqrt{n}$。任何形如 $a^{f(n)}$（其中 $a>1$ 且 $f(n)$ 是一个随 $n$ 增长的函数）的函数，如果其指数部分不是对数级的，那么它通常是指数级的。$2^{\sqrt{n}}$ 的增长速度比任何多项式 $n^k$ 都要快。这被称为准指数时间。

因此，答案是正确的。前两者被多项式函数所界定，而后两者不是。

这个问题考察的是对 NP 类 定义的精确理解。NP (Nondeterministic Polynomial time) 的核心定义之一是基于验证器的。

一个语言 $L$ 属于 NP，如果存在一个确定性图灵机（即验证器） $V$，它满足两个条件：

1. 高效验证：$V$ 的运行时间必须是输入字符串 $x$ 长度的多项式，即 $O(|x|^k)$，其中 $k$ 是一个常数。
2. 完备性与可靠性：
   • 如果 $x \in L$，那么存在一个“证据”或“证书” $c$，使得 $V(x, c)$ 接受。
   • 如果 $x \notin L$，那么对于所有的证书 $c$，$V(x, c)$ 都拒绝。

从条件1可以推断出，证书 $c$ 的长度也必须是 $|x|$ 的多项式。为什么呢？因为如果 $c$ 的长度是 $|x|$ 的指数级，一个运行时间为 $|x|$ 多项式的验证器甚至没有足够的时间来完整地读取证书 $c$。

现在我们来看题目中的陈述：验证器 $V$ 的运行时间是 $|x|+|c|$ 的多项式。这看起来似乎是高效的，但问题在于它没有限制证书 $c$ 的长度。

错误之处：如果我们可以选择一个长度是 $|x|$ 指数级的证书 $c$（例如， $|c| = 2^{|x|}$），那么运行时间是 $|x|+|c|$ 的多项式，比如 $O((|x|+|c|)^2)$, 将会变成 $O((|x|+2^{|x|})^2)$。这个时间是关于 $|x|$ 的指数级，而不是多项式级。

这意味着，通过使用一个非常长的证书，我们给了验证器指数级的计算时间。这违反了 NP 定义中“多项式时间验证”的核心要求。这样的语言可能属于 NEXP (Nondeterministic Exponential Time)，但不一定在 NP 中。

这个问题考察的是 NP-完全 (NP-Complete, NPC) 问题的定义和性质。让我们先分解 NP-完全 的定义。

一个语言（问题）$B$ 是 NP-完全的，如果它满足两个条件：

1. $B \in \mathrm{NP}$：$B$ 本身是一个 NP 问题。这意味着存在一个多项式时间的验证器来验证 $B$ 的解。
2. $B$ 是 NP-难 (NP-Hard)：对于任何一个在 NP 中的语言 $L$，都存在一个多项式时间归约，记作 $L \leq_{\mathrm{P}} B$。这意味着 $L$ 的任何实例都可以通过一个多项式时间的转换函数，变成 $B$ 的一个实例，并且两者的答案（是/否）保持一致。通俗地说，$B$ 至少和 NP 中任何问题一样“难”。

现在题目说：任取两个 NP-完全 问题 $A$ 和 $B$，我们是否可以证明它们能相互进行多项式时间归约？也就是 $A \leq_{\mathrm{P}} B$ 并且 $B \leq_{\mathrm{P}} A$ 是否成立？答案的证明只展示了 $A \leq_{\mathrm{P}} B$，但 $B \leq_{\mathrm{P}} A$ 的证明是完全对称的。

让我们一步步跟随答案的逻辑：

1. 目标: 证明 $A \leq_{\mathrm{P}} B$。
2. 利用 $B$ 的性质: 我们知道 $B$ 是 NP-完全的，因此它一定是 NP-难的。
3. 应用 NP-难 的定义: 根据 NP-难的定义，对于 NP 中的 任何 语言 $L$，都有 $L \leq_{\mathrm{P}} B$。这个 $L$ 可以是 NP 集合中的任何一个问题。
4. 利用 $A$ 的性质: 我们也知道 $A$ 是 NP-完全的。根据 NP-完全定义的第一个条件，$A$ 本身必须在 NP 中，即 $A \in \mathrm{NP}$。
5. 关键结合: 在第3步中，我们说结论对 任何 $L \in \mathrm{NP}$ 成立。现在，在第4步中，我们确认了 $A$ 就是 NP 中的一个成员。因此，我们可以把那个普适的 $L$ 具体化为我们眼前的 $A$。
6. 得出结论: 将 $L=A$ 代入第3步的结论，我们直接得到 $A \leq_{\mathrm{P}} B$。

这个证明是完全正确的。由于 $A$ 和 $B$ 的地位是平等的，我们也可以用完全相同的方法，通过交换 $A$ 和 $B$ 的角色，来证明 $B \leq_{\mathrm{P}} A$。因此，所有 NP-完全 问题构成了一个等价类，它们在多项式时间归约的意义下，难度是完全相同的。

这个问题考察的是对“输入大小”的精确理解，这是复杂性分析的基石。一个算法是否是多项式时间的，是比较其运行时间与 输入编码的长度，而不是输入所代表的 数值的大小。

1. 输入是什么？ 输入是一个整数 $N$。
2. 输入是如何编码的？ 题目明确指出，它是以二进制形式给出的。
3. 输入大小是多少？ 一个整数 $N$ 的二进制表示所需要的位数大约是 $\log_2(N)$。所以，我们设输入大小（长度）为 $n = |\text{input}| \approx \log_2(N)$。
4. 算法的运行时间是多少？ 题目给出运行时间是 $O(N^2)$。这里的 $N$ 是数值本身。
5. 判断是否为多项式时间: 我们需要判断运行时间 $O(N^2)$ 是否是输入大小 $n$ 的多项式。换句话说， $O(N^2)$ 是否可以表示为 $O(n^k)$ 的形式，其中 $k$ 是一个常数？

让我们建立 $N$ 和 $n$ 之间的关系：

从 $n \approx \log_2(N)$，我们可以反解出 $N \approx 2^n$。

现在，我们将运行时间 $T(N) = O(N^2)$ 用输入大小 $n$ 来表示：

$T(n) = O((2^n)^2) = O(2^{2n})$。

这个结果 $O(2^{2n})$ 是一个关于输入大小 $n$ 的指数函数，而不是多项式函数 $O(n^k)$。因此，这个算法不是多项式时间的，而是指数时间的。

这个问题要求证明 NP 类对于并运算是封闭的。所谓“封闭”，是指对集合中的成员进行某种运算后，结果仍然在该集合中。这里，集合是 NP，运算是并集（Union）。也就是说，如果 $L_1$ 和 $L_2$ 都是 NP 问题，那么它们俩的并集 $L_1 \cup L_2$ 也一定是一个 NP 问题。

要证明 $L_1 \cup L_2 \in \mathrm{NP}$，我们需要根据 NP 的定义，为其构造一个多项式时间的验证器。我们称这个新的验证器为 $V$。

证明思路：

1. 利用已知条件: 我们知道 $L_1$ 和 $L_2$ 都在 NP 中。这意味着它们各自都有一个多项式时间的验证器，我们称之为 $V_1$ 和 $V_2$。
2. 构造新验证器 $V$: 我们要为 $L_1 \cup L_2$ 设计一个新的验证器 $V$。一个字符串 $x$ 属于 $L_1 \cup L_2$ 的意思是，$x$ 要么属于 $L_1$，要么属于 $L_2$（或者两者都属于）。
   • 那么，一个能证明 $x \in L_1 \cup L_2$ 的证据（证书 $c$），应该是什么样的呢？它应该要么是能让 $V_1$ 接受的证据，要么是能让 $V_2$ 接受的证据。
   • 所以，我们的新验证器 $V$ 在拿到输入 $x$ 和证书 $c$ 后，可以这么做：它先把 $c$ 当作是给 $V_1$ 的证书，运行 $V_1(x, c)$。如果 $V_1$ 接受了，太好了，这说明 $x \in L_1$，那么 $x$ 自然就在 $L_1 \cup L_2$ 中，所以 $V$ 可以立刻接受。
   • 如果 $V_1$ 拒绝了，也没关系。$V$ 再把 $c$ 当作是给 $V_2$ 的证书，运行 $V_2(x, c)$。如果 $V_2$ 接受了，说明 $x \in L_2$，那么 $x$ 也自然在 $L_1 \cup L_2$ 中，所以 $V$ 也应该接受。
   • 如果 $V_1$ 和 $V_2$ 都拒绝了 $c$，那么这个证书 $c$ 无法证明 $x$ 属于 $L_1$ 或 $L_2$。$V$ 就应该拒绝。
3. 证明 $V$ 是一个合法的NP验证器:
   • 时间复杂性分析: $V$ 的操作包括运行 $V_1$ 和运行 $V_2$。因为 $V_1$ 和 $V_2$ 都是多项式时间的（比如分别是 $O(|x|^{k_1})$ 和 $O(|x|^{k_2})$），那么顺序执行它们俩的总时间就是 $O(|x|^{k_1}) + O(|x|^{k_2})$，这仍然是 $|x|$ 的一个多项式时间 $O(|x|^{\max(k_1, k_2)})$。所以 $V$ 是高效的。
   • 正确性证明 (完备性与可靠性): 这需要证明双向蕴含关系 $x \in L_{1} \cup L_{2} \Longleftrightarrow \exists c \text { such that } V(x, c) \text { accepts}$。
   • ($\Rightarrow$) 正向证明 (完备性):
   • 假设 $x \in L_1 \cup L_2$。我们需要证明存在一个证书 $c$ 能让 $V$ 接受。
   • 分两种情况：
   • Case 1: $x \in L_1$。因为 $L_1 \in \mathrm{NP}$，所以必然存在一个证书 $c_1$ 使得 $V_1(x, c_1)$ 接受。那么，我们让新验证器 $V$ 使用这个 $c_1$ 作为证书，即 $c=c_1$。根据 $V$ 的设计，它会运行 $V_1(x, c_1)$，发现 $V_1$ 接受了，于是 $V$ 就会接受。我们找到了一个让 $V$ 接受的证书。
   • Case 2: $x \in L_2$。同理，存在一个证书 $c_2$ 使得 $V_2(x, c_2)$ 接受。我们让 $V$ 使用 $c=c_2$ 作为证书。$V$ 先运行 $V_1(x, c_2)$ (可能会拒绝)，然后运行 $V_2(x, c_2)$，发现 $V_2$ 接受了，于是 $V$ 接受。我们也找到了一个让 $V$ 接受的证书。
   • 综上，只要 $x \in L_1 \cup L_2$，就一定能找到一个证书让 $V$ 接受。
   • ($\Leftarrow$) 反向证明 (可靠性):
   • 假设存在一个证书 $c$ 使得 $V(x, c)$ 接受。我们需要证明 $x \in L_1 \cup L_2$。
   • 根据 $V$ 的算法，它接受只可能是两种情况之一：要么是 $V_1(x, c)$ 接受了，要么是 $V_2(x, c)$ 接受了。
   • 如果 $V_1(x, c)$ 接受，根据 $V_1$ 是 $L_1$ 的验证器，我们知道 $x \in L_1$。
   • 如果 $V_2(x, c)$ 接受，根据 $V_2$ 是 $L_2$ 的验证器，我们知道 $x \in L_2$。
   • 既然 $x \in L_1$ 或者 $x \in L_2$，那么根据并集的定义，必然有 $x \in L_1 \cup L_2$。
4. 结论: 我们成功地为 $L_1 \cup L_2$ 构建了一个多项式时间的验证器 $V$，并证明了其正确性。因此，根据 NP 的定义，$L_1 \cup L_2 \in \mathrm{NP}$。NP 在并运算下是封闭的。

这个问题探讨了当 团 (Clique) 问题中的团大小 $k$ 是一个固定的常数时，其复杂性。我们要证明 $k$-Clique 问题属于 P 类，即存在一个多项式时间的确定性算法来解决它。

问题定义:

• 输入: 一个有 $n$ 个顶点的图 $G$。
• 参数: 一个固定的常数 $k$ (比如 $k=3, k=5, k=100$)。注意 $k$ 不是输入的一部分。
• 问题: 图 $G$ 中是否存在一个大小为 $k$ 的顶点子集，其中任意两个顶点之间都有边相连（即形成一个 $k$-团）？

算法思路 (暴力搜索):

既然我们要找一个大小为 $k$ 的特定子集，最直接的方法就是检查所有可能性。

1. 从图 $G$ 的 $n$ 个顶点中，枚举出所有可能的大小为 $k$ 的顶点子集。
2. 对于每一个枚举出的子集 $S$，检查它是否构成一个团。
   • 如何检查？对子集 $S$ 中的任意一对顶点 $(u, v)$，都去查询图 $G$ 中是否存在边 $(u,v)$。
   • 如果对于所有顶点对，边都存在，那么恭喜，我们找到了一个 $k$-团。算法可以立即停止并返回“是”。
3. 如果检查完所有的大小为 $k$ 的子集后，都没有找到一个团，那么图中就不存在 $k$-团。算法返回“否”。

时间复杂性分析:

这是证明的关键部分。我们要分析上述算法的运行时间是否是输入大小 $n$ 的多项式。

1. 输入大小: 图 $G$ 有 $n$ 个顶点，可以用一个 $n \times n$ 的邻接矩阵表示，所以输入大小是 $O(n^2)$。我们的复杂性要与 $n$ 进行比较。
2. 步骤1的计算量: 从 $n$ 个顶点中选取 $k$ 个组成一个子集，总共有 $\binom{n}{k}$ 种组合。

$\binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{n(n-1)\dots(n-k+1)}{k!}$

由于 $k$ 是一个常数， $k!$ 也是一个常数。上式的分子是一个关于 $n$ 的 $k$ 次多项式。因此，$\binom{n}{k} = O(n^k)$。

1. 步骤2的计算量: 对于每一个大小为 $k$ 的子集 $S$，我们需要检查其中所有顶点对。一个大小为 $k$ 的集合有 $\binom{k}{2} = \frac{k(k-1)}{2}$ 对顶点。检查每对顶点之间是否有边，在邻接矩阵中只需要 $O(1)$ 的时间。

由于 $k$ 是一个常数，$\binom{k}{2}$ 也是一个常数。所以，检查一个子集是否为团的时间是 $O(k^2)$，也就是常数时间。

1. 总运行时间: 总时间 = (子集数量) $\times$ (检查每个子集的时间)

$T(n) = O(n^k) \times O(k^2)$

因为 $k$ 是常数，所以 $O(k^2)$ 也是常数。因此，总运行时间是 $T(n) = O(n^k)$。

1. 结论: 运行时间 $O(n^k)$ 是一个关于 $n$ 的多项式（因为指数 $k$ 是常数）。因此，$k$-Clique 问题属于 P 类。

这个问题解释了为什么当团的大小 $k$ 成为输入的一部分时，前面用于证明 $k$-Clique $\in \mathrm{P}$ 的算法不再是多项式时间的。这正是通用 Clique 问题是 NP-完全 而非 P 类问题的关键所在。

问题定义的变化:

• 输入: 一个图 $G$（大小 $O(n^2)$）和 一个整数 $k$（大小 $O(\log k)$）。
• 总输入大小: 约为 $O(n^2 + \log k)$。
• 问题: 图 $G$ 中是否存在一个大小为 $k$ 的团？

分析之前的算法:

我们仍然使用相同的暴力搜索算法：枚举所有大小为 $k$ 的子集并检查。

• 运行时间: $T(n, k) = O(\binom{n}{k} \cdot k^2)$。

为什么不再是多项式时间？

关键在于，现在的运行时间必须与总输入大小 $O(n^2 + \log k)$ 进行比较。

让我们考虑一个最坏情况的例子，正如原文所建议的：

• 设 $k = n/2$。这是一个非常合理的情形，因为 $k$ 是输入的一部分，它可以是 $n$ 的一个函数。
• 输入大小: $O(n^2 + \log(n/2)) = O(n^2)$。
• 算法运行时间:
• 算法需要检查 $\binom{n}{n/2}$ 个子集。
• 使用斯特林公式近似，我们知道 $\binom{n}{n/2} \approx \frac{2^n}{\sqrt{\pi n/2}}$。这是一个指数级别的数量，为 $O(2^n / \sqrt{n})$。
• 每个子集的检查时间是 $O(k^2) = O((n/2)^2) = O(n^2)$。
• 总运行时间 $T(n) = O(\frac{2^n}{\sqrt{n}} \cdot n^2)$。

现在我们来比较：

• 运行时间: $O(2^n \cdot n^{1.5})$，这是一个关于 $n$ 的指数函数。
• 输入大小: $O(n^2)$，这是一个关于 $n$ 的多项式函数。

由于运行时间是输入大小的指数函数，而不是多项式函数，所以这个算法不是多项式时间算法。

为什么之前的证明失效了？

之前的证明依赖于一个关键假设：$T(n) = O(n^k)$ 是一个多项式时间，因为指数 $k$ 是一个常数。

但是现在，指数 $k$ 本身就是输入的一部分，是一个变量。当 $k$ 可以随 $n$ 变化时（例如 $k=n/2$），运行时间 $O(n^k)$ 就变成了 $O(n^{n/2})$，这显然不是一个多项式函数。

这个问题探讨了一个非常反直觉的、但在理论上极为重要的推论：如果 P=NP 这个千古猜想成立，那么整个复杂性世界的版图将会发生惊人的坍塌。具体来说，几乎所有我们认为“简单”的 P 类问题（除了两个最极端的平凡问题），都将在一夜之间变成“最难”的 NP-完全 问题。

证明框架:

1. 前提假设:
   • P = NP。这意味着所有 NP 问题都可以在多项式时间内被确定性地解决。
   • $A$ 是一个语言，满足：
   • $A \in \mathrm{P}$ (A 是一个“简单”问题)。
   • $A \neq \emptyset$ (A 不是空集，即至少包含一个“是”的实例)。
   • $A \neq \Sigma^*$ (A 不是全集，即至少包含一个“否”的实例)。 $\Sigma^*$ 代表所有可能的字符串集合。
2. 目标: 证明 $A$ 是 NP-完全的。
3. NP-完全的定义: 要证明 $A$ 是 NP-完全的，我们需要证明两点：
   • (a) $A \in \mathrm{NP}$
   • (b) $A$ 是 NP-难的 (即，所有 NP 问题都能多项式时间归约到 $A$)。

分步证明:

• 证明 (a) $A \in \mathrm{NP}$:
• 我们已知 $A \in \mathrm{P}$。
• 因为所有可以在多项式时间解决的问题，都可以在多项式时间验证（验证器可以直接自己解决问题，忽略证书），所以 P 是 NP 的一个子集 ($\mathrm{P} \subseteq \mathrm{NP}$)。
• 因此，从 $A \in \mathrm{P}$ 可以直接推出 $A \in \mathrm{NP}$。这部分证毕。

• 证明 (b) $A$ 是 NP-难的:
• 要证明 $A$ 是 NP-难的，我们需要证明对于任意一个 $L \in \mathrm{NP}$，都有 $L \leq_{\mathrm{P}} A$。
• 一个更便捷的技巧是：我们只需要证明一个已知的 NP-完全 问题可以归约到 $A$ 即可。因为 NP-完全 问题之间可以互相归约，只要 $A$能和它们中的任何一个“搭上关系”，就等于和所有 NP 问题都搭上了关系。
• 我们选择一个经典的 NP-完全 问题，比如 3-SAT。
• 我们的子目标: 证明 $\text{3-SAT} \leq_{\mathrm{P}} A$。
• 归约函数构造: 我们需要构造一个多项式时间的函数 $f$，把任意一个 3-SAT 的实例 $\phi$ 映射成 $A$ 的一个实例 $f(\phi)$，并满足 $\phi \in \text{3-SAT} \iff f(\phi) \in A$。

构造归约函数 $f$:

1. 利用前提:
   • 因为 $A \neq \emptyset$ 且 $A \neq \Sigma^*$，所以必定存在一个字符串 $y$ 使得 $y \in A$，和另一个字符串 $z$ 使得 $z \notin A$。这两个 $y$ 和 $z$ 是固定的。
   • 因为 P = NP，所以 3-SAT 这个问题本身也在 P 中。这意味着存在一个多项式时间的算法（判定器）$M$，可以直接判断任意给定的布尔范式 $\phi$ 是否可满足。
2. 定义函数 $f(\phi)$:
   • 输入：一个 3-CNF 公式 $\phi$。
   • 算法：
3. 运行多项式时间的 3-SAT 判定器 $M$ 在输入 $\phi$ 上。
4. 如果 $M$ 输出“是”（即 $\phi$ 是可满足的）：那么函数 $f$ 就输出我们预先找到的那个固定字符串 $y$。
5. 如果 $M$ 输出“否”（即 $\phi$ 是不可满足的）：那么函数 $f$ 就输出我们预先找到的那个固定字符串 $z$。
6. 验证函数 $f$ 的有效性:
   • $f$ 是多项式时间的吗？ 是。因为 $f$ 的主体操作就是运行算法 $M$，而我们知道 $M$ 是多项式时间的。找到 $y$ 和 $z$ 是一个一次性的预备工作，不计入每次调用的时间。输出 $y$ 或 $z$ 也是常数时间。
   • $f$ 满足归约条件吗？ 我们需要检查 $\phi \in \text{3-SAT} \iff f(\phi) \in A$。
   • 正向: 如果 $\phi \in \text{3-SAT}$，那么 $M$ 会接受，我们的 $f$ 会输出 $y$。因为我们选择的 $y$ 满足 $y \in A$，所以 $f(\phi) \in A$。条件满足。
   • 反向: 如果 $f(\phi) \in A$，那么 $f$ 输出的结果必须是 $y$（因为 $z \notin A$）。而 $f$ 只在 $M$ 接受 $\phi$ 时才输出 $y$。$M$ 接受 $\phi$ 意味着 $\phi \in \text{3-SAT}$。条件满足。
   • 归约条件成立！
7. 最终结论:
   • 我们成功证明了 $\text{3-SAT} \leq_{\mathrm{P}} A$。这意味着 $A$ 是 NP-难的。
   • 结合我们之前证明的 $A \in \mathrm{NP}$，根据定义，$A$ 是 NP-完全的。

关于平凡语言 $\emptyset$ 和 $\Sigma^*$ 的解释:

• 为什么 $A$ 不能是 $\emptyset$？
• 如果 $A=\emptyset$（空集），那么任何字符串都不在 $A$ 中，即 $f(x) \in A$ 永远为假。
• 归约条件是 $x \in L \iff f(x) \in A$。如果 $L$ 不是空集（比如 3-SAT 就不是），那么总存在某个 $x \in L$。对于这个 $x$，左边为真，右边为假，矛盾。所以无法构造出这样的归约。
• 为什么 $A$ 不能是 $\Sigma^*$？
• 如果 $A=\Sigma^*$（全集），那么任何字符串都在 $A$ 中，即 $f(x) \in A$ 永远为真。
• 如果 $L$ 不是全集（比如 3-SAT），那么总存在某个 $x \notin L$。对于这个 $x$，左边为假，右边为真，矛盾。也无法构造出归约。
• 这两个平凡语言无法作为归约的目标，因为它们无法区分“是”与“否”两种情况，失去了作为“逻辑门”的能力。

这个问题展示了一对看似“镜像”的问题，但它们的复杂性却有天壤之别。SPATH (Shortest Path) 寻找短路径，而 LPATH (Longest Path) 寻找长路径。

第一部分：证明 SPATH $\in \mathrm{P}$

问题定义:

• SPATH: 给定图 $G$，起点 $a$，终点 $b$，和一个整数 $k$。问是否存在一条从 $a$ 到 $b$ 的简单路径，其长度（边的数量）至多为 $k$？

关键洞察:

• 如果存在一条从 $a$ 到 $b$ 长度不大于 $k$ 的路径，那么最短的那条路径的长度也必然不大于 $k$。
• 广度优先搜索 (BFS) 是一个寻找图中两点间最短路径（以边的数量衡量）的经典算法。
• BFS 找到的路径天然就是简单路径，因为它按层次扩展，不会走回头路形成环。

算法:

1. 在图 $G$ 上，从源点 $a$ 开始执行 BFS。
2. BFS 会维护每个节点到 $a$ 的最短距离。我们用一个数组 dist[] 来记录，初始时 dist[a]=0，其他为无穷大。
3. BFS 逐层扩展。首先访问所有 dist=1 的节点，然后是 dist=2 的节点，以此类推。
4. 在 BFS 执行过程中，一旦我们第一次到达节点 $b$，此时记录的 dist[b] 就是从 $a$ 到 $b$ 的最短路径长度。
5. 我们可以修改 BFS：
   • 如果在搜索过程中计算出的 dist[b] 小于或等于 $k$，那么我们已经找到了一条满足条件的路径。算法可以立即停止并返回“是”。
   • 如果 BFS 正常结束（即所有从 $a$ 可达的节点都已访问）而我们从未到达 $b$，或者到达 $b$ 时其最短距离 dist[b] 已经大于 $k$，那么就不存在这样的短路径。
   • 一个更简单的实现是：完整运行 BFS 得到从 $a$ 到所有点的最短距离。然后检查 dist[b] 的值。如果 dist[b] <= k，则返回“是”，否则返回“否”。

时间复杂性分析:

• BFS 算法的运行时间对于一个有 $V$ 个顶点和 $E$ 条边的图是 $O(V+E)$。
• 输入大小是图的描述（邻接矩阵 $O(V^2)$ 或邻接表 $O(V+E)$）加上 $a,b,k$。
• $O(V+E)$ 是输入大小的多项式（甚至是线性的）。
• 因此，SPATH 问题可以在多项式时间内解决，故 SPATH $\in \mathrm{P}$。

第二部分：证明 LPATH 是 NP-完全的

要证明 LPATH 是 NP-完全的，我们需要做两件事：

1. 证明 LPATH $\in \mathrm{NP}$。
2. 证明 LPATH 是 NP-难的。

1. 证明 LPATH $\in \mathrm{NP}$

• 思路: 我们需要为 LPATH 设计一个多项式时间的验证器。
• 证书: 一个合理的证书 $p$ 就是一条宣称满足条件的路径，即一个顶点的序列。
• 验证器算法 (Algorithm 5):
• 输入: $\langle G, a, b, k \rangle$ 和证书（路径）$p$。
• 步骤1: 检查 $p$ 是否是一条从 $a$到$b$ 的简单路径。
• 检查路径的起点是否是 $a$，终点是否是 $b$。($O(1)$)
• 检查路径中没有重复的顶点。（用哈希表或排序，可在路径长度的多项式时间内完成）。
• 检查路径中每一步相邻的两个顶点在图 $G$ 中是否真的有边相连。（$O(|p|)$ 次查询）。
• 步骤2: 检查路径 $p$ 的长度是否至少为 $k$。路径长度是顶点数减1，即 $|p|-1 \ge k$。($O(|p|)$)。
• 结论: 如果上述检查都通过，则接受；否则拒绝。
• 时间分析: 路径 $p$ 作为简单路径，其长度最多为 $n-1$（$n$是顶点数）。所有检查步骤都可以在图和路径大小的多项式时间内完成。因此，验证器是多项式时间的。
• 正确性: 如果存在这样一条长路径，那么这条路径本身就是最好的证书。如果不存在，任何给定的路径都无法通过验证。
• 结论: LPATH 属于 NP。

2. 证明 LPATH 是 NP-难的

• 思路: 我们需要把一个已知的 NP-完全问题多项式时间归约到 LPATH。一个和路径问题高度相关的 NP-完全问题是哈密顿路径 (HamPath)。
• 归约目标: 证明 HamPath $\leq_{\mathrm{P}}$ LPATH。
• HamPath 问题定义: 给定图 $G$ 和两个顶点 $s, t$，问是否存在一条从 $s$ 到 $t$ 的简单路径，恰好访问图中每个顶点一次？
• 构造归约函数 $f$:
• $f$ 的输入: 一个 HamPath 问题的实例 $\langle G=(V,E), s, t \rangle$。设 $|V|=n$。
• $f$ 的输出: 一个 LPATH 问题的实例 $\langle G', a, b, k \rangle$。
• 我们的构造非常直接：
• $G' = G$ (图保持不变)
• $a = s$ (起点保持不变)
• $b = t$ (终点保持不变)
• $k = n-1$ (设置目标路径长度为 $n-1$)
• 于是，$f(\langle G, s, t \rangle) = \langle G, s, t, n-1 \rangle$。（原文中用 $k=n$ 假设路径长度为顶点数，这里按边数算为 $n-1$，两者等价）。
• 验证归约:
• $f$ 是多项式时间的吗？ 是。这个函数只是复制了图和起终点，并将 $k$ 设置为 $n-1$。计算 $n$ 并输出，这些都是非常快速的操作。
• 满足归约条件吗？ 我们需要证明 $\langle G, s, t \rangle \in \text{HamPath} \iff \langle G, s, t, n-1 \rangle \in \text{LPATH}$。
• ($\Rightarrow$) 正向: 假设 $G$ 中存在一条从 $s$ 到 $t$ 的哈密顿路径。
• 根据哈密顿路径的定义，这是一条访问了全部 $n$ 个顶点的简单路径。
• 一条包含 $n$ 个不同顶点的路径，其边的数量恰好是 $n-1$。
• 所以，我们找到了一条从 $s$ 到 $t$ 的简单路径，其长度为 $n-1$。
• 这条路径的长度满足“至少为 $n-1$”的要求。
• 因此，$\langle G, s, t, n-1 \rangle \in \text{LPATH}$。
• ($\Leftarrow$) 反向: 假设 $\langle G, s, t, n-1 \rangle \in \text{LPATH}$。
• 这意味着，在图 $G$ 中，存在一条从 $s$ 到 $t$ 的简单路径，其长度至少为 $n-1$。
• 一条简单路径不能有重复顶点。在一个只有 $n$ 个顶点的图中，一条简单路径最多只能包含 $n$ 个顶点，其长度最大为 $n-1$。
• 所以，“长度至少为 $n-1$” 和 “长度最大为 $n-1$” 结合起来，意味着这条路径的长度必须 恰好是 $n-1$。
• 一条长度为 $n-1$ 的简单路径必然访问了 $n$ 个不同的顶点。
• 在一个只有 $n$ 个顶点的图中，这意味着它访问了 所有 顶点。
• 这完全符合哈密顿路径的定义。
• 因此，$\langle G, s, t \rangle \in \text{HamPath}$。
• 结论: 归约有效。我们证明了 HamPath $\leq_{\mathrm{P}}$ LPATH。因为 HamPath 是 NP-完全的，所以 LPATH 至少和它一样难，故 LPATH 是 NP-难的。

最终结论:

• 因为 LPATH $\in \mathrm{NP}$ 并且 LPATH 是 NP-难的，所以根据定义，LPATH 是 NP-完全的。

这个脚注是对练习1中问题2答案的补充说明，它解释了为什么 NP 定义中“验证器 $V$ 运行时间是 $|x|$ 的多项式”这一条，隐含地要求了“证书 $c$ 的长度也必须是 $|x|$ 的多项式”。

逻辑链条:

1. 前提: 验证器 $V$ 的运行时间是 $T_V = O(|x|^k)$，其中 $k$ 是常数。
2. 图灵机的工作方式: 一个图灵机要处理输入，必须先在带子上读取它。读取一个长度为 $m$ 的输入，至少需要 $m$ 步操作（磁头需要移动 $m$ 个位置）。
3. $V$ 的输入: 验证器 $V$ 的总输入是字符串 $x$ 和证书 $c$，总长度是 $|x| + |c|$。
4. 时间下限: 要完整读取其输入， $V$ 至少需要 $O(|x| + |c|)$ 的时间。
5. 结合: 我们有 $V$ 的运行时间必须同时满足两个条件：
   • $T_V \ge O(|x| + |c|)$ (因为要读取输入)
   • $T_V = O(|x|^k)$ (根据 NP 的定义)
6. 推论: 将两者结合，我们得到 $O(|x| + |c|) \le O(|x|^k)$。
7. 结论: 为了使这个不等式成立， $|c|$ 的大小不能超过 $|x|$ 的多项式。如果 $|c|$ 是指数级的，比如 $2^{|x|}$，那么左边就是指数级的，右边是多项式级的，不等式将不成立。所以，必然存在某个多项式 $p$ 使得 $|c| \le p(|x|)$。

这个脚注是针对练习2（证明 NP 对并集封闭）中构造的新验证器 $V$ 的一个技术性补充。它处理了一个微妙的边界情况。

问题: 在我们为 $L_1 \cup L_2$ 构造的验证器 $V$ 中，我们假设 $V_1$ 和 $V_2$ 的运行时间分别是 $p_1(|x|)$ 和 $p_2(|x|)$。根据上一条脚注的逻辑，它们各自的有效证书 $c_1, c_2$ 的长度也分别被 $p_1(|x|)$ 和 $p_2(|x|)$ 所限制。那么，我们给新验证器 $V$ 的证书 $c$ 的长度应该是什么呢？

脚注的观点:

1. 我们知道 $V_1$ 的运行时间是某个多项式 $p_1(|x|)$， $V_2$ 的运行时间是 $p_2(|x|)$。
2. 如果提供给 $V_1$ 的证书 $c$ 的长度 $|c|$ 大于 $p_1(|x|)$，那么 $V_1$ 甚至没有足够的时间来读完整个证书，它绝对不可能接受。同样的情况也适用于 $V_2$。
3. 因此，在我们构造的验证器 $V(x, c)$ 中，可以增加一个初始步骤：检查证书 $c$ 的长度。
   • 设 $p_{max}(|x|) = \max(p_1(|x|), p_2(|x|))$。
   • 如果 $|c| > p_{max}(|x|)$，那么这个 $c$ 不可能是 $V_1$ 或 $V_2$ 的有效证书，我们可以让 $V$ 直接拒绝，而无需实际运行 $V_1$ 或 $V_2$。
4. 这个预检查步骤确保了传递给 $V_1$ 和 $V_2$ 的证书长度是有界的，从而使整个时间分析更加严谨。它明确了新验证器 $V$ 的有效证书长度也被一个多项式所限制，即 $p_{max}(|x|)$。

为什么可以忽略:

作者说这是“可以忽略的技术点”，因为 NP 的定义是“存在一个证书”。我们证明了如果 $x \in L_1 \cup L_2$，那么就存在一个（长度为多项式的）证书 $c_1$ 或 $c_2$ 能让 $V$ 接受。对于那些过长的、无效的证书，我们的验证器 $V$ 将会（正确地）拒绝它们，这并不影响证明的核心逻辑。这个脚注只是让验证器的构造更加“鲁棒”和“高效”。

这个脚注是对练习3中关于通用 Clique 问题分析的强调。

核心思想:

1. 复杂性分析是悲观的: 在分析一个算法的复杂性时，我们通常关心的是最坏情况 (Worst-Case)。这意味着我们要找到一种输入，能让算法运行得最慢，并以此作为其性能的度量。
2. 在 Clique 问题中什么是“最坏情况”: 对于暴力枚举算法 $O(\binom{n}{k}k^2)$，其运行时间主要由组合数 $\binom{n}{k}$ 决定。
3. $\binom{n}{k}$ 的性质: 对于固定的 $n$，当 $k$ 在 $n/2$ 附近时，$\binom{n}{k}$ 的值最大。当 $k$ 接近 0 或 $n$ 时，$\binom{n}{k}$ 的值很小。
4. 构造最坏输入: 因此，要让算法变得“非常慢”，我们只需要选择一个 $k$ 值，它是 $n$ 的一个线性函数，比如 $k=n/2$ 或者 $k=n/3$。只要 $k$ 不是常数，并且能随 $n$ 增长，算法的指数特性就会暴露出来。
5. 结论: 哪怕算法对于某些输入（比如 $k=2$）很快，但只要存在一类系统性的输入（比如 $k=n/2$）能让它变得指数慢，这个算法就不是多项式时间算法。

这个脚注是作者在练习5证明 LPATH 的 NP-难度时，对自己使用的“路径长度”定义的一个澄清。

两种常见的“路径长度”定义:

1. 边数 (Edge Count): 一条路径经过的边的数量。这是图论中最常见的定义。一条从 $v_0$到$v_m$的路径 $v_0 \to v_1 \to \dots \to v_m$ 长度为 $m$。
2. 顶点数 (Vertex Count): 一条路径包含的顶点的数量。在同样路径下，长度为 $m+1$。

脚注的作用:

• 在证明 LPATH 是 NP-难 时，作者将 HamPath 归约到 LPATH，并将 LPATH 的参数 $k$ 设置为 $n$（图中顶点的总数）。
• 他这么做的依据是，他把“路径长度”暂时定义为了“路径上的顶点数”。
• 根据这个定义：
• 哈密顿路径：访问所有 $n$ 个顶点的路径 $\implies$ 长度为 $n$。
• LPATH 问题：寻找长度至少为 $k$ 的路径。
• 设置 $k=n$ 后，LPATH 问题就变成了“寻找长度至少为 $n$ 的简单路径”。
• 在一个 $n$ 顶点的图中，简单路径最长就是 $n$（访问所有顶点）。
• 所以“长度至少为 $n$”就等价于“长度恰好为 $n$”，这正好就是哈密顿路径。

与标准定义的关系:

• 如果使用标准的“边数”定义：
• 哈密顿路径：访问 $n$ 个顶点 $\implies$ 长度为 $n-1$ 条边。
• 归约时应设置 $k=n-1$。
• LPATH 问题变成“寻找长度至少为 $n-1$ 的简单路径”。
• 简单路径最长为 $n-1$ 条边。
• 所以“长度至少为 $n-1$”等价于“长度恰好为 $n-1$”，这也正好是哈密顿路径。

结论:

这个脚注澄清了作者在特定步骤中使用了一个非标准的定义，但它想强调的是，无论使用哪种定义，证明的逻辑都是完全相同的，只是具体的 $k$ 值差了1。这不影响归约的正确性。

本部分旨在对整个“讲义 11B：复杂性复习 - 解答”进行一次高层次的总结，提炼出每个练习所揭示的核心概念与思想。通过这次回顾，我们可以将孤立的知识点串联起来，形成对计算复杂性理论更宏观和深刻的理解。