1 讲义 11A：复杂性回顾

这部分是讲义的引言。作者 William Pires 首先明确了这份讲义的目的和内容。

1. 目的：这份讲义旨在提供一些在课堂上可能被提及但没有详细证明的理论主张的完整证明。这在理论课程中很常见，因为课堂时间有限，无法深入每一个细节。讲义作为补充材料，让学生可以深入研究。
2. 内容：讲义包含了一些关键主张的证明。
3. 学习建议：作者建议学生将阅读和理解这些证明，甚至尝试自己独立推导它们，作为一种学习练习。这有助于加深对概念的理解，而不仅仅是记忆结论。
4. 范围说明：作者强调，学生的考试或课程要求范围仅限于课堂上讲授的内容。这份讲义是可选的补充学习材料，但对深入理解非常有益。
5. 后续内容预告：引言最后提到，讲义的后半部分内容可能会在未来的讲座中进行讲解，这暗示了讲义内容的重要性以及与课程进度的衔接。

这一段引入了计算复杂性理论的核心概念之一：时间复杂性。

1. 基本设定：我们从一个理论计算模型——图灵机 $M$ 开始。这个图灵机被设计用来“判决”一个语言 $L$。“判决”（decide）一个语言意味着对于任何给定的字符串，图灵机总能在有限的时间内停机，并明确地回答“是”（接受）或“否”（拒绝）。“是”表示该字符串属于语言 $L$，“否”则表示不属于。
2. 核心问题：我们关心的不仅仅是图灵机 能否 解决问题，更关心它解决问题需要 多长时间。这个“多长时间”就是时间复杂性要研究的对象。
3. 衡量标准：时间不是用秒或分钟来衡量的，因为那取决于具体的计算机硬件。在理论计算机科学中，时间是用图灵机执行的“步骤”数来衡量的。一个步骤通常指一次状态转换。
4. 输入的角色：解决一个问题的耗时通常不固定，它依赖于问题的“规模”。对于图灵机来说，问题的规模就是输入字符串 $x$ 的长度，记为 $|x|$。输入越长，通常处理时间也越长。
5. 函数关系：因此，我们不讨论某个具体输入的运行时间，而是将运行时间看作是输入长度 $n$ 的一个函数。这个函数描述了运行时间随着输入长度增长的变化趋势。

这个定义精确地形式化了上一段引入的“运行时间函数”的概念。

1. 前提条件：这个定义只适用于“在每个输入上都停机”的图灵机。这种图灵机也叫判决器 (decider)。如果一个图灵机在某些输入上会无限循环，那么它的运行时间就是无限，这个定义就没意义了。
2. 运行时间的记号：运行时间函数通常用 $t(n)$ 表示，其中 $n$ 是输入长度。
3. 核心思想：最坏情况分析 (Worst-Case Analysis)：定义中的 max 是关键。对于所有长度为 $n$ 的输入字符串，它们的实际运行步数可能各不相同。$t(n)$ 取的是这些步数中的“最大值”。这意味着我们总是在为最坏的情况做准备。无论你给我哪个长度为 $n$ 的输入，我都能保证在 $t(n)$ 步之内解决它。
4. 形式化定义：
   • $t(n) :=$ 这是定义 $t(n)$ 的符号。
   • $\max_{x \in \Sigma^{*},|x|=n}$：这部分是说，我们要考虑所有可能的、长度为 $n$ 的输入字符串 $x$。$\Sigma^{*}$ 表示由字母表 $\Sigma$ 中所有符号组成的所有有限长度字符串的集合。
   • number of steps M takes before it halts on x：这是对单个输入 $x$ 的运行步数。
5. 步骤的定义：一段补充说明，明确了“步骤数”就是图灵机从开始到停机所执行的状态转换的总次数。

这一段解释了为什么我们需要以及如何使用大O符号 (Big O Notation)。

1. 动机：精确计算 $t(n)$，比如 $t(n) = 5n^2 + 10n + 3$，是非常繁琐且不必要的。我们更关心的是当输入规模 $n$ 变得非常大时，运行时间的“增长趋势”或“数量级”。是像 $n$ (线性)，还是像 $n^2$ (平方)，或是像 $2^n$ (指数)？
2. 大 O 的作用：大O符号提供了一种标准的方式来忽略那些在 $n$ 很大时变得不重要的部分（低阶项和常数系数），而只关注起主导作用的部分。它描述了函数增长的“上界”。
3. 形式化定义：$f(n) = O(g(n))$ 这句话的含义是“函数 $f(n)$ 的增长速度不会比函数 $g(n)$ 快太多”。
   • 前提：有两个从自然数（$\mathbb{N}$）映射到正实数（$\mathbb{R}^{+}$）的函数 $f$ 和 $g$。在我们的场景中，$f(n)$ 就是运行时间 $t(n)$。
   • 条件：要满足 $f(n) = O(g(n))$，必须能找到两个常数：一个正的比例因子 $c$ 和一个起始点 $n_0$。
   • 核心不等式：对于所有大于等于这个起始点 $n_0$ 的 $n$，不等式 $f(n) \leq c \cdot g(n)$ 必须恒成立。这意味着，从 $n_0$ 开始，$f(n)$ 的曲线总是在 $c \cdot g(n)$ 曲线的下方（或与之重合）。

这个定义利用大O符号将具有相似运行时间的语言（或问题）归为一类，这个“类”就是复杂性类。

1. 什么是复杂性类：复杂性类是一个“装语言的篮子”。所有能被某种特定资源限制（比如时间或空间）的计算模型解决的语言，都被放进同一个篮子里。
2. TIME(t(n)) 的定义：这个特定的篮子叫做 $\operatorname{Time}(t(n))$。它装的是所有那些“可以被一个运行时间为 $O(t(n))$ 的图灵机判决”的语言。
3. 展开定义：一个语言 $L$ 属于 $\operatorname{Time}(t(n))$，当且仅当：
   • 存在一个图灵机 $M$ 能够判决 $L$。
   • 这个图灵机 $M$ 的运行时间是 $O(t(n))$。根据大O定义，这意味着存在常数 $c$ 和 $n_0$，使得对于所有长度 $n \geq n_0$ 的输入，$M$ 的最坏情况运行步数不超过 $c \cdot t(n)$。
4. 对计算模型的敏感性：这是一个非常重要的理论细节。$\operatorname{Time}(t(n))$ 的确切内容取决于你用的是哪种图灵机。例如，一个问题用“多带图灵机”可能在 $O(n)$ 时间解决，但用“单带图灵机”可能需要 $O(n^2)$ 时间。这意味着同一个语言 $L$ 可能属于多带图灵机的 $\operatorname{Time}(n)$，但属于单带图灵机的 $\operatorname{Time}(n^2)$。
5. P 的优越性：作者提前剧透，后续将要定义的复杂性类 P（多项式时间）有一个非常好的特性，就是它对这些常见的确定性计算模型不敏感。一个问题在多带图灵机上是多项式时间可解的，那么在单带图灵机上也是（尽管多项式的次数可能会增加）。这使得我们可以忽略底层模型的细节，直接用更方便的伪代码来讨论算法，只要能证明它是多项式时间的就行。

这段内容定义了什么是“多项式”时间，并列举了它的关键性质。这是区分“高效”算法和“低效”算法的核心分界线。

1. 多项式的定义：一个函数 $f(n)$ 被认为是多项式的，如果它的增长速度被某个 $n^k$ 函数所限制。换句话SHUO，它的大O表示是 $O(n^k)$，其中 $k$ 是一个固定的常数，与 $n$ 无关。
2. 示例分析：
   • $n^5 + 1000$：是 $O(n^5)$，因为当 $n$ 很大时，$n^5$ 项占主导。这里的 $k=5$，所以它是多项式的。
   • $\log(n)$：对数函数的增长比任何 $n^k$（只要 $k>0$）都要慢。例如，$\log(n) = O(n^1)$。所以它也是多项式的。这是一个需要注意的点，比多项式增长慢的函数也算在多项式时间的范畴里。
   • $2^n + n^3$：这是一个指数函数。无论你选择多大的常数 $k$，当 $n$ 足够大时，$2^n$ 的增长最终都会超过 $n^k$。因此，$2^n$ 不是 $O(n^k)$，这个函数不是多项式的。
3. 多项式的封闭性 (Closure Properties)：这部分是“好消息”，因为它说明了多项式时间算法的良好组合特性。
   • 和 (Addition)：两个多项式时间算法顺序执行，总时间是两者之和，结果仍然是多项式时间。
   • 积 (Multiplication)：一个多项式时间的循环，其内部再执行一个多项式时间的操作，总时间是两者之积，结果仍然是多项式时间。
   • 复合 (Composition)：一个多项式时间的算法，其输入是另一个多项式时间算法的输出，总时间是函数的复合，结果仍然是多项式时间。这在归约（后面会讲）中非常重要。
4. 使用许可：作者允许我们直接使用这些封闭性质，无需每次都重新证明，这大大简化了后续的复杂性分析。

这是讲义的核心章节标题，预示着本章将介绍计算机科学领域最核心、最著名的两个复杂性类：P 和 NP。这个标题将整个讨论从基础定义（时间复杂性，大O）提升到了对重大理论概念的探讨。P vs NP 问题是计算机科学中最重要、悬而未决的百万美元大奖问题。本章将分别定义它们，并为后续讨论它们之间的关系打下基础。

这是“P 和 NP”章节下的一个小节标题，表示将首先开始详细定义和讨论复杂性类 P。

这个定义正式引入了复杂性类 P。

1. 第一种定义（描述性）：
   • $\mathrm{P}$ 是一个语言的集合（一个复杂性类）。
   • 一个语言 $L$ 属于 P，条件是：存在一个确定性图灵机（decider） $M$ 能够判决 $L$，并且这个 $M$ 的运行时间是多项式时间。
   • “多项式时间”的含义是，存在某个常数 $k$，使得 $M$ 的运行时间是 $O(n^k)$。
   • 简而言之，P 包含了所有可以被确定性算法在多项式时间内“高效”解决的问题。
2. 第二种定义（数学化）：
   • $\mathrm{P}$ 是所有 $\operatorname{Time}(n^k)$ 复杂性类的并集。
   • $k$ 取遍所有自然数 $N=\{0, 1, 2, \dots\}$。
   • $\operatorname{Time}(n^0)$, $\operatorname{Time}(n^1)$, $\operatorname{Time}(n^2)$, $\operatorname{Time}(n^3)$, ... 把所有这些复杂性类里的语言都倒进一个大篮子里，这个大篮子就是 P。
   • 这个定义更精确地表达了“存在某个常数 $k$”的含义。只要你能找到任何一个 $k$ 使得问题能在 $O(n^k)$ 时间解决，那它就属于 P。

这段提供了一个标准的、结构化的方法来证明一个问题（语言 $L$）是属于复杂性类 P 的。

1. 步骤 1: 描述算法。首先，你必须设计一个具体的、一步一步的确定性算法（用伪代码描述就足够了）。这个算法的输入是问题的一个实例 $x$。
2. 步骤 2: 证明完备性 (Completeness)。你必须证明，对于任何一个“是”的实例（即 $x \in L$），你的算法总能正确地输出“接受”。这保证了你的算法不会漏掉任何正确的解。
3. 步骤 3: 证明可靠性 (Soundness)。你必须证明，对于任何一个“否”的实例（即 $x \notin L$），你的算法总能正确地输出“拒绝”。这保证了你的算法不会把不是解的误判为解。步骤2和3合起来证明了你的算法是“正确”的。
4. 步骤 4: 证明效率。最后，也是最关键的一步，你必须分析你的算法的运行时间，并证明它是多项式时间的。也就是说，它的运行时间是 $O(n^k)$，其中 $n$ 是输入 $x$ 的长度，$k$ 是某个常数。这一步证明了你的算法是“高效”的。

同时满足这四点，就严格地证明了 $L \in \mathrm{P}$。

这一段开始介绍复杂性类 NP，首先从它的计算模型——非确定性图灵机 (Nondeterministic Turing Machine, NTM)——开始。

1. 与确定性的区别：确定性图灵机 (DTM) 在任何时刻，根据当前状态和读到的符号，下一步的动作是唯一确定的。而 NTM 在同样的情况下，可能有多种选择。
2. “非确定性”的含义：它不是指随机，而是指“多分叉的可能性”。你可以把 NTM 的计算过程想象成一棵树，每个节点代表一个机器状态，每条树枝代表一个可能的转换。DTM 的计算是一条单一的路径，而 NTM 的计算是探索一整棵树。
3. 转换函数的形式化：
   • DTM 的转换函数 $\delta(q, a) = (q', a', d)$ 返回一个元组，表示下一个状态、要写入的符号和移动方向。
   • NTM 的转换函数 $\delta(q, a)$ 返回一个集合，这个集合里包含多个可能的元组。例如 $\delta(q_1, 'a') = \{ (q_2, 'b', R), (q_3, 'a', L) \}$，意味着在 $q_1$ 状态读到 'a' 时，机器可以变成 $q_2$ 状态、写入 'b' 并右移，或者可以变成 $q_3$ 状态、写入 'a' 并左移。
   • $\mathcal{P}(\dots)$ 表示幂集 (Power Set)，即所有子集的集合。返回一个转换元组的集合，就意味着可以选择其中任何一个来执行。

这部分定义了 NTM 如何“判决”一个语言以及如何衡量其运行时间，这两点都与 DTM 有着微妙但关键的区别。

NTM 的判决规则：

1. 停机要求：首先，NTM 必须是一个判决器，意味着在任何输入上，沿着任何计算分支，都必须在有限步内停机。不能有无限循环的分支。
2. 接受条件 (Asymmetry)：
   • 对于属于 L 的输入 ($x \in L$)：只需要至少存在一个计算分支（一条“幸运”的路径）最终到达“接受”状态。
   • 对于不属于 L 的输入 ($x \notin L$)：所有的计算分支都必须最终到达“拒绝”状态。
3. “猜测与验证”模型：这个不对称的接受规则完美地诠释了“猜测并验证”的模式。NTM 首先“猜测”一个可能的解（通过一系列非确定性选择），然后沿着这个分支的剩余部分“验证”这个猜测是否正确。如果 $x \in L$，那么至少存在一个正确的“解”可以被猜到并验证成功。如果 $x \notin L$，那么任何“猜测”都无法通过验证。

NTM 的运行时间定义 (定义 5)：

1. 最长路径决定：NTM 的计算是一棵树，运行时间 $t(n)$ 不是由接受路径的长度决定的，而是由这棵树的深度决定的。
2. 最坏情况中的最坏情况：和 DTM 一样，NTM 的运行时间也是一个最坏情况的度量。它是指，在所有长度为 $n$ 的输入中，那个能产生最深的计算树的输入的树深。
3. 接受与时间的对比：
   • 接受: 是“最好情况”逻辑——只要有一个分支接受就算接受。
   • 时间: 是“最坏情况”逻辑——必须等到所有分支（即使是那些最终拒绝的）都停机，取其中最长的时间。

这两个定义完全仿照 P 的定义方式，但把计算模型从确定性图灵机 (DTM) 换成了非确定性图灵机 (NTM)。

定义 6 (NTIME(t(n))):

• 这是一个非确定性时间复杂性类。
• 它是一个语言的集合。
• 一个语言 $L$ 属于 $\operatorname{NTIME}(t(n))$，当且仅当存在一个非确定性图灵机 (NTM) 能够在 $O(t(n))$ 的时间内判决它。
• 这个定义与 $\operatorname{Time}(t(n))$ 的唯一区别就是把 "Turing machine" 换成了 "non-deterministic Turing machine"。

定义 7 (NP):

• NP 的全称是 Nondeterministic Polynomial time（非确定性多项式时间）。
• 描述性定义: NP 是所有可以被一个非确定性图灵机 (NTM) 在多项式时间内判决的语言的集合。
• 数学化定义: NP 是所有非确定性多项式时间复杂性类的并集。即 $\mathrm{NP} = \mathrm{NTIME}(n^0) \cup \mathrm{NTIME}(n^1) \cup \mathrm{NTIME}(n^2) \cup \dots$。
• 这个定义与 P 的定义在结构上是平行的，唯一的区别就是把 $\operatorname{Time}$ 换成了 $\operatorname{NTIME}$。

这个模板提供了使用 NTM 定义来证明一个语言 $L$ 属于 NP 的标准流程。它和证明 $L \in \mathrm{P}$ 的模板非常相似，但核心区别在于算法的性质（非确定性）和正确性证明的逻辑（存在性 vs. 普遍性）。

1. 步骤 1: 设计 NTM 算法。你需要描述一个非确定性算法。这个算法的核心通常是“猜测”一个潜在的解。伪代码中需要明确指出哪些步骤是非确定性的。
2. 步骤 2: 证明完备性 (“是”的情况)。你必须证明，如果输入 $x$ 是一个“是”实例（$x \in L$），那么至少存在一条“幸运”的非确定性选择路径，能引导算法最终接受 $x$。这通常对应于“猜中”了那个能证明 $x \in L$ 的解。
3. 步骤 3: 证明可靠性 (“否”的情况)。你必须证明，如果输入 $x$ 是一个“否”实例（$x \notin L$），那么无论非确定性步骤做出何种选择，算法的每一条可能路径都必须最终拒绝 $x$。这保证了算法不会接受一个不该接受的输入。
4. 步骤 4: 证明效率。你必须分析 NTM 的运行时间。根据定义，这指的是其最长计算路径的长度（即计算树的深度）。你必须证明这个最长路径的长度是输入长度 $n$ 的多项式，即 $O(n^k)$。

这个例子应用了“模板2”来证明一个著名的问题——3-着色问题 (3-COLORING)——属于 NP。

1. 问题定义:
   • 输入: 一个图 $G=(V, E)$，其中 $V$ 是顶点集，E 是边集。
   • 问题: 是否能用三种颜色（比如红、绿、蓝）给图中的每个顶点着色，使得任意一条边的两个端点颜色都不同？
2. 应用模板2:
   • 步骤 1 (NTM 伪代码): 算法分为两阶段：
   • 猜测阶段: 遍历图中的每一个顶点 $v$。对于每个 $v$，非确定性地从 {红, 绿, 蓝} 中选择一个颜色赋给它。当所有顶点都赋完颜色后，我们就“猜测”出了一种完整的着色方案。
   • 验证阶段: 遍历图中的每一条边 $(u,v)$。检查 $u$ 和 $v$ 的颜色。如果发现它们的颜色相同，则说明这个着色方案是无效的，立即拒绝。如果检查完所有边都没有发现冲突，说明这是一个有效的 3-着色，接受。
   • 步骤 2 (完备性证明): 文中解释：“如果图存在 3-着色 $C$，那么存在某个非确定性分支，图灵机将此着色分配给顶点并因此接受。” 这句话的意思是，在猜测阶段，那条“幸运”的、恰好猜出正确着色方案 $C$ 的计算路径是存在的。当算法沿着这条路径执行时，验证阶段不会发现任何冲突，因此会接受。
   • 步骤 3 (可靠性证明): 文中解释：“如果输入是一个图，但不存在 3-着色，那么图灵机永远不会接受。” 这是因为，对于猜测阶段产生的所有可能的着色方案（每一个方案都是一条计算路径），它们没有一个是有效的 3-着色。因此，对于任何一个着色方案，验证阶段都必然能至少找到一条边 $(u,v)$，其两端颜色相同，从而导致该路径被拒绝。既然所有路径都被拒绝，NTM 作为一个整体就拒绝该输入。
   • 步骤 4 (效率分析):
   • 猜测阶段: 有 $|V|$ 个顶点，对每个顶点做一次 3 选 1 的非确定性选择。这个过程的路径长度是 $O(|V|)$。
   • 验证阶段: 有 $|E|$ 条边。对于每条边，需要查找其两个端点的颜色并比较。查找颜色可能需要 $O(|V|)$（如果颜色存储在列表中）或者 $O(1)$（如果用哈希表或数组）。假设是 $O(|V|)$，则总验证时间是 $O(|V| \cdot |E|)$。这是一个关于输入规模的多项式。（原文中分析 “$|V|*|E|$” 有些夸大，更精确的分析是 $O(|E|)$，假定颜色可以快速访问）。无论如何，这显然是多项式时间。
3. 结论: 既然 3-着色问题满足了模板2的所有条件，因此它属于 NP。

这一段从一个更直观、更实用的角度重新定义了 NP，即通过“验证器” (Verifier) 的概念。

1. 核心思想的转换：我们不再谈论神奇的“非确定性图灵机”，而是回到了我们更熟悉的“确定性算法”。但这个算法的任务不是从头解决问题，而是“验证一个解”。
2. 验证器的角色:
   • 一个验证器 $V$ 是一个确定性的算法。
   • 它接受两个输入：原始问题实例 $x$ 和一个所谓的“证书” (certificate) $c$。
   • 这个证书 $c$ 就像是宣称“$x$ 属于 $L$”的一个“证据”或“证明”。
3. 验证器的逻辑 (定义 8)：
   • $x \in L \leftrightarrow \exists c \text { such that } V(x, c) \text { accepts.}$
   • 这句话是双向的：
   • ($\rightarrow$) 如果 $x \in L$: 那么必须存在至少一个证书 $c$，当你把 $(x, c)$ 一起喂给验证器 $V$ 时，$V$ 会输出“接受”。这个 $c$ 就是 $x \in L$ 的“证据”。
   • ($\leftarrow$) 如果存在一个证书 $c$ 使得 $V(x,c)$ 接受: 那么我们就可以断定 $x \in L$。
   • 推论: 如果 $x \notin L$，那么对于所有可能的证书 $c$，$V(x, c)$ 都必须输出“拒绝”。任何伪造的“证据”都无法通过验证。
4. 多项式时间验证器:
   • NP 的关键在于这个验证过程必须是“高效”的。
   • 一个验证器被称为多项式时间验证器，如果它的运行时间是关于原始输入 $x$ 长度的多项式，即 $O(|x|^k)$。
5. 证书的长度:
   • 一个重要的隐含条件是，证书 $c$ 本身的长度也必须是 $|x|$ 的多项式。
   • 原因很简单：如果证书是指数级长度，验证器光是把它读一遍就需要指数时间，那它就不可能是多项式时间验证器了。

这部分是讲义的引言。作者 William Pires 首先明确了这份讲义的目的和内容。

1. 目的：这份讲义旨在提供一些在课堂上可能被提及但没有详细证明的理论主张的完整证明。这在理论课程中很常见，因为课堂时间有限，无法深入每一个细节。讲义作为补充材料，让学生可以深入研究。
2. 内容：讲义包含了一些关键主张的证明。
3. 学习建议：作者建议学生将阅读和理解这些证明，甚至尝试自己独立推导它们，作为一种学习练习。这有助于加深对概念的理解，而不仅仅是记忆结论。
4. 范围说明：作者强调，学生的考试或课程要求范围仅限于课堂上讲授的内容。这份讲义是可选的补充学习材料，但对深入理解非常有益。
5. 后续内容预告：引言最后提到，讲义的后半部分内容可能会在未来的讲座中进行讲解，这暗示了讲义内容的重要性以及与课程进度的衔接。

这一段引入了计算复杂性理论的核心概念之一：时间复杂性。

1. 基本设定：我们从一个理论计算模型——图灵机 $M$ 开始。这个图灵机被设计用来“判决”一个语言 $L$。“判决”（decide）一个语言意味着对于任何给定的字符串，图灵机总能在有限的时间内停机，并明确地回答“是”（接受）或“否”（拒绝）。“是”表示该字符串属于语言 $L$，“否”则表示不属于。
2. 核心问题：我们关心的不仅仅是图灵机 能否 解决问题，更关心它解决问题需要 多长时间。这个“多长时间”就是时间复杂性要研究的对象。
3. 衡量标准：时间不是用秒或分钟来衡量的，因为那取决于具体的计算机硬件。在理论计算机科学中，时间是用图灵机执行的“步骤”数来衡量的。一个步骤通常指一次状态转换。
4. 输入的角色：解决一个问题的耗时通常不固定，它依赖于问题的“规模”。对于图灵机来说，问题的规模就是输入字符串 $x$ 的长度，记为 $|x|$。输入越长，通常处理时间也越长。
5. 函数关系：因此，我们不讨论某个具体输入的运行时间，而是将运行时间看作是输入长度 $n$ 的一个函数。这个函数描述了运行时间随着输入长度增长的变化趋势。

这个定义精确地形式化了上一段引入的“运行时间函数”的概念。

1. 前提条件：这个定义只适用于“在每个输入上都停机”的图灵机。这种图灵机也叫判决器 (decider)。如果一个图灵机在某些输入上会无限循环，那么它的运行时间就是无限，这个定义就没意义了。
2. 运行时间的记号：运行时间函数通常用 $t(n)$ 表示，其中 $n$ 是输入长度。
3. 核心思想：最坏情况分析 (Worst-Case Analysis)：定义中的 max 是关键。对于所有长度为 $n$ 的输入字符串，它们的实际运行步数可能各不相同。$t(n)$ 取的是这些步数中的“最大值”。这意味着我们总是在为最坏的情况做准备。无论你给我哪个长度为 $n$ 的输入，我都能保证在 $t(n)$ 步之内解决它。
4. 形式化定义：
   • $t(n) :=$ 这是定义 $t(n)$ 的符号。
   • $\max_{x \in \Sigma^{*},|x|=n}$：这部分是说，我们要考虑所有可能的、长度为 $n$ 的输入字符串 $x$。$\Sigma^{*}$ 表示由字母表 $\Sigma$ 中所有符号组成的所有有限长度字符串的集合。
   • number of steps M takes before it halts on x：这是对单个输入 $x$ 的运行步数。
5. 步骤的定义：一段补充说明，明确了“步骤数”就是图灵机从开始到停机所执行的状态转换的总次数。

这一段解释了为什么我们需要以及如何使用大O符号 (Big O Notation)。

1. 动机：精确计算 $t(n)$，比如 $t(n) = 5n^2 + 10n + 3$，是非常繁琐且不必要的。我们更关心的是当输入规模 $n$ 变得非常大时，运行时间的“增长趋势”或“数量级”。是像 $n$ (线性)，还是像 $n^2$ (平方)，或是像 $2^n$ (指数)？
2. 大 O 的作用：大O符号提供了一种标准的方式来忽略那些在 $n$ 很大时变得不重要的部分（低阶项和常数系数），而只关注起主导作用的部分。它描述了函数增长的“上界”。
3. 形式化定义：$f(n) = O(g(n))$ 这句话的含义是“函数 $f(n)$ 的增长速度不会比函数 $g(n)$ 快太多”。
   • 前提：有两个从自然数（$\mathbb{N}$）映射到正实数（$\mathbb{R}^{+}$）的函数 $f$ 和 $g$。在我们的场景中，$f(n)$ 就是运行时间 $t(n)$。
   • 条件：要满足 $f(n) = O(g(n))$，必须能找到两个常数：一个正的比例因子 $c$ 和一个起始点 $n_0$。
   • 核心不等式：对于所有大于等于这个起始点 $n_0$ 的 $n$，不等式 $f(n) \leq c \cdot g(n)$ 必须恒成立。这意味着，从 $n_0$ 开始，$f(n)$ 的曲线总是在 $c \cdot g(n)$ 曲线的下方（或与之重合）。

这个定义利用大O符号将具有相似运行时间的语言（或问题）归为一类，这个“类”就是复杂性类。

1. 什么是复杂性类：复杂性类是一个“装语言的篮子”。所有能被某种特定资源限制（比如时间或空间）的计算模型解决的语言，都被放进同一个篮子里。
2. TIME(t(n)) 的定义：这个特定的篮子叫做 $\operatorname{Time}(t(n))$。它装的是所有那些“可以被一个运行时间为 $O(t(n))$ 的图灵机判决”的语言。
3. 展开定义：一个语言 $L$ 属于 $\operatorname{Time}(t(n))$，当且仅当：
   • 存在一个图灵机 $M$ 能够判决 $L$。
   • 这个图灵机 $M$ 的运行时间是 $O(t(n))$。根据大O定义，这意味着存在常数 $c$ 和 $n_0$，使得对于所有长度 $n \geq n_0$ 的输入，$M$ 的最坏情况运行步数不超过 $c \cdot t(n)$。
4. 对计算模型的敏感性：这是一个非常重要的理论细节。$\operatorname{Time}(t(n))$ 的确切内容取决于你用的是哪种图灵机。例如，一个问题用“多带图灵机”可能在 $O(n)$ 时间解决，但用“单带图灵机”可能需要 $O(n^2)$ 时间。这意味着同一个语言 $L$ 可能属于多带图灵机的 $\operatorname{Time}(n)$，但属于单带图灵机的 $\operatorname{Time}(n^2)$。
5. P 的优越性：作者提前剧透，后续将要定义的复杂性类 P（多项式时间）有一个非常好的特性，就是它对这些常见的确定性计算模型不敏感。一个问题在多带图灵机上是多项式时间可解的，那么在单带图灵机上也是（尽管多项式的次数可能会增加）。这使得我们可以忽略底层模型的细节，直接用更方便的伪代码来讨论算法，只要能证明它是多项式时间的就行。

这段内容定义了什么是“多项式”时间，并列举了它的关键性质。这是区分“高效”算法和“低效”算法的核心分界线。

1. 多项式的定义：一个函数 $f(n)$ 被认为是多项式的，如果它的增长速度被某个 $n^k$ 函数所限制。换句话说，它的大O表示是 $O(n^k)$，其中 $k$ 是一个固定的常数，与 $n$ 无关。
2. 示例分析：
   • $n^5 + 1000$：是 $O(n^5)$，因为当 $n$ 很大时，$n^5$ 项占主导。这里的 $k=5$，所以它是多项式的。
   • $\log(n)$：对数函数的增长比任何 $n^k$（只要 $k>0$）都要慢。例如，$\log(n) = O(n^1)$。所以它也是多项式的。这是一个需要注意的点，比多项式增长慢的函数也算在多项式时间的范畴里。
   • $2^n + n^3$：这是一个指数函数。无论你选择多大的常数 $k$，当 $n$ 足够大时，$2^n$ 的增长最终都会超过 $n^k$。因此，$2^n$ 不是 $O(n^k)$，这个函数不是多项式的。
3. 多项式的封闭性 (Closure Properties)：这部分是“好消息”，因为它说明了多项式时间算法的良好组合特性。
   • 和 (Addition)：两个多项式时间算法顺序执行，总时间是两者之和，结果仍然是多项式时间。
   • 积 (Multiplication)：一个多项式时间的循环，其内部再执行一个多项式时间的操作，总时间是两者之积，结果仍然是多项式时间。
   • 复合 (Composition)：一个多项式时间的算法，其输入是另一个多项式时间算法的输出，总时间是函数的复合，结果仍然是多项式时间。这在归约（后面会讲）中非常重要。
4. 使用许可：作者允许我们直接使用这些封闭性质，无需每次都重新证明，这大大简化了后续的复杂性分析。

这是讲义的核心章节标题，预示着本章将介绍计算机科学领域最核心、最著名的两个复杂性类：P 和 NP。这个标题将整个讨论从基础定义（时间复杂性，大O）提升到了对重大理论概念的探讨。P vs NP 问题是计算机科学中最重要、悬而未决的百万美元大奖问题。本章将分别定义它们，并为后续讨论它们之间的关系打下基础。

这是“P 和 NP”章节下的一个小节标题，表示将首先开始详细定义和讨论复杂性类 P。

这个定义正式引入了复杂性类 P。

1. 第一种定义（描述性）：
   • $\mathrm{P}$ 是一个语言的集合（一个复杂性类）。
   • 一个语言 $L$ 属于 P，条件是：存在一个确定性图灵机（decider） $M$ 能够判决 $L$，并且这个 $M$ 的运行时间是多项式时间。
   • “多项式时间”的含义是，存在某个常数 $k$，使得 $M$ 的运行时间是 $O(n^k)$。
   • 简而言之，P 包含了所有可以被确定性算法在多项式时间内“高效”解决的问题。
2. 第二种定义（数学化）：
   • $\mathrm{P}$ 是所有 $\operatorname{Time}(n^k)$ 复杂性类的并集。
   • $k$ 取遍所有自然数 $N=\{0, 1, 2, \dots\}$。
   • $\operatorname{Time}(n^0)$, $\operatorname{Time}(n^1)$, $\operatorname{Time}(n^2)$, $\operatorname{Time}(n^3)$, ... 把所有这些复杂性类里的语言都倒进一个大篮子里，这个大篮子就是 P。
   • 这个定义更精确地表达了“存在某个常数 $k$”的含义。只要你能找到任何一个 $k$ 使得问题能在 $O(n^k)$ 时间解决，那它就属于 P。

这段提供了一个标准的、结构化的方法来证明一个问题（语言 $L$）是属于复杂性类 P 的。

1. 步骤 1: 描述算法。首先，你必须设计一个具体的、一步一步的确定性算法（用伪代码描述就足够了）。这个算法的输入是问题的一个实例 $x$。
2. 步骤 2: 证明完备性 (Completeness)。你必须证明，对于任何一个“是”的实例（即 $x \in L$），你的算法总能正确地输出“接受”。这保证了你的算法不会漏掉任何正确的解。
3. 步骤 3: 证明可靠性 (Soundness)。你必须证明，对于任何一个“否”的实例（即 $x \notin L$），你的算法总能正确地输出“拒绝”。这保证了你的算法不会把不是解的误判为解。步骤2和3合起来证明了你的算法是“正确”的。
4. 步骤 4: 证明效率。最后，也是最关键的一步，你必须分析你的算法的运行时间，并证明它是多项式时间的。也就是说，它的运行时间是 $O(n^k)$，其中 $n$ 是输入 $x$ 的长度，$k$ 是某个常数。这一步证明了你的算法是“高效”的。

同时满足这四点，就严格地证明了 $L \in \mathrm{P}$。

这一段开始介绍复杂性类 NP，首先从它的计算模型——非确定性图灵机 (Nondeterministic Turing Machine, NTM)——开始。

1. 与确定性的区别：确定性图灵机 (DTM) 在任何时刻，根据当前状态和读到的符号，下一步的动作是唯一确定的。而 NTM 在同样的情况下，可能有多种选择。
2. “非确定性”的含义：它不是指随机，而是指“多分叉的可能性”。你可以把 NTM 的计算过程想象成一棵树，每个节点代表一个机器状态，每条树枝代表一个可能的转换。DTM 的计算是一条单一的路径，而 NTM 的计算是探索一整棵树。
3. 转换函数的形式化：
   • DTM 的转换函数 $\delta(q, a) = (q', a', d)$ 返回一个元组，表示下一个状态、要写入的符号和移动方向。
   • NTM 的转换函数 $\delta(q, a)$ 返回一个集合，这个集合里包含多个可能的元组。例如 $\delta(q_1, 'a') = \{ (q_2, 'b', R), (q_3, 'a', L) \}$，意味着在 $q_1$ 状态读到 'a' 时，机器可以变成 $q_2$ 状态、写入 'b' 并右移，或者可以变成 $q_3$ 状态、写入 'a' 并左移。
   • $\mathcal{P}(\dots)$ 表示幂集 (Power Set)，即所有子集的集合。返回一个转换元组的集合，就意味着可以选择其中任何一个来执行。

这部分定义了 NTM 如何“判决”一个语言以及如何衡量其运行时间，这两点都与 DTM 有着微妙但关键的区别。

NTM 的判决规则：

1. 停机要求：首先，NTM 必须是一个判决器，意味着在任何输入上，沿着任何计算分支，都必须在有限步内停机。不能有无限循环的分支。
2. 接受条件 (Asymmetry)：
   • 对于属于 L 的输入 ($x \in L$)：只需要至少存在一个计算分支（一条“幸运”的路径）最终到达“接受”状态。
   • 对于不属于 L 的输入 ($x \notin L$)：所有的计算分支都必须最终到达“拒绝”状态。
3. “猜测与验证”模型：这个不对称的接受规则完美地诠释了“猜测并验证”的模式。NTM 首先“猜测”一个可能的解（通过一系列非确定性选择），然后沿着这个分支的剩余部分“验证”这个猜测是否正确。如果 $x \in L$，那么至少存在一个正确的“解”可以被猜到并验证成功。如果 $x \notin L$，那么任何“猜测”都无法通过验证。

NTM 的运行时间定义 (定义 5)：

1. 最长路径决定：NTM 的计算是一棵树，运行时间 $t(n)$ 不是由接受路径的长度决定的，而是由这棵树的深度决定的。
2. 最坏情况中的最坏情况：和 DTM 一样，NTM 的运行时间也是一个最坏情况的度量。它是指，在所有长度为 $n$ 的输入中，那个能产生最深的计算树的输入的树深。
3. 接受与时间的对比：
   • 接受: 是“最好情况”逻辑——只要有一个分支接受就算接受。
   • 时间: 是“最坏情况”逻辑——必须等到所有分支（即使是那些最终拒绝的）都停机，取其中最长的时间。

这两个定义完全仿照 P 的定义方式，但把计算模型从确定性图灵机 (DTM) 换成了非确定性图灵机 (NTM)。

定义 6 (NTIME(t(n))):

• 这是一个非确定性时间复杂性类。
• 它是一个语言的集合。
• 一个语言 $L$ 属于 $\operatorname{NTIME}(t(n))$，当且仅当存在一个非确定性图灵机 (NTM) 能够在 $O(t(n))$ 的时间内判决它。
• 这个定义与 $\operatorname{Time}(t(n))$ 的唯一区别就是把 "Turing machine" 换成了 "non-deterministic Turing machine"。

定义 7 (NP):

• NP 的全称是 Nondeterministic Polynomial time（非确定性多项式时间）。
• 描述性定义: NP 是所有可以被一个非确定性图灵机 (NTM) 在多项式时间内判决的语言的集合。
• 数学化定义: NP 是所有非确定性多项式时间复杂性类的并集。即 $\mathrm{NP} = \mathrm{NTIME}(n^0) \cup \mathrm{NTIME}(n^1) \cup \mathrm{NTIME}(n^2) \cup \dots$。
• 这个定义与 P 的定义在结构上是平行的，唯一的区别就是把 $\operatorname{Time}$ 换成了 $\operatorname{NTIME}$。

这个模板提供了使用 NTM 定义来证明一个语言 $L$ 属于 NP 的标准流程。它和证明 $L \in \mathrm{P}$ 的模板非常相似，但核心区别在于算法的性质（非确定性）和正确性证明的逻辑（存在性 vs. 普遍性）。

1. 步骤 1: 设计 NTM 算法。你需要描述一个非确定性算法。这个算法的核心通常是“猜测”一个潜在的解。伪代码中需要明确指出哪些步骤是非确定性的。
2. 步骤 2: 证明完备性 (“是”的情况)。你必须证明，如果输入 $x$ 是一个“是”实例（$x \in L$），那么至少存在一条“幸运”的非确定性选择路径，能引导算法最终接受 $x$。这通常对应于“猜中”了那个能证明 $x \in L$ 的解。
3. 步骤 3: 证明可靠性 (“否”的情况)。你必须证明，如果输入 $x$ 是一个“否”实例（$x \notin L$），那么无论非确定性步骤做出何种选择，算法的每一条可能路径都必须最终拒绝 $x$。这保证了算法不会接受一个不该接受的输入。
4. 步骤 4: 证明效率。你必须分析 NTM 的运行时间。根据定义，这指的是其最长计算路径的长度（即计算树的深度）。你必须证明这个最长路径的长度是输入长度 $n$ 的多项式，即 $O(n^k)$。

这个例子应用了“模板2”来证明一个著名的问题——3-着色问题 (3-COLORING)——属于 NP。

1. 问题定义:
   • 输入: 一个图 $G=(V, E)$，其中 $V$ 是顶点集，E 是边集。
   • 问题: 是否能用三种颜色（比如红、绿、蓝）给图中的每个顶点着色，使得任意一条边的两个端点颜色都不同？
2. 应用模板2:
   • 步骤 1 (NTM 伪代码): 算法分为两阶段：
   • 猜测阶段: 遍历图中的每一个顶点 $v$。对于每个 $v$，非确定性地从 {红, 绿, 蓝} 中选择一个颜色赋给它。当所有顶点都赋完颜色后，我们就“猜测”出了一种完整的着色方案。
   • 验证阶段: 遍历图中的每一条边 $(u,v)$。检查 $u$ 和 $v$ 的颜色。如果发现它们的颜色相同，则说明这个着色方案是无效的，立即拒绝。如果检查完所有边都没有发现冲突，说明这是一个有效的 3-着色，接受。
   • 步骤 2 (完备性证明): 文中解释：“如果图存在 3-着色 $C$，那么存在某个非确定性分支，图灵机将此着色分配给顶点并因此接受。” 这句话的意思是，在猜测阶段，那条“幸运”的、恰好猜出正确着色方案 $C$ 的计算路径是存在的。当算法沿着这条路径执行时，验证阶段不会发现任何冲突，因此会接受。
   • 步骤 3 (可靠性证明): 文中解释：“如果输入是一个图，但不存在 3-着色，那么图灵机永远不会接受。” 这是因为，对于猜测阶段产生的所有可能的着色方案（每一个方案都是一条计算路径），它们没有一个是有效的 3-着色。因此，对于任何一个着色方案，验证阶段都必然能至少找到一条边 $(u,v)$，其两端颜色相同，从而导致该路径被拒绝。既然所有路径都被拒绝，NTM 作为一个整体就拒绝该输入。
   • 步骤 4 (效率分析):
   • 猜测阶段: 有 $|V|$ 个顶点，对每个顶点做一次 3 选 1 的非确定性选择。这个过程的路径长度是 $O(|V|)$。
   • 验证阶段: 有 $|E|$ 条边。对于每条边，需要查找其两个端点的颜色并比较。查找颜色的时间取决于实现，如果用数组或哈希表，是 $O(1)$。总验证时间是 $O(|E|)$。因此总时间是 $O(|V| + |E|)$，这是一个多项式时间。原文的 $|V|*|E|$ 是一个宽松但正确的上界。
3. 结论: 既然 3-着色问题满足了模板2的所有条件，因此它属于 NP。

这一段从一个更直观、更实用的角度重新定义了 NP，即通过“验证器” (Verifier) 的概念。

1. 核心思想的转换：我们不再谈论神奇的“非确定性图灵机”，而是回到了我们更熟悉的“确定性算法”。但这个算法的任务不是从头解决问题，而是“验证一个解”。
2. 验证器的角色:
   • 一个验证器 $V$ 是一个确定性的算法。
   • 它接受两个输入：原始问题实例 $x$ 和一个所谓的“证书” (certificate) $c$。
   • 这个证书 $c$ 就像是宣称“$x$ 属于 $L$”的一个“证据”或“证明”。
3. 验证器的逻辑 (定义 8)：
   • $x \in L \leftrightarrow \exists c \text { such that } V(x, c) \text { accepts.}$
   • 这句话是双向的：
   • ($\rightarrow$) 如果 $x \in L$: 那么必须存在至少一个证书 $c$，当你把 $(x, c)$ 一起喂给验证器 $V$ 时，$V$ 会输出“接受”。这个 $c$ 就是 $x \in L$ 的“证据”。
   • ($\leftarrow$) 如果存在一个证书 $c$ 使得 $V(x,c)$ 接受: 那么我们就可以断定 $x \in L$。
   • 推论: 如果 $x \notin L$，那么对于所有可能的证书 $c$，$V(x, c)$ 都必须输出“拒绝”。任何伪造的“证据”都无法通过验证。
4. 多项式时间验证器:
   • NP 的关键在于这个验证过程必须是“高效”的。
   • 一个验证器被称为多项式时间验证器，如果它的运行时间是关于原始输入 $x$ 长度的多项式，即 $O(|x|^k)$。
5. 证书的长度:
   • 一个重要的隐含条件是，证书 $c$ 本身的长度也必须是 $|x|$ 的多项式。
   • 原因很简单：如果证书是指数级长度，验证器光是把它读一遍就需要指数时间，那它就不可能是多项式时间验证器了。

这段内容提供了使用验证器模型来证明一个语言 $L$ 属于 NP 的标准模板，并立即用 3-着色问题作为示例进行了演示。

证明模板 3 的步骤：

1. 定义证书并设计验证器: 首先，你要想清楚，对于这个问题，一个“解”或者“证据”（即证书 $c$）应该长什么样。然后设计一个接收问题实例 $x$ 和证书 $c$ 的确定性算法 $V$。
2. 证明完备性: 证明对于任何“是”实例 $x \in L$，都确实存在一个对应的“好”证书 $c$，能让你的验证器 $V$ 接受。
3. 证明可靠性: 证明对于任何“否”实例 $x \notin L$，无论提供什么样的“坏”证书 $c$（甚至是伪造的证据），你的验证器 $V$ 都绝不会接受，总能发现问题并拒绝。
4. 证明效率: 分析验证器 $V$ 的运行时间，确保它是关于原始输入 $|x|$ 的多项式时间。同时要确保你定义的证书 $c$ 的长度也是多项式的。

示例 2: 3-着色问题的验证器

1. 定义证书和验证器:
   • 问题实例 x: 图 $\langle V, E \rangle$。
   • 证书 c: 一个具体的着色方案 $C$。它可以是一个列表或哈希表，将每个顶点映射到一种颜色 {r, g, b}。
   • 验证器 V (算法2):
   • 接收图 $\langle V, E \rangle$ 和着色方案 $C$。
   • 遍历图中所有的边 $(u, v)$。
   • 对于每一条边，根据 $C$ 查找 $u$ 和 $v$ 的颜色。
   • 如果颜色相同，立即停止并拒绝。
   • 如果所有边都检查完毕，没有发现冲突，则接受。
2. 完备性: 文中已解释。如果图是可 3-着色的，那么一个正确的着色方案 $C$ 就是存在的。将这个 $C$ 作为证书提供给验证器，验证器检查所有边都不会发现冲突，因此会接受。
3. 可靠性: 文中已解释。如果图不可 3-着色，那么任何一个给定的着色方案 $C$ 都必然是错误的。错误意味着至少有一条边的两个端点颜色相同。验证器在遍历边的过程中必然会检查到这条冲突的边，并因此拒绝。所以，没有证书能骗过验证器。
4. 效率:
   • 证书长度: 方案 $C$ 需要记录 $|V|$ 个顶点的颜色，其长度是 $O(|V|)$，是多项式的。
   • 运行时间:
   • 算法遍历 $|E|$ 条边。
   • 对于每条边，查找两个顶点的颜色。原文分析说这需要 $O(|V|)$，所以总时间是 $O(|V| \cdot |E|)$。这是一个多项式。
   • (更精细的分析：如果着色方案 $C$ 是一个以顶点 ID 为索引的数组，查找颜色是 $O(1)$。那么总时间就是 $O(|E|)$，这仍然是多项式的。)
   • 结论是正确的：验证器在多项式时间内运行。

结论: 3-着色问题满足验证器定义的所有条件，因此它属于 NP。

这段内容陈述了一个非常重要的结论：基于非确定性图灵机 (NTM) 的 NP 定义，和基于多项式时间验证器的 NP 定义，是完全等价的。并简要说明了两者之间相互转换的核心思想。

定理 1: 这句话是验证器定义的重申，但在这里它被提升为“定理”，强调其与 NTM 定义的等价地位。

证明思路 (双向转换):

1. 从 NTM 到 验证器 (NTM $\Rightarrow$ Verifier):
   • 假设我们有一个多项式时间 NTM $M$ 用于判决语言 $L$。
   • 我们如何构造一个验证器 $V$？
   • 证书 $c$: 如果一个输入 $x \in L$，那么必然存在一条“幸运”的计算路径（一系列非确定性选择）导致 $M$ 接受。这个证书 $c$ 就是对这条路径的描述。例如，$c$ 可以是一个字符串 "21132..."，表示在第1个选择点选第2个分支，第2个选择点选第1个分支，...
   • 验证器 $V(x, c)$ 的工作:
   • 效率: NTM 的运行时间是多项式 $p(|x|)$。这意味着证书 $c$ 的长度（路径长度）也是多项式的。验证器 $V$ 只是模拟这条路径，所以它的运行时间也是多项式的。
   • 这样，我们就从一个 NTM 构造出了一个等价的多项式时间验证器。
2. 从 验证器 到 NTM (Verifier $\Rightarrow$ NTM):
   • 假设我们有一个多项式时间验证器 $V(x, c)$ 用于语言 $L$。
   • 我们如何构造一个 NTM $M$？
   • NTM $M(x)$ 的工作:
   • 逻辑: 如果 $x \in L$，那么存在一个“好”证书 $c$。NTM 的“幸运”计算分支会恰好猜测到这个 $c$，然后验证通过并接受。如果 $x \notin L$，那么不存在任何“好”证书，所以无论 NTM 猜出什么 $c'$，验证都会失败，所有分支都会拒绝。
   • 这正是 NTM 判决语言的定义。
   • 效率: 猜测多项式长度的证书需要多项式时间。运行多项式时间的验证器也需要多项式时间。两者相加仍然是多项式时间。
   • 这样，我们就从一个验证器构造出了一个等价的多项式时间 NTM。

结论: 因为可以双向转换，所以两种定义是等价的。这给予了我们选择更方便的工具来证明问题属于 NP 的自由。

这段阐述了 P 和 NP 之间最基本的关系，并引出了著名的 P vs. NP 问题。

定理 2: P 是 NP 的子集 ($\mathrm{P} \subseteq \mathrm{NP}$)

1. 证明思路:
   • 我们要证明：任何一个属于 P 的语言 $L$，也一定属于 NP。
   • 前提: 如果 $L \in \mathrm{P}$，根据 P 的定义，存在一个多项式时间的确定性图灵机 (DTM) $M$ 来判决它。
   • 关键点: 一个确定性图灵机可以被看作是一个非常“无聊”的非确定性图灵机 (NTM)。这个 NTM 在每个转换点，只有一个选择。它的计算树不是一棵“树”，而是一条“棍子”。
   • 构造: 我们可以直接把这个 DTM $M$ 当作一个 NTM $M'$ 来用。
   • 如果 $x \in L$: DTM $M$ 会接受 $x$。那么这个被看作 NTM 的 $M'$ 也有一条（唯一的）计算路径会接受 $x$。根据 NTM 的接受定义（存在一条路径接受即可），$M'$ 接受 $x$。
   • 如果 $x \notin L$: DTM $M$ 会拒绝 $x$。那么 $M'$ 的所有（唯一的一条）计算路径都会拒绝 $x$。根据 NTM 的拒绝定义（所有路径都拒绝），$M'$ 拒绝 $x$。
   • 效率: 这个 NTM $M'$ 的运行时间和 DTM $M$ 完全一样，也是多项式时间。
   • 结论: 我们找到了一个多项式时间的 NTM ($M'$) 来判决 $L$，因此根据 NP 的定义，$L \in \mathrm{NP}$。
   • 因为这个结论对所有 $L \in \mathrm{P}$ 都成立，所以 $\mathrm{P} \subseteq \mathrm{NP}$。

P vs. NP 问题:

1. 核心问题: 我们已经知道所有“容易解决”的问题（P）也都是“容易验证”的（NP）。那么，反过来是否成立？是不是所有“容易验证”的问题（NP）也都是“容易解决”的（P）？
2. 形式化: $\mathrm{NP} \subseteq \mathrm{P}$ 是否成立？
3. 两种可能性:
   • 如果 $\mathrm{P} = \mathrm{NP}$: 这意味着，任何一个解只要能被快速验证，那么这个问题本身也一定能被快速解决。这将引发技术革命，许多我们认为困难的优化问题（如蛋白质折叠、物流规划、密码破解）都将有高效算法。
   • 如果 $\mathrm{P} \neq \mathrm{NP}$: 这意味着，存在一些问题，它们的解容易验证，但找到解本身就是很困难的。这将符合我们大多数人的直觉，并意味着我们目前依赖的许多加密算法是安全的。
4. 现状: 这是计算机科学中最著名的未解之谜，克雷数学研究所为其设立了百万美元的千禧年大奖。绝大多数计算机科学家相信 $\mathrm{P} \neq \mathrm{NP}$，但至今无人能给出严格的数学证明。

这是下一大章的引言，为引入 NP-难 (NP-Hard) 和 NP-完全 (NP-Complete) 这两个关键概念提供了动机。

1. 观察到的现象: 在 NP 这个大篮子里，有一大堆问题（比如 3-SAT, TSP, 3-着色, 团问题等）。对于这些问题，尽管我们知道它们的解很容易验证（所以它们在 NP 里），但几十年来，全世界最聪明的头脑都没能为它们找到任何一个多项式时间的确定性算法。所有已知的算法都是指数时间的“暴力搜索”。
2. 提出的问题: 这些问题是真的“难”，还是我们只是“不够聪明”？
3. 激发的概念: 为了研究这些“最难的” NP 问题，科学家们提出了两个概念：
   • NP-难 (NP-Hard): 用来描述一类问题，它们的难度“至少”和 NP 中任何问题一样难。
   • NP-完全 (NP-Complete): 用来描述那些既在 NP 中，又是 NP-难的问题。它们是 NP 中“最难的”那一批问题。

这是定义 NP-难和 NP-完全的核心技术工具：多项式时间归约 (Polynomial-time reduction)。

1. 归约的本质: 归约是一种“问题转化”技术。说“问题 A 可以归约到问题 B”，直观上意味着“如果你有一个能解决问题 B 的黑盒子（算法），那么你就可以利用它来解决问题 A”。这暗示了 A 不比 B “更难”。
2. 映射归约: 这里的归约是一种特定类型，叫映射归约 (mapping reduction)。它要求有一个函数 $f$，能把问题 A 的任何一个实例 $x$，转化为问题 B 的一个实例 $f(x)$。
3. 多项式时间的要求: 这个转化过程本身必须是“高效”的。函数 $f$ 必须是一个多项式时间可计算函数，即计算 $f(x)$ 的算法的运行时间是 $|x|$ 的多项式。
4. 保持答案一致性: 这是归约的核心逻辑。转化函数 $f$ 必须保持“是/否”答案不变。
   • 如果 $x$ 是 A 的一个“是”实例 ($x \in A$)，那么转化后的 $f(x)$ 必须是 B 的一个“是”实例 ($f(x) \in B$)。
   • 如果 $x$ 是 A 的一个“否”实例 ($x \notin A$)，那么转化后的 $f(x)$ 必须是 B 的一个“否”实例 ($f(x) \notin B$)。
5. 记号: $A \le_P B$ 读作 "A is polynomial-time reducible to B"。这个小于等于号非常形象，暗示了“A 的难度小于等于 B 的难度”。
6. 输出大小: 一个重要的技术细节是，输出 $f(x)$ 的大小也必须是输入 $|x|$ 的多项式。如果 $f(x)$ 产生指数级的输出，那么即使解决 B 的算法是多项式的，用它来解决 $f(x)$ 也会变成指数时间。

这段内容证明了多项式时间归约的一个关键性质：如果一个问题 A 可以归约到一个“简单”问题 B（B 在 P 中），那么问题 A 本身也是“简单”的（A 也在 P 中）。

定理 3 的直观含义: 难度不会通过“简单”的转换凭空产生。如果你能把一个问题 A，通过一个简单的翻译（多项式时间归约 $f$），变成一个简单的问题 B，那么 A 本身也一定是简单的。

证明详解:

1. 目标: 证明 $A \in \mathrm{P}$。根据定义，就是要为 A 设计一个多项式时间的确定性算法 $M_A$。
2. 已知条件:
   • $A \le_P B$: 存在多项式时间的归约函数 $f$。
   • $B \in \mathrm{P}$: 存在多项式时间的算法 $M_B$ 来解决 B。
3. 构造算法 $M_A$ (算法 3):
   • 输入: A 的一个实例 $x$。
   • 步骤 1: 调用归约函数 $f$，计算出 B 的实例 $y = f(x)$。
   • 步骤 2: 调用解决 B 的算法 $M_B$，让它在 $y$ 上运行。
   • 步骤 3: 完全相信 $M_B$ 的答案。如果 $M_B$ 接受 $y$，那么 $M_A$ 就接受 $x$；如果 $M_B$ 拒绝 $y$，那么 $M_A$ 就拒绝 $x$。
4. 证明 $M_A$ 的正确性:
   • $M_A$ 接受 $x$ $\Longleftrightarrow$ $M_B$ 接受 $f(x)$ (根据 $M_A$ 的构造)
   • $M_B$ 接受 $f(x)$ $\Longleftrightarrow$ $f(x) \in B$ (因为 $M_B$ 是 B 的正确算法)
   • $f(x) \in B$ $\Longleftrightarrow$ $x \in A$ (根据归约 $f$ 的定义)
   • 把这三条串起来，得到：$M_A$ 接受 $x \Longleftrightarrow x \in A$。所以，$M_A$ 是 A 的一个正确算法。
5. 证明 $M_A$ 的效率 (多项式时间):
   • $M_A$ 的总时间 = (计算 $f(x)$ 的时间) + (运行 $M_B$ 在 $f(x)$ 上的时间)。
   • 计算 $f(x)$ 的时间: 已知 $f$ 是多项式时间的，所以这一步耗时 $O(|x|^{k_1})$。
   • 运行 $M_B$ 的时间:
   • 已知 $M_B$ 是多项式时间的，所以它在输入 $y=f(x)$ 上的时间是 $O(|y|^{k_2}) = O(|f(x)|^{k_2})$。
   • 因为 $f$ 是多项式时间的，其输出大小 $|f(x)|$ 也必须是多项式的，即 $|f(x)| = O(|x|^{k_1})$。
   • 把两者结合起来，运行 $M_B$ 的时间是 $O((|x|^{k_1})^{k_2}) = O(|x|^{k_1 \cdot k_2})$。
   • 总时间: $O(|x|^{k_1}) + O(|x|^{k_1 \cdot k_2})$。两个多项式的和仍然是多项式（取次数较高的那个），所以总时间是 $O(|x|^{\max(k_1, k_1 \cdot k_2)})$。
   • 结论: $M_A$ 是一个多项式时间算法。
6. 最终结论: 我们为 A 找到了一个多项式时间的正确算法 $M_A$，因此 $A \in \mathrm{P}$。

原文中的一个小错误:

• 原文最后一行说总时间是 $O(|x|^{k_1+k_2})$。这在多数情况下是正确的，但更严谨的应该是 $O(|x|^{k_1 \cdot k_2})$，因为是函数复合。不过，这不影响最终结论，因为两者都是多项式。$k_1+k_2$ 和 $k_1 \cdot k_2$ 都是常数。正确的总时间上界应该是 $O(|x|^{k_1} + |f(x)|^{k_2})$，而 $|f(x)|$ 本身是 $O(|x|^{k_1'})$，所以总时间是 $O(|x|^{k_1} + (|x|^{k_1'})^{k_2})$，这仍然是一个关于 $|x|$ 的多项式。

这个定理与定理3平行，它说明NP这个复杂性类对于多项式时间归约也是“向下封闭”的。

定理 4 的直观含义: 如果一个问题 A 可以归约到一个“可以在非确定性多项式时间解决”的问题 B（B 在 NP 中），那么问题 A 本身也一定“可以在非确定性多项式时间解决”（A 也在 NP 中）。

证明思路 (使用验证器模型):

1. 目标: 证明 $A \in \mathrm{NP}$。根据验证器定义，就是要为 A 设计一个多项式时间的确定性验证器 $V_A(x, c_A)$。
2. 已知条件:
   • $A \le_P B$: 存在多项式时间的归约函数 $f$。
   • $B \in \mathrm{NP}$: 存在一个多项式时间的验证器 $V_B(y, c_B)$ 来验证 B 的实例。
3. 构造 A 的验证器 $V_A$:
   • 输入: A 的一个实例 $x$，和 A 的一个证书 $c_A$。
   • 等等，A 的证书是什么？ 这是关键。既然 A 和 B 的答案是一致的，那么能证明 $f(x) \in B$ 的证据，也应该能间接证明 $x \in A$。所以，我们直接定义 A 的证书 $c_A$ 就是 B 的证书 $c_B$。
   • $V_A(x, c)$ 的算法:
4. 证明 $V_A$ 的正确性:
   • 如果 $x \in A$:
   • 根据归约定义，有 $f(x) \in B$。
   • 因为 $f(x) \in B$，根据 B 的验证器定义，存在一个 B 的证书 $c_B$ 使得 $V_B(f(x), c_B)$ 接受。
   • 那么，对于 A 的实例 $x$，我们也存在一个证书（就是这个 $c_B$），使得我们构造的 $V_A(x, c_B)$ 能够接受。
   • 如果 $x \notin A$:
   • 根据归约定义，有 $f(x) \notin B$。
   • 因为 $f(x) \notin B$，根据 B 的验证器定义，对于所有可能的证书 $c_B$，$V_B(f(x), c_B)$ 都会拒绝。
   • 那么，对于 A 的实例 $x$，无论我们给 $V_A$ 提供什么证书 $c$，$V_A(x, c)$ 内部调用的 $V_B(f(x), c)$ 都会拒绝，从而 $V_A$ 也会拒绝。
   • 这完全符合 A 的验证器的定义。
5. 证明 $V_A$ 的效率:
   • $V_A$ 的总时间 = (计算 $f(x)$ 的时间) + (运行 $V_B$ 的时间)。
   • 计算 $f(x)$ 是多项式时间的。
   • 运行 $V_B$ 是多项式时间的（关于其输入 $f(x)$ 的大小）。
   • 和定理3的分析完全一样，两个多项式时间操作的组合仍然是多项式时间的。
6. 最终结论: 我们为 A 找到了一个多项式时间的正确验证器 $V_A$，因此 $A \in \mathrm{NP}$。

这一定义引入了计算复杂性中一个至关重要的概念：NP-难 (NP-Hard)。

1. NP-难的定义:
   • 一个语言（问题）B 被称为 NP-难，它需要满足一个非常强的条件。
   • 这个条件是：NP 中的任何一个问题 A，都可以多项式时间归约到 B。
   • 形式化地：For every $A \in \mathrm{NP}$, $A \le_P B$ holds.
2. NP-难的直观含义:
   • NP-难问题是 NP 宇宙的“万能问题”或“难度上限”。
   • 它的难度至少和 NP 中任何一个问题一样难。
   • 如果你能解决一个 NP-难问题，你就能解决所有 NP 问题。
3. NP-难问题不一定在 NP 中:
   • 这是NP-难和 NP-完全的一个关键区别。
4. 重要推论:
   • 这句话是理解 NP-难重要性的关键：“如果我们能够找到一个 NP 难问题的多项式时间算法，那么我们就将有 $\mathrm{NP}=\mathrm{P}$。”
   • 证明:

这一定义引入了NP-完全 (NP-Complete) 的概念，它位于复杂性理论的中心。

1. NP-完全的两个条件: 一个问题 B 要想成为 NP-完全问题，必须同时满足两个条件：

a. 它本身必须在 NP 中 ($B \in \mathrm{NP}$)。这意味着，B 的解虽然可能难找，但验证是容易的。它必须是“那群怪兽”的一员。

b. 它必须是 NP-难的 ($B$ is NP-Hard)。这意味着，所有 NP 问题都可以多项式时间归约到 B。它必须是那群怪兽里的“龙之王”。

1. NP-完全 = NP 中最难的问题:
   • NP-完全问题可以被认为是 NP 中“最难”和“最具代表性”的问题。
   • 最难: 因为所有其他 NP 问题都能归约到它，所以它的难度是 NP 类的上限。
   • 代表性: 任何一个 NP-完全问题的命运，就代表了整个 NP 类的命运。
2. P vs NP 问题的关键:
   • 如果我们能为任何一个 NP-完全问题找到多项式时间算法，那么：
   • 因为它在 P 中，而它又是 NP-难的，根据前面的推论，$\mathrm{P}=\mathrm{NP}$。
   • 反过来，如果有人能证明任何一个 NP-完全问题不存在多项式时间算法，那么：
   • 这就意味着 $\mathrm{P} \neq \mathrm{NP}$，因为我们找到了一个在 NP 中但不在 P 中的问题。
   • 因此，所有 NP-完全问题“同生共死”。要么它们全都有多项式时间算法（$\mathrm{P}=\mathrm{NP}$），要么它们全都没有（$\mathrm{P} \neq \mathrm{NP}$）。

(这是一个经典的韦恩图，展示了 P, NP, NP-Complete, NP-Hard 之间的关系，假设 P!=NP)

这段介绍了计算复杂性历史上里程碑式的定理——库克-莱文定理 (Cook-Levin Theorem)。

1. 一个“先有鸡还是先有蛋”的问题:
   • 证明一个问题 B 是 NP-难，需要从一个已知的 NP-难问题 A 出发，证明 $A \le_P B$。
   • 但是，第一个 NP-难问题 A 是如何被证明的呢？在它之前，没有任何已知的 NP-难问题可以用来归约。
2. Cook 和 Levin 的突破:
   • Stephen Cook 和 Leonid Levin 在 1970 年代初独立地解决了这个“创世纪”的问题。
   • 他们没有使用归约，而是直接回归到 NP-难的原始定义：证明 NP 中的任何一个问题，都可以多项式时间归约到某一个特定的问题。
   • 他们选择的这个问题是布尔可满足性问题 (SAT)。后来发现，它的一个变种 3-SAT 也同样具有这个性质。
3. 定理 5 的内容: 3-SAT 问题是 NP-完全的。
   • 这意味着 3-SAT 不仅在 NP 中，而且是 NP-难的。
   • 它是第一个被验明正身的 NP-完全问题。
4. 证明思路简介 (非常高层次):
   • 目标: 证明对于任何一个在 NP 中的语言 $L$，都有 $L \le_P \text{3-SAT}$。
   • 出发点: 如果 $L \in \mathrm{NP}$，那么存在一个多项式时间的非确定性图灵机 (NTM) $M$ 来判决它。
   • 核心构造: Cook 和 Levin 展示了如何构造一个多项式时间的归约 $f$。这个 $f$ 的输入是 NTM $M$ 的一个输入字符串 $x$，输出是一个巨大的 3-CNF 布尔公式 $\phi = f(x)$。
   • 构造的属性: 这个公式 $\phi$ 被巧妙地设计成对 NTM $M$ 的整个计算过程的“模拟”。
   • 公式中的变量代表了图灵机在每一步的每个带单元上的状态、磁头位置和符号。
   • 公式中的子句描述了图灵机的合法行为规则：起始状态是正确的、每一步转换是合法的、最终到达了接受状态。
   • 逻辑: NTM $M$ 在输入 $x$ 上存在一条接受路径 $\Longleftrightarrow$ 构造出的布尔公式 $\phi$ 是可满足的。
   • 结论: 这个构造本身可以被一个算法在 $|x|$ 的多项式时间内完成。因此，这建立了一个从任意 NP 问题到 3-SAT 的多项式时间归约。这就证明了 3-SAT 是 NP-难的。
   • 再加上证明 3-SAT 本身在 NP 中是容易的（给一个变量赋值，验证公式是否为真），所以 3-SAT 是 NP-完全的。

这个定理是证明新问题是 NP-难的标准方法。它表明 NP-难这个属性是可以通过多项式时间归约来“传递”的。

定理 6 的直观含义: 如果问题 A 已经很难了（NP-难），而你又能把 A 转化为 B（$A \le_P B$），那么 B 肯定也一样难，甚至更难。

证明详解:

1. 目标: 证明 B 是 NP-难的。
2. NP-难的定义: 要证明 B 是 NP-难，我们必须证明对于任意一个 NP 问题 L，都有 $L \le_P B$。
3. 已知条件:
   • $A$ 是 NP-难的。这意味着对于我们选定的任意 L，我们已经知道 $L \le_P A$。存在一个多项式时间归约 $g$。
   • $A \le_P B$。这是题目给的。存在一个多项式时间归约 $f$。
4. 构造从 L 到 B 的归约:
   • 我们需要找到一个函数 $h$，使得 $L \le_P B$。
   • 我们的路径是 $L \xrightarrow{g} A \xrightarrow{f} B$。
   • 自然的想法是把两个函数复合起来：定义 $h(x) = f(g(x))$。
5. 证明 $h$ 是一个有效的归约: 我们需要证明两件事：

a. $h$ 是多项式时间的:

• 原文的详细论证：

i. 计算 $g(x)$ 需要多项式时间 $O(|x|^{k_g})$。

ii. 其输出大小 $|g(x)|$ 也是多项式的，$O(|x|^{k'_{g}})$。

iii. 计算 $f(y)$ 需要多项式时间 $O(|y|^{k_f})$。

iv. 所以计算 $f(g(x))$ 需要的时间是 $O(|g(x)|^{k_f}) = O((|x|^{k'_{g}})^{k_f}) = O(|x|^{k'_{g} \cdot k_f})$。

v. 总时间是计算 $g(x)$ 的时间 + 计算 $f(g(x))$ 的时间，两个多项式的和仍然是多项式。

• 结论: 复合函数 $h=f \circ g$ 是多项式时间可计算的。

b. $h$ 保持答案一致性:

• 原文的逻辑链条：

$x \in L$

$\Longleftrightarrow g(x) \in A$ (因为 $g$ 是 $L \to A$ 的归约)

$\Longleftrightarrow f(g(x)) \in B$ (因为 $f$ 是 $A \to B$ 的归约)

• 结论: $x \in L \Longleftrightarrow h(x) \in B$。

1. 最终结论: 我们已经为任意的 $L \in NP$ 构造了一个从 L 到 B 的多项式时间归约 $h$。因此，根据定义，B 是 NP-难的。

这个模板将定理6的理论直接转化为一个可操作的证明流程。

1. 步骤 1: 选择源问题 A:
   • 你不能凭空证明 B 是 NP-难的。你必须站在巨人的肩膀上。
   • 这个“巨人”就是一个你已经知道是 NP-难的问题 A。通常，我们会选择一个与我们当前问题 B 在结构上最相似的已知 NP-难问题，这样构造归约会更容易。
   • 最早的源头是 3-SAT。后来，3-SAT 被用来证明 3-着色、哈密顿路径、团问题等都是 NP-难的。现在，这个“已知 NP-难问题库”已经非常庞大，你可以从中选择任何一个方便的来用。
2. 步骤 2: 构造归约函数 f:
   • 这是证明中最具创造性和挑战性的一步。
   • 你需要设计一个算法，它能接收问题 A 的任何实例 $x$，并输出问题 B 的一个实例 $f(x)$。
   • 这个构造必须非常巧妙，以便保持“是/否”答案的一致性。
3. 步骤 3: 证明 f 是多项式时间的:
   • 你必须分析你设计的构造算法的运行时间，证明它是一个关于输入 $|x|$ 的多项式时间算法。如果构造过程本身就需要指数时间，那这个归约就无效了。
4. 步骤 4: 证明 "是" $\Rightarrow$ "是":
   • 这是证明归约正确性的第一个方向。
   • 你需要假设 $x$ 是 A 的一个“是”实例，然后通过逻辑推导，证明你构造出的 $f(x)$ 也必然是 B 的一个“是”实例。
5. 步骤 5: 证明 "否" $\Rightarrow$ "否":
   • 这是证明归约正确性的第二个方向。
   • 你需要假设 $x$ 是 A 的一个“否”实例，然后证明你构造出的 $f(x)$ 也必然是 B 的一个“否”实例。
   • 有时，证明这个方向的逆否命题会更容易：证明如果 $f(x) \in B$，那么 $x \in A$。这和步骤 4 结合起来，就构成了 $x \in A \Longleftrightarrow f(x) \in B$。

这个模板非常直接，它源于 NP-完全的定义。

1. 步骤 1: 证明 B 属于 NP ($B \in \mathrm{NP}$):
   • 这一步是证明问题 B 的解是“容易验证”的。
   • 你需要使用模板 2 (NTM) 或模板 3 (验证器) 来完成。
   • 通常，使用验证器模型更简单：
2. 步骤 2: 证明 B 是 NP-难的 ($B$ is NP-Hard):
   • 这一步是证明问题 B 是“至少和所有 NP 问题一样难”的。
   • 你需要使用模板 4 来完成。

同时完成这两步，就证明了 B 既是 NP 的一员，又是 NP 中最难的之一，因此 B 是 NP-完全的。

本段列举了一些著名的 NP-完全问题，让读者对这类问题有一个具体的感受。

1. SAT / 3-SAT (布尔可满足性问题):
   • 这是所有 NP-完全问题的“始祖”。
   • 问题: 给定一个由逻辑“与”连接的、由逻辑“或”组成的子句构成的布尔表达式，是否存在一种对变量的“真/假”赋值，使得整个表达式为真？
   • 3-SAT 是其简化版，要求每个子句中恰好有3个文字（变量或其否定）。它仍然是 NP-完全的，并且在构造归约时更规整、更好用。
2. Hampath (哈密顿路径问题):
   • 问题: 在一个给定的图中，是否存在一条路径，从起点 s 到终点 t，并且这条路径恰好经过图中每个顶点一次？
   • 这是图论中的经典难题。与寻找普通路径（在 P 中）不同，“经过每个顶点一次”这个约束使得问题变得异常困难。
3. Clique (团问题):
   • 问题: 在一个给定的图中，是否存在一个由 k 个顶点组成的“团”？“团”指的是一个顶点子集，其中任何两个顶点之间都有一条边，即一个完全子图。
   • 这在社交网络分析等领域有应用（例如，寻找一个 k 个人的小团体，他们彼此都互相认识）。
4. Sudoku (数独):
   • 问题: 给定一个部分填好的 $n^2 \times n^2$ 的数独网格，是否存在一个合法的解？
   • 经典的 $9 \times 9$ 数独是这个问题的特例 ($n=3$)。因为大小固定，任何 $9 \times 9$ 的数独都可以在有限（常数）时间内解决。但当我们将问题推广到任意大小的 $n^2 \times n^2$ 网格时，它就变成了 NP-完全问题。

这部分讨论了一个在算法分析中常见的组合问题——遍历子集，并用 3-Sum 问题作为例子，说明了当子集大小 $k$ 是一个常数时，暴力搜索算法可以是多项式时间的。

1. 子集数量分析:
   • 从 $n$ 个元素中选出 $k$ 个组成子集，总共有 $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ 种方式。
   • 关键近似: 当 $k$ 是一个常数时，$\binom{n}{k} = \frac{n(n-1)\dots(n-k+1)}{k!}$。这是一个关于 $n$ 的 $k$ 次多项式。因此，我们可以说 $\binom{n}{k} = O(n^k)$。
   • 重要对比: 如果 $k$ 不是常数，而是 $n$ 的函数（例如 $k=n/2$），那么 $\binom{n}{n/2}$ 的增长是指数级的 ($O(\frac{2^n}{\sqrt{n}})$)，算法就不是多项式时间了。
2. 示例 3: 3-Sum 问题:
   • 问题: 给定一个含 $n$ 个整数的集合 $S$，是否存在三个不同的元素 $a,b,c \in S$ 使得它们的和为 0？
   • 算法 (暴力搜索):
   • 遍历 $S$ 中所有大小为 3 的子集。
   • 对于每个子集 $\{a, b, c\}$，计算它们的和。
   • 如果和为 0，立即停止并回答“是”(Accept)。
   • 如果遍历完所有子集都没找到，则回答“否”(Reject)。
3. 证明 3-Sum $\in \mathrm{P}$:
   • 算法正确性: 算法检查了所有可能性，所以如果存在解，它一定能找到；如果不存在，它会检查完所有情况后正确地拒绝。
   • 效率分析:
   • 关键在于循环次数，即大小为 3 的子集的数量。这个数量是 $\binom{n}{3}$。
   • 因为这里的 $k=3$ 是一个常数，所以 $\binom{n}{3} = \frac{n(n-1)(n-2)}{6} = O(n^3)$。
   • 每次循环内部的操作（取三个数，加起来，比较）是常数时间。
   • 所以总运行时间是 $O(n^3)$。
   • 因为 $O(n^3)$ 是多项式时间，所以 3-Sum 问题属于 P。
   • (注：存在更优的 $O(n^2)$ 算法，但 $O(n^3)$ 已足以证明它在 P 中)。

这部分强调了一个在复杂性分析中极其重要但容易被忽略的细节：数字作为输入时是如何编码的，因为这直接决定了“输入规模 $n$”到底是什么。

1. 两种编码方式:
   • 一元 (Unary): 用 $N$ 个 "1" 来表示数字 $N$。例如，数字 5 表示为 "11111"。这种表示法的长度就是 $N$。
   • 二元 (Binary): 使用标准的二进制表示法。例如，数字 5 表示为 "101"。这种表示法的长度大约是 $\log_2 N$。
2. 长度的指数级差异:
   • 输入长度，即我们复杂性分析中的变量 $n$，在一元表示下是 $n=N$，而在二元表示下是 $n \approx \log N$。
   • 这两者之间的关系是指数的：$N = 2^{\log N} \approx 2^n$。
3. 对多项式时间的影响:
   • 复杂性分析的核心是判断运行时间是否是输入长度 $n$ 的多项式。
   • 假设有一个算法，运行时间是 $O(N)$ 步。
   • 如果输入是一元的，那么 $n=N$。运行时间 $O(N) = O(n)$，这是多项式时间的。
   • 如果输入是二元的，那么 $n=\log N$。运行时间 $O(N) = O(2^n)$，这是指数时间的！
4. 默认约定:
   • 在计算复杂性领域，除非特别声明，否则所有数字输入都默认采用二元（或任何其他进制，如十进制，它们在对数尺度上是等价的）表示。这是一种更紧凑、更符合计算机实际存储方式的表示。
5. 判断标准:
   • 当输入是一个数字 $N$ 时，输入规模是 $n = O(\log N)$。
   • 你的算法如果运行时间是 $N$ 的多项式，例如 $O(N^2), O(N^3)$，它被称为伪多项式时间 (Pseudo-polynomial time)，但它不是真正的多项式时间，而是关于输入长度 $n$ 的指数时间。
   • 只有当你的算法运行时间是 $\log N$ 的多项式，例如 $O((\log N)^2), O((\log N)^3)$，它才是真正的多项式时间算法。

这部分用合数问题 (Composite) 作为具体例子，来说明上一节中数字表示的重要性。

1. 问题定义:
   • 语言: Composite。
   • 成员: 大于等于2的合数 $N$。
   • 输入: 数字 $N$ 的二元表示 $\langle N \rangle$。
2. 算法 5 (试除法):
   • 这是一个解决该问题的确定性算法。
   • 逻辑: 从 2 开始，一直到 $N-1$，逐个尝试是否能整除 $N$。
   • 如果找到一个因子 $i$，立即可以确定 $N$ 是合数，接受。
   • 如果循环结束都没找到因子，说明 $N$ 是素数，拒绝。
3. 算法正确性: 这是判断合数的定义，算法是正确的。
4. 效率分析 (关键部分):
   • 运行时间 vs. N: for 循环最多执行 $N-2$ 次。每次循环做一次除法。除法的时间是 $\log N$ 的多项式。所以总时间大约是 $O(N \cdot (\log N)^k)$。为简单起见，我们关注主导项 $O(N)$。
   • 运行时间 vs. n: 输入是 $\langle N \rangle$，其长度是 $n = O(\log N)$。
   • 转换: 我们需要把以 $N$ 表示的时间，转换为以 $n$ 表示。因为 $n \approx \log_2 N$，所以 $N \approx 2^n$。
   • 结论: $O(N)$ 的运行时间，换算成输入长度 $n$ 的函数，就是 $O(2^n)$。这是一个指数时间算法，因此它不是多项式时间的。
5. 优化后的算法:
   • 我们可以优化试除法，只需要检查到 $\sqrt{N}$ 即可。
   • 优化后的运行时间是 $O(\sqrt{N})$。
   • 但这仍然是指数时间的！因为 $\sqrt{N} = (2^n)^{1/2} = 2^{n/2}$。$O(2^{n/2})$ 仍然是指数级的。
6. 引出的问题: 这个简单的确定性算法不是多项式时间的，那么 Composite 问题是否属于 P 呢？（在很长一段时间里，这是未知的）。

这段展示了，尽管我们没找到合数问题的多项式时间确定性算法（在当时），但为它设计一个多项式时间非确定性算法 (NTM) 却非常容易。这证明了 Composite $\in \mathrm{NP}$。

1. 算法 6 (NTM for Composite):
   • 这是一个典型的“猜测并验证”算法。
   • 猜测阶段: 非确定性地猜测一个介于 2 和 $N-1$ 之间的整数 $i$。这个 $i$ 就是合数的“证据”或“证书”——一个非平凡因子。
   • 验证阶段: 确定性地检查 $N$ 能否被猜测出的 $i$ 整除。如果可以，接受；否则拒绝。
2. 正确性分析:
   • 如果 N 是合数: 根据定义，N 至少有一个在 $[2, N-1]$ 范围内的因子 $i_0$。那么，NTM 的计算树中必然有一条“幸运”的分支，恰好猜测到了这个 $i_0$。在这条分支上，验证步骤 i divides N 会成功，从而该分支接受。根据 NTM 的接受规则，整个 NTM 接受。
   • 如果 N 是素数: 那么在 $[2, N-1]$ 范围内不存在任何 N 的因子。因此，无论 NTM 猜测哪个 $i$，验证步骤 i divides N 都会失败，导致该分支拒绝。既然所有分支都拒绝，整个 NTM 拒绝。
   • 算法是正确的。
3. 效率分析 (多项式时间):
   • 输入长度: $n = O(\log N)$。
   • 猜测阶段: 猜测一个数 $i$，$2 \le i < N$。这个数 $i$ 的二进制长度最多也就是 $n$ 位。NTM 可以在 $O(n)$ 的时间内猜测出这 $n$ 位。这是一个多项式时间操作。
   • 验证阶段: 检查 $i$ 是否整除 $N$。做一次整数除法，标准算法的时间复杂性是两个数位数的多项式，即 $O((\log N)^k)$，也就是 $O(n^k)$。这也是多项式时间的。
   • 总时间: NTM 计算树的深度（最长路径）是 $O(n) + O(n^k)$，这仍然是关于输入长度 $n$ 的多项式。
4. 结论: 我们找到了一个多项式时间的 NTM，因此 Composite $\in \mathrm{NP}$。
5. 一个重要的后记:
   • 文中最后提到，Composite 问题实际上也属于 P。
   • 2002年，三位印度科学家 Agrawal, Kayal, Saxena 提出了 AKS 素数测试，这是第一个被证明的、确定性的、无条件的、多项式时间的素性测试算法。
   • 这证明了 Composite $\in \mathrm{P}$。这是一个里程碑式的发现，但其算法远比这里的 NTM 算法复杂。

这部分详细解释了布尔可满足性问题 (SAT) 的背景知识、相关术语和它的复杂性。

1. 基本术语:
   • 变量 (Variable): 可以取值为“真”(1)或“假”(0)的符号，如 $x_1, x_2$。
   • 赋值 (Assignment): 为所有变量指定一组具体的真/假值。$n$ 个变量有 $2^n$ 种可能的赋值。
   • 文字 (Literal): 一个变量或其否定，如 $x_1$ 或 $\bar{x_1}$。
   • 子句 (Clause): 若干个文字通过逻辑“或”($\vee$)连接而成。例如 $(x_1 \vee \bar{x_2})$。一个子句被满足，当且仅当其中至少有一个文字为真。
   • 合取范式 (CNF Formula): 若干个子句通过逻辑“与”($\wedge$)连接而成。例如 $(x_1 \vee \bar{x_2}) \wedge (\bar{x_1} \vee x_2)$。一个 CNF 公式被满足，当且仅当它的所有子句都被满足。
2. SAT 问题:
   • 输入: 一个 CNF 公式 $\phi$。
   • 问题: 是否存在一个对变量的赋值，使得 $\phi$ 被满足？
3. k-CNF 和 k-SAT:
   • k-CNF 公式: 每个子句中文字的数量不超过 $k$。
   • 3-CNF 就是一个例子，每个子句有1、2或3个文字。
   • k-SAT 问题就是输入被限制为 k-CNF 公式的 SAT 问题。
4. 暴力解法:
   • 思路: 遍历所有 $2^n$ 种可能的变量赋值。
   • 对于每一种赋值:
   • 总运行时间: $O(2^n \cdot |\phi|)$。
5. 暴力解法的复杂性:
   • 运行时间是 $2^n$ 的指数函数，所以这是一个指数时间算法。
   • 对于 k-CNF，子句数量 $|\phi|$ 是 $n$ 的多项式，所以总时间仍然是指数级的。
6. SAT 的核心地位:
   • 尽管暴力解法很慢，但至今无人找到多项式时间的确定性解法。
   • SAT (特别是 3-SAT) 是第一个被证明的 NP-完全问题。
   • 这意味着，如果能为 SAT 找到一个多项式时间算法，那么 $\mathrm{P}=\mathrm{NP}$。反之，如果能证明 SAT 不存在多项式时间算法，那么 $\mathrm{P} \neq \mathrm{NP}$。

这部分通过一个具体的例子和一张（部分展示的）真值表，来演示一个 CNF 公式是如何被判定为“不可满足”的。

1. 给定的公式 $\phi$:
   • $\phi = (x_1 \lor x_2) \land (x_2 \lor x_3) \land (\bar{x}_3 \lor \bar{x}_1) \land (\bar{x}_4 \lor \bar{x}_2) \land x_4$
   • 这是一个有 5 个子句和 4 个变量的 CNF 公式。
2. 分析过程 (手工推导):
   • 我们要寻找一个赋值 $(x_1, x_2, x_3, x_4)$ 让所有子句都为真。
   • 从最简单的子句开始：第五个子句是 $(x_4)$。为了满足它，必须有 $x_4=1$。这立刻将我们的搜索空间从 $2^4=16$ 种可能减少到了 $2^3=8$ 种。
   • 现在我们知道 $x_4=1$。看第四个子句 $(\bar{x}_4 \lor \bar{x}_2)$。因为 $x_4=1$，所以 $\bar{x}_4=0$。为了满足这个子句，必须有 $\bar{x}_2=1$，即 $x_2=0$。搜索空间又减少到 $2^2=4$ 种。
   • 现在我们知道 $x_4=1, x_2=0$。看第一个子句 $(x_1 \lor x_2)$。因为 $x_2=0$，为了满足它，必须有 $x_1=1$。搜索空间减少到 $2^1=2$ 种。
   • 现在我们知道 $x_4=1, x_2=0, x_1=1$。看第二个子句 $(x_2 \lor x_3)$。因为 $x_2=0$，为了满足它，必须有 $x_3=1$。搜索空间只剩下 1 种可能赋值。
   • 唯一的候选解: 我们推导出，如果存在解，那它必须是 $(x_1, x_2, x_3, x_4) = (1, 0, 1, 1)$。
   • 最后验证: 我们用这个唯一的候选解去检查所有子句，特别是我们还没用过的第三个子句 $(\bar{x}_3 \lor \bar{x}_1)$。
   • 代入 $x_1=1, x_3=1$，我们得到 $(\bar{1} \lor \bar{1}) = (0 \lor 0) = 0$。
   • 这个子句没有被满足！
3. 结论:
   • 因为唯一可能满足其他四个子句的赋值，却无法满足第三个子句，所以不存在任何赋值可以同时满足所有五个子句。
   • 因此，这个公式 $\phi$ 是不可满足的 (unsatisfiable)。
4. 真值表:
   • 原文中的表格代表了暴力搜索方法，即列出所有 $2^4=16$ 种赋值，然后逐行计算每个子句的真值和整个公式 $\phi$ 的真值。
   • 最后一列 $\phi$ 是前五列（代表五个子句的真值）的逻辑“与”。只有当一行的前五列全为 1 时，$\phi$ 列才为 1。
   • 作者指出，如果你填完整个表格，会发现 $\phi$ 这一列永远是 0。这直观地证明了公式的不可满足性。

1. "所有 $n \log n, n^{100}+3n^2, n^{0.001n}, 2^{\sqrt{n}}$ 都是多项式的。"
   • 解答: 错。
   • 解释:
   • $n \log n = O(n^2)$，所以它是多项式的。
   • $n^{100}+3n^2 = O(n^{100})$，所以它是多项式的。
   • $n^{0.001n} = (n^{0.001})^n$。这个函数的指数部分包含 $n$，它的增长速度远超任何多项式 $n^k$。它不是多项式的。
   • $2^{\sqrt{n}}$。这是一个次指数函数，但它仍然比任何多项式 $n^k$ 增长得快。为了看清这一点，可以取对数：$\log(2^{\sqrt{n}}) = \sqrt{n}$，而 $\log(n^k) = k \log n$。因为 $\sqrt{n}$ 比 $k \log n$ 增长得快，所以 $2^{\sqrt{n}}$ 比 $n^k$ 增长得快。它不是多项式的。
2. "如果你为语言 L 展示了一个验证器 V(x, c)，其中 V 在 $|x|+|c|$ 的多项式时间内运行，那么 L 必须属于 NP。"
   • 解答: 错。
   • 解释: NP 的验证器定义要求验证器 $V$ 在关于原始输入 $|x|$ 的多项式时间内运行。如果证书 $|c|$ 的长度是 $|x|$ 的指数级（例如 $|c|=2^{|x|}$），那么 $|x|+|c|$ 的多项式 $O((|x|+2^{|x|})^k)$ 就不再是 $|x|$ 的多项式了。一个有效的 NP 验证器必须能处理一个多项式长度的证书，并在关于 $|x|$ 的多项式时间内完成验证。
3. "所有 NP 完全问题都可以多项式时间归约到彼此。"
   • 解答: 对。
   • 解释:
   • 设 A 和 B 是两个 NP-完全问题。
   • 证明 $A \le_P B$: 因为 B 是 NP-完全的，所以它是 NP-难的。根据 NP-难的定义，任何 NP 问题都可以多项式时间归约到 B。因为 A 是 NP-完全的，所以 A 也在 NP 中。因此，$A \le_P B$。
   • 证明 $B \le_P A$: 因为 A 是 NP-完全的，所以它是 NP-难的。根据 NP-难的定义，任何 NP 问题都可以多项-式时间归约到 A。因为 B 是 NP-完全的，所以 B 也在 NP 中。因此，$B \le_P A$。
   • 结论成立。
4. "假设图灵机的输入是二元表示的整数 N，并且 M 在 $O(N^2)$ 时间内运行，那么 M 在多项式时间内运行。"
   • 解答: 错。
   • 解释: 这是关于数字表示的经典陷阱。多项式时间是关于输入长度 $n$ 的多项式。对于二元表示的整数 $N$，输入长度是 $n = O(\log N)$。因此，运行时间 $O(N^2) = O((2^n)^2) = O(2^{2n})$。这是一个关于输入长度 $n$ 的指数时间，而不是多项式时间。

目标: 证明如果 $L_1, L_2 \in \mathrm{NP}$，那么 $L_1 \cup L_2 \in \mathrm{NP}$。

证明 (使用验证器模型):

1. 已知条件:
   • 因为 $L_1 \in \mathrm{NP}$，所以存在一个多项式时间验证器 $V_1(x, c_1)$ 和一个多项式 $p_1$ 使得 $|c_1| \le p_1(|x|)$。
   • 因为 $L_2 \in \mathrm{NP}$，所以存在一个多项式时间验证器 $V_2(x, c_2)$ 和一个多项式 $p_2$ 使得 $|c_2| \le p_2(|x|)$。
2. 构造 $L_1 \cup L_2$ 的验证器 $V_{union}$:
   • 证书: 我们为 $L_1 \cup L_2$ 定义一个新的证书 $c_{union}$。这个证书的结构是一个序对，例如 (b, c)，其中 b 是一个比特 (0 或 1)，c 是原始的证书。
   • 验证器 $V_{union}(x, c_{union})$ 的算法:
3. 证明正确性:
   • 如果 $x \in L_1 \cup L_2$:
   • 情况一: $x \in L_1$。那么存在一个证书 $c_1$ 使得 $V_1(x, c_1)$ 接受。我们可以构造一个新的证书 $c_{union} = (0, c_1)$。当 $V_{union}$ 收到这个证书时，它会执行 $V_1(x, c_1)$ 并接受。所以存在一个能让 $V_{union}$ 接受的证书。
   • 情况二: $x \in L_2$。同理，存在一个证书 $c_2$ 使得 $V_2(x, c_2)$ 接受。我们可以构造 $c_{union} = (1, c_2)$，它会让 $V_{union}$ 接受。
   • 在任何情况下，只要 $x \in L_1 \cup L_2$，就存在一个让 $V_{union}$ 接受的证书。
   • 如果 $x \notin L_1 \cup L_2$:
   • 这意味着 $x \notin L_1$ 且 $x \notin L_2$。
   • 那么，对于所有的 $c_1$，$V_1(x, c_1)$ 都会拒绝。对于所有的 $c_2$，$V_2(x, c_2)$ 都会拒绝。
   • 无论我们提供给 $V_{union}$ 的证书 $c_{union}=(b,c)$ 是什么，它要么调用 $V_1$（被拒绝），要么调用 $V_2$（也被拒绝）。
   • 因此，对于所有的 $c_{union}$，$V_{union}$ 都会拒绝。
4. 证明效率:
   • 证书长度: $|c_{union}| = 1 + |c|$。$|c|$ 的长度是 $|c_1|$ 或 $|c_2|$，以较长的为准，即 $\max(p_1(|x|), p_2(|x|))$。这是一个多项式。所以新证书的长度也是多项式的。
   • 运行时间: $V_{union}$ 的时间是解析证书的时间（可忽略）加上运行 $V_1$ 或 $V_2$ 的时间。$V_1$ 和 $V_2$ 都是多项式时间的。所以 $V_{union}$ 也是多项式时间的。

结论: 我们为 $L_1 \cup L_2$ 找到了一个多项式时间验证器，因此 $L_1 \cup L_2 \in \mathrm{NP}$。NP 在并集下是封闭的。

• k-团问题 (k-Clique) 属于 P:

1. 关键点: 在这个问题中，$k$ 是一个固定的常数，不是输入的一部分。例如，问题可能是“5-团问题”或“10-团问题”。
2. 算法:

a. 遍历图中所有大小为 $k$ 的顶点子集。

b. 对于每个子集，检查它是否构成一个团（即检查子集中 $\binom{k}{2}$ 对顶点之间是否都有边）。

c. 如果找到一个团，接受。

d. 如果遍历完所有子集都没找到，拒绝。

1. 效率分析:

a. 步骤 a 的次数: 共有 $\binom{n}{k}$ 个大小为 $k$ 的子集。因为 $k$ 是一个常数，所以 $\binom{n}{k} = O(n^k)$，这是一个关于 $n$ 的多项式。

b. 步骤 b 的时间: 检查一个大小为 $k$ 的子集需要检查 $\binom{k}{2}$ 条边。因为 $k$ 是常数，所以这也是一个常数时间的操作。

c. 总时间: $O(n^k) \times (\text{常数}) = O(n^k)$。

1. 结论: 由于 $k$ 是常数，算法的运行时间是多项式的。因此，k-团问题属于 P。

• 为什么该证明不适用于 NP-完全的团问题:

1. 关键区别: 在 NP-完全的 团 (Clique) 问题中， $k$ 是输入的一部分。
2. 算法分析失效: 我们仍然可以使用相同的暴力搜索算法。但是，它的运行时间是 $O(\binom{n}{k})$。
3. 为什么不再是多项式: 因为 $k$ 不再是常数，它可以和 $n$ 一样大。例如，考虑 $k=n/2$ 的情况。$\binom{n}{n/2}$ 是一个指数级的函数 (大约是 $2^n/\sqrt{\pi n/2}$)。$O(n^k)$ 这种表示法在这里也不再是多项式，因为指数 $k$ 是一个变量。
4. 结论: 当 $k$ 成为输入的一部分时，暴力搜索算法的运行时间是指数级的，因此这个算法无法证明问题属于 P。这并不证明它不属于 P，只是说这个特定的算法不够好。NP-完全的证明需要通过归约来表明，可能不存在任何多项式时间算法。

目标: 证明如果 $\mathrm{P}=\mathrm{NP}$，那么任何语言 $A \in \mathrm{P}$ (且 $A \neq \emptyset, A \neq \Sigma^*$) 都是 NP-完全的。

证明:

1. NP-完全的两个条件: 我们需要证明 A 满足：

a. $A \in \mathrm{NP}$

b. $A$ 是 NP-难的

1. 证明 a. $A \in \mathrm{NP}$:
   • 我们已知 $A \in \mathrm{P}$。
   • 我们也知道 $\mathrm{P} \subseteq \mathrm{NP}$ (定理 2)。
   • 因此，$A \in \mathrm{NP}$ 自动成立。
2. 证明 b. $A$ 是 NP-难的:
   • 目标: 根据定义，我们需要证明对于任意一个语言 $L \in \mathrm{NP}$，都有 $L \le_P A$。
   • 构造归约 $f$ 从 L 到 A:
   • 存在一个字符串 $y_{yes}$ 使得 $y_{yes} \in A$。
   • 存在一个字符串 $y_{no}$ 使得 $y_{no} \notin A$。
   • 输入: $L$ 的一个实例 $x$。
   • 算法:
3. 验证归约 $f$:
   • $f$ 是多项式时间的吗？: 是。计算 $f(x)$ 的过程就是运行多项式时间的算法 $M_L$，然后输出一个固定长度的字符串。整个过程是多项式时间的。
   • $f$ 是否保持答案一致性？:
   • 如果 $x \in L$: $M_L$ 接受 $x$，所以 $f(x) = y_{yes}$。我们已知 $y_{yes} \in A$。所以 $x \in L \implies f(x) \in A$。
   • 如果 $x \notin L$: $M_L$ 拒绝 $x$，所以 $f(x) = y_{no}$。我们已知 $y_{no} \notin A$。所以 $x \notin L \implies f(x) \notin A$。
   • 这两点合起来就是 $x \in L \Longleftrightarrow f(x) \in A$。
4. 结论:
   • 我们已经成功地为任意 $L \in \mathrm{NP}$ 构造了一个多项式时间归约 $L \le_P A$。
   • 因此，$A$ 是 NP-难的。
5. 最终结论: 因为 $A$ 既属于 NP 又属于 NP-难，所以 $A$ 是 NP-完全的。这个结论适用于任何非平凡的 P 类问题。

为什么要求 $A \neq \emptyset$ 和 $A \neq \Sigma^*$?

• 如果 $A = \emptyset$，那么不存在 $y_{yes} \in A$，我们的归约构造不成立。
• 如果 $A = \Sigma^*$，那么不存在 $y_{no} \notin A$，我们的归约构造也不成立。

这两个平凡的语言无法成为归约的目标。

Part 1: 证明 SPATH $\in \mathrm{P}$

• SPATH (Shortest Path): 是否存在一条从 $a$ 到 $b$ 的简单路径（不重复顶点），其长度至多为 $k$。
• 长度在这里指边的数量。
• 算法思路: 我们可以使用一个修改版的广度优先搜索 (BFS)。BFS 天然地按路径长度（边的数量）层层扩展，找到的是最短路径。
• 算法:

1. 创建一个队列 Q，初始时放入 (a, path=[a])，其中 path 记录了当前路径。
2. 创建一个集合 visited 来防止在同一条路径中重复访问节点，但注意我们需要允许不同的路径访问相同的节点。一个更好的方法是记录 (vertex, length) 的访问状态。
3. 修改后的 BFS:
   • 队列中存储 (current_node, current_path_length)。
   • 从 (a, 0) 开始。
   • 当从队列中取出 (u, len_u):
   • 如果 len_u >= k，则不再从 $u$ 扩展，因为路径已经太长了。
   • 对于 $u$ 的每个邻居 $v$：
   • 如果 $v$ 就是 $b$，我们找到了一条长度为 len_u + 1 的路径。因为 BFS 按层搜索，这是找到的第一条路径，它一定是最短的。如果 len_u + 1 <= k，则接受。
   • 如果 $v$ 不是 $b$，则将 (v, len_u + 1) 加入队列。
   • 一个更简单的图论算法: 在图 $G$ 上运行标准的 BFS/Dijkstra 算法，从源点 $a$ 开始，计算到所有其他节点的最短距离 dist[]。这个算法是多项式时间的（BFS 是 $O(V+E)$）。然后，只需检查 dist[b] 是否小于等于 $k$ 即可。因为 BFS/Dijkstra 找到的路径本身就是简单路径（在无负权重的图中），所以这个解法是正确的。
   • 结论: 存在多项式时间算法（如 BFS）可以解决 SPATH。因此 SPATH $\in \mathrm{P}$。

Part 2: 证明 LPATH 是 NP-完全的

• LPATH (Longest Path): 是否存在一条从 $a$ 到 $b$ 的简单路径，其长度至少为 $k$。
• NP-完全证明步骤:

1. 证明 LPATH $\in \mathrm{NP}$:
   • 证书: 一条具体的路径，即一个顶点序列 $c = (v_0, v_1, \dots, v_m)$。
   • 验证器:
   • 效率: 所有这些检查都可以在路径长度的多项式时间内完成。路径长度最多为 $|V|$。因此，这是一个多项式时间验证器。
   • 结论: LPATH $\in \mathrm{NP}$。
2. 证明 LPATH 是 NP-难的:
   • 选择源问题: 我们选择已知的 NP-完全问题 哈密顿路径 (HAMPATH)。
   • HAMPATH 定义: 给定图 $G$ 和两个顶点 $s, t$，是否存在一条经过所有 $|V|$ 个顶点的简单路径从 $s$ 到 $t$？一条经过所有顶点的简单路径，其长度（边数）恰好是 $|V|-1$。
   • 归约: 从 HAMPATH 归约到 LPATH。
   • 输入: HAMPATH 的一个实例 $\langle G, s, t \rangle$。
   • 归约函数 f: $f(\langle G, s, t \rangle) = \langle G, s, t, |V|-1 \rangle$。
   • 解释: 我们将 HAMPATH 实例直接转化为一个 LPATH 实例，图和起点/终点都不变，只是将目标长度 $k$ 设定为 $|V|-1$。
   • f 是多项式时间: 是。这个构造只是计算了 $|V|-1$，是 $O(1)$ 的。
   • 证明正确性 ($x \in A \iff f(x) \in B$):
   • ($\Rightarrow$): 假设在 $G$ 中存在一条从 $s$ 到 $t$ 的哈密顿路径。根据定义，这条路径是简单的，且长度恰好为 $|V|-1$。因此，它满足 LPATH 问题中“长度至少为 $|V|-1$”的要求。所以 $f$ 的输出是一个“是”实例。
   • ($\Leftarrow$): 假设 LPATH 实例 $\langle G, s, t, |V|-1 \rangle$ 的答案是“是”。这意味着在 $G$ 中存在一条从 $s$ 到 $t$ 的简单路径，其长度至少为 $|V|-1$。因为简单路径不能重复顶点，一条路径最多只能包含 $|V|$ 个顶点，其长度最多为 $|V|-1$。所以，这条路径的长度恰好是 $|V|-1$。一条包含 $|V|$ 个顶点的简单路径，就是哈密顿路径。所以原始的 HAMPATH 实例是“是”。
   • 结论: HAMPATH $\le_P$ LPATH。因为 HAMPATH 是 NP-难的，所以 LPATH 也是 NP-难的。

• 最终结论: 因为 LPATH 既属于 NP 又是 NP-难的，所以 LPATH 是 NP-完全的。