7_时间复杂性7.2.ZH解释

这段话是在回顾和总结前面章节（定理 7.8 和 7.11，虽然这里没有给出具体内容，但我们可以根据上下文推断）得出的两个核心结论，并以此引出计算复杂性理论中的一个根本性划分。

1. 确定性模型之间的关系：首先，它提到了确定型图灵机的不同变体，比如单带图灵机（只有一个存储和读写的工作带）和多带图灵机（有多个工作带）。结论是，这两个模型在计算能力上是等价的，并且在效率上的差异是“多项式级别”的。这意味着，如果一个问题在多带图灵机上可以用时间 $t(n)$ 解决，那么在单带图灵机上一定可以用 $t(n)^2$ 或者某个 $t(n)$ 的多项式，比如 $t(n)^k$ 的时间内解决。从宏观角度看，这种差异被认为是“不大”的。
2. 确定性与非确定性模型的关系：其次，它对比了确定型图灵机和非确定型图灵机。结论是，这两个模型在效率上的差异可能是“指数级别”的。非确定型图灵机有一个“猜测”或“并行探索所有可能性”的能力。如果一个问题在非确定型图灵机上可以用时间 $t(n)$ 解决，在确定型图灵机上解决它可能需要 $2^{t(n)}$ 级别的时间。这种差异被认为是“巨大”的，是本质上的不同。
3. 引出核心概念：通过这两个对比，作者强调了“多项式”和“指数”这两种增长率之间的鸿沟。这个鸿沟成为了划分问题“难易”程度的理论基础。

这段话提出了一个核心问题：为什么在计算复杂性理论中，我们选择以“多项式 vs. 指数”作为划分“易”与“难”的界线，而不是其他的函数划分，比如 $n^3$ vs $n^4$，或者 $n^{\log n}$ vs $2^n$？接下来的内容将为这个选择提供辩护和解释。这本质上是在说明将“多项式时间”定义为“高效”的合理性。

这里给出了选择“多项式 vs. 指数”作为分界线的第一个，也是最直观的理由：增长率的巨大差异。

1. 多项式增长：函数如 $n, n^2, n^3$ 等。当输入规模 $n$ 增大时，它们的函数值虽然也增大，但增长速度是相对“温和”的。作者举例 $n=1000$ 时，$n^3 = 1,000,000,000$（10亿）。对于现代计算机来说，执行10亿次操作是完全可能的（比如一个几 GHz 的CPU在一秒内就能执行几十亿次操作）。所以，这是一个“可管理”的数字。
2. 指数增长：函数如 $2^n, 3^n, n!$ 等。当输入规模 $n$ 增大时，它们的函数值会以爆炸性的速度增长。作者举例 $n=1000$ 时，$2^{1000}$ 的值。$2^{10} \approx 10^3$，所以 $2^{1000} = (2^{10})^{100} \approx (10^3)^{100} = 10^{300}$。这个数字远远超过了可观测宇宙中原子的总数（大约是 $10^{80}$）。这样的计算量在任何实际的计算机上都是绝对无法完成的。
3. 结论：因此，从实践角度看，多项式时间算法通常意味着问题是“可解的”、“可行的”；而指数时间算法通常意味着问题是“难解的”、“不可行的”，尤其当输入规模稍大时。

这段话解释了指数时间算法的一个常见来源，并指出了提升算法效率的途径。

1. 来源：暴力搜索 (Brute-force search)：许多问题的最直观解法是尝试所有可能性。这种方法被称为穷举搜索或暴力搜索。当可能性的数量随着输入规模 $n$ 呈指数增长时，暴力搜索算法就是指数时间的。
2. 例子：因数分解：要分解一个数 $N$，最简单的方法是尝试从 2 到 $\sqrt{N}$ 之间的所有数，看哪个能整除 $N$。输入是数字 $N$，其“规模”通常用其二进制表示的位数 $n$ 来衡量，即 $n \approx \log_2 N$。所以 $N \approx 2^n$。搜索范围是到 $\sqrt{N} \approx \sqrt{2^n} = 2^{n/2}$。搜索空间的大小 $2^{n/2}$ 是输入规模 $n$ 的指数函数，因此这是一个指数时间的暴力算法。
3. 改进途径：避免指数时间的关键在于找到比暴力搜索更聪明的方法。这通常需要对问题结构有更深刻的数学洞察。如果能找到一个巧妙的捷径，就有可能设计出多项式时间的算法。例如，虽然我们目前还没有找到大数分解的多项式时间经典算法，但对于其他许多问题（如下文的PATH问题），我们已经成功地从指数时间的暴力搜索改进到了多项式时间算法。

这段话提出了支持将“多项式时间”作为标准的一个强有力的理论依据：计算模型的稳健性。

1. 多项式等价 (Polynomially equivalent)：这个概念是指，如果我们在模型A上解决一个问题需要时间 $T(n)$，那么在模型B上模拟模型A来解决同一个问题，需要的时间是 $T(n)$ 的某个多项式，比如 $(T(n))^k$。反之亦然。
2. 合理的确定型计算模型：这个短语没有一个严格的数学定义，但它通常指那些计算能力与图灵机相当，并且其一步操作能在图灵机上用多项式步数模拟的计算模型。这包括我们日常使用的计算机的底层模型（如随机存取机 RAM 模型）、多带图灵机、多维图灵机等。它排除了那些过于强大以至于不真实的模型（比如可以一步完成指数级运算的模型）。
3. 核心论点：所有这些“合理”的模型都是多项式等价的。这意味着，一个问题如果在一个“合理”模型上是多项式时间可解的，那么它在所有其他“合理”模型上也是多项式时间可解的。反之，如果在一个模型上需要指数时间，在其他模型上也需要指数时间。
4. 意义：这个性质使得“多项式时间可解性”这个概念摆脱了对具体计算模型的依赖。我们不必纠结于用的是单带图灵机还是现代电脑，只要一个问题被证明是“多项式时间可解的”，这个结论就具有普遍性。它描述的是问题本身的内在属性，而不是某个特定机器的属性。

这段话是对前面论述的一个总结和宣告。

1. 研究焦点的声明：作者明确指出，接下来的讨论将进入一个更高层次的抽象。我们将不再关心一个算法是 $O(n^2)$ 还是 $O(n^3)$，我们只关心它是不是 $O(n^k)$（即，是不是多项式时间的）。我们关注的是“多项式 vs. 非多项式”的二元划分。
2. 理由重申：为什么要这么做？因为这样做可以构建一个普适的 (universal)、模型无关的 (model-independent) 理论。这个理论揭示的是计算问题本身 (problem) 的内在难度，而不是解决这个问题的特定算法 (algorithm) 或特定机器 (machine) 的效率。
3. 最终目标：理论计算机科学的宏大目标是理解“计算”这一概念的本质和极限。通过忽略具体的、依赖于模型的细节（如多项式差异），我们可以更清晰地看到那些更根本、更永恒的性质。

这段话正面回应了读者（尤其是具有编程实践经验的读者）可能产生的质疑。

1. 承认实践与理论的矛盾：作者承认，从一个“真正的程序员”或实践者的角度来看，忽略 $n$ 和 $n^3$ 之间的差异是“荒谬的”。在实际项目中，将一个 $O(n^3)$ 的算法优化到 $O(n \log n)$ 是巨大的成功，可能会让一个原本不可用的系统变得流畅。将程序速度提升两倍（即改变常数因子）也是工程师们日常追求的目标。
2. 类比与递进：作者通过类比来为这种忽略进行辩护。他提醒读者，我们之前在学习算法基础时，就已经接受了渐近表示法（大O表示法）。当时，我们就学会了忽略常数因子（例如，认为 $2n$ 和 $100n$ 都是 $O(n)$）和低阶项（例如，认为 $n^2 + 100n$ 是 $O(n^2)$）。
3. 提出更高层次的抽象：现在，作者建议我们把这种抽象再推进一步。之前我们忽略了 $n$ 和 $2n$ 的差异，现在我们建议忽略 $n$ 和 $n^3$ 的差异。这本质上是同一思想在不同层次上的应用：为了抓住更宏观的规律，我们需要忽略更细微的差别。

这段是前一段的补充和升华，进一步阐明了理论视角的重要性。

1. 再次肯定实践的重要性：作者强调，理论家们并非不食人间烟火。他们完全承认 $n$ 和 $n^3$ 的差异在实践中是“重要的”。
2. 提出另一类同样重要的问题：但是，存在着另一类同样重要，甚至更为根本的问题。这些问题的答案不依赖于多项式的具体次数，而只依赖于“是不是多项式”。例如，“大数分解问题到底有没有一个多项式时间的解法？” 这个问题，如果答案是“有”，那么将对密码学等领域产生颠覆性的影响，无论那个多项式解法是 $n^2$ 还是 $n^{100}$。从“无”到“有”的突破，其意义远大于从 $n^3$ 到 $n^2$ 的优化。
3. 森林与树木的比喻：这是一个非常经典的比喻。
   • 树木 (Trees)：指代算法的具体性能、多项式的次数、常数因子等细节。程序员和算法工程师通常专注于“树木”，力求让每一棵树都长得更高更壮。
   • 森林 (Forest)：指代问题的内在复杂性、大的复杂性类别（如P、NP）。理论计算机科学家专注于“森林”，试图描绘出整个计算世界的宏观版图。
   • 结论：关注森林并不意味着树木不重要。两者都很重要，只是研究的视角 (perspective) 和层次 (level) 不同。

这是一个引子，告诉读者，经过前面所有的铺垫和论证，我们终于要正式引入本节，乃至整个复杂性理论中最重要的核心定义之一了。

这是P类的正式定义。

1. P的含义：P 代表 Polynomial time（多项式时间）。
2. 核心内容：P类是一个语言的集合（a class of languages）。什么样的语言（问题）属于这个集合呢？标准是：存在一台确定型图灵机，它可以在多项式时间内判定这个语言。
   • 判定 (decide)：意味着图灵机对于任何输入，都能在有限时间内停机，并给出明确的“接受”或“拒绝”的答案。
   • 多项式时间 (polynomial time)：意味着图灵机的运行步数（时间）是输入长度 $n$ 的一个多项式函数，即 $O(n^k)$，其中 $k$ 是某个固定的常数。
   • 确定型单带图灵机：定义中特意选用了最基础的计算模型——确定型单带图灵机。根据之前的论证，因为所有合理的确定型模型都是多项式等价的，所以选择哪个模型作为基准并不影响P类的最终构成。选择最简单的模型可以使定义更清晰、更基本。
3. 数学化表达：
   • $\operatorname{TIME}(t(n))$：这是一个复杂性类，表示所有能被确定型单带图灵机在 $O(t(n))$ 时间内判定的语言的集合。
   • $\operatorname{TIME}(n^k)$：特指能在 $O(n^k)$ 时间内判定的语言集合。
   • $\bigcup_{k} \operatorname{TIME}\left(n^{k}\right)$：这个表达式的意思是，把所有 $k \geq 0$ 的 $\operatorname{TIME}(n^k)$ 集合都取并集。也就是说，一个语言只要存在任何一个 $k$，使得它可以在 $O(n^k)$ 时间内被判定，那么它就属于P类。这包含了 $O(n)$, $O(n^2)$, $O(n^{100})$ 等所有多项式时间可判定的语言。

这段话总结了P类之所以如此重要的两个核心原因。

1. 理论上的稳健性 (Robustness)：正如之前所论证的，“是否属于P类”这个属性不依赖于我们选择哪种合理的确定型计算模型。无论你用的是图灵机、RAM模型，还是C++、Java语言（的底层模型），一个问题是P问题，它就永远是P问题。这使得P类成为一个非常坚实的、适合进行理论研究的对象。它具有模型无关性。
2. 实践上的相关性 (Relevance)：P类粗略地划定了在现实世界中，哪些问题是“实际可计算的”或“易解的”(tractable)。虽然一个 $O(n^{100})$ 的算法在实践中并不可行，但将P类作为“易解”的门槛，在历史上被证明是一个非常有用的指导原则。

这段话是对“P类 ≈ 实际可解”这个说法的进一步阐释和辩护。

1. 承认P类算法的实用性差异：作者承认，并非所有P类算法都是实用的。一个算法的运行时间是 $O(n^k)$，它的实用性高度依赖于指数 $k$ 的大小以及常数因子。$O(n^2)$ 通常是实用的，而 $O(n^{100})$ 几乎肯定是不实用的。
2. P类作为“门槛”的价值：尽管存在上述差异，但将“多项式时间”作为“实际可解性”的门槛或分水岭，依然是非常有用的。这个门槛的意义不在于精确描述每一个算法的可用性，而在于提供一个分类标准。
3. 从“无”到“有”的突破：本段最重要的论点是，为一个问题找到第一个多项式时间算法，是一个重大的理论突破。
   • 关键洞察：这通常标志着我们对该问题的内在结构有了质的飞跃的理解，找到了避免暴力搜索的“捷径”。
   • 后续优化：历史经验表明，一旦第一个（可能很慢的，如 $O(n^{10})$）多项式时间算法被发现，研究者们往往能在此基础上进行改进和优化，最终得到一个在实践中真正有用的（如 $O(n^3)$ 或 $O(n^2)$）算法。从指数到多项式的跨越，是最困难也是最关键的一步。

这段话是在说明，为了证明一个问题属于P类，我们描述其算法时所采用的抽象层次。

1. 高级描述 (High-level description)：我们不会用图灵机的语言（状态转移、磁带操作）来描述算法。那种描述太底层、太繁琐了，会掩盖算法的核心思想。相反，我们会使用一种类似于伪代码的、人类易于理解的语言。
2. 模型无关：这种高级描述是独立于具体计算模型的。它不关心底层是单带图灵机还是现代计算机，从而使得我们的论证更具通用性。
3. 遵循约定：虽然是高级描述，但它并不是随意的。它必须遵循一定的规范，使得我们能够清晰地分析其时间复杂度，并确信它能在多项式时间内完成。接下来的段落会详细说明这些约定。

这里具体说明了描述算法的约定之一：分阶段描述。

1. 带编号的阶段 (Numbered stages)：算法将被分解为一系列清晰的、按顺序执行的步骤或阶段。
2. 对时间敏感：在进行复杂性分析时，我们必须关注两件事：
   • 总阶段数：算法总共执行了多少个阶段？这个总数必须是输入规模 $n$ 的一个多项式。
   • 每个阶段的成本：单个阶段的操作，如果用图灵机来实现，需要多少步骤？每个阶段自身也必须能在多项式时间内完成。
3. 多项式的复合：如果一个算法包含多项式数量的阶段，并且每个阶段都能在多项式时间内完成，那么这个算法的总运行时间也是多项式的。因为多项式的多项式（比如 $(n^2) \cdot (n^3) = n^5$）仍然是一个多项式。

这段是上文的进一步展开和强调，清晰地列出了证明一个算法是多项式时间算法的两步证明法。

1. 第一步：分析阶段数量：证明算法执行的总步骤数或总阶段数有一个多项式上界。也就是说，总阶段数是 $O(n^k)$，其中 $n$ 是输入长度，$k$ 是常数。这通常通过分析算法中的循环结构来完成。
2. 第二步：分析单个阶段：要确保我们描述的每个阶段都不是“魔法”。我们必须有信心，每一个高级描述的阶段（如“扫描所有边”、“标记节点”）都可以在一个标准的计算模型（如图灵机）上，用多项式数量的基本操作来实现。作者提到，在设计高级描述时，就会刻意地将阶段划分成这种“易于分析”的模块。
3. 结论：一旦这两步都完成，就可以得出结论：算法整体是多项式时间的。理由是“多项式的复合仍然是多项式”（A polynomial of a polynomial is a polynomial）。

这段话指出了分析复杂度时一个非常重要但又容易被忽略的细节：输入的编码方式。

1. 编码 (Encoding)：图灵机处理的是字符串。任何复杂的数学对象（如图、数字、公式）都必须首先被“翻译”成一个字符串，才能作为图灵机的输入。这个翻译过程就是编码。我们用 $\langle O \rangle$ 表示对象 $O$ 的编码字符串。
2. 合理编码 (Reasonable encoding)：一个编码方式是“合理的”，有两个要求：
   • 简洁性：编码后的字符串长度不应该比表示该对象所需信息的本质长度大太多。具体来说，它应该与我们通常使用的表示法（如二进制、十进制）在长度上是多项式关系的。
   • 编解码效率：从对象到字符串的编码过程，以及从字符串到对象的解码过程，都应该能在多项式时间内完成。
3. 不合理的编码例子：一元表示法 (Unary)：
   • 用 $n$ 个 "1" 来表示数字 $n$。例如，数字 17 表示为 11111111111111111。
   • 问题所在：一个数字 $N$ 的值是其二进制表示长度 $n$ 的指数函数 ($N \approx 2^n$)。而一元表示法的长度就是 $N$ 本身。所以，一元表示的长度是二进制表示长度的指数级。
   • 为什么不合理：如果使用一元编码，一个本来需要指数时间才能解决的问题（相对于二进制编码），可能会“伪装”成一个多项式时间问题。例如，测试一个数 $N$ 是否为素数的暴力算法需要 $O(\sqrt{N})$ 时间。如果输入是二进制编码，长度为 $n \approx \log N$，那么复杂度是 $O(\sqrt{2^n}) = O(2^{n/2})$，是指数级的。但如果输入是一元编码，长度为 $m=N$，那么复杂度是 $O(\sqrt{m})$，这变成了多项式级！这是通过“作弊”——即极大地拉长输入——来实现的，它没有改变问题的根本难度。因此，一元编码被认为是不合理的。
4. 合理的编码例子：二进制、十进制、邻接矩阵/邻接表（用于图）等都是合理的编码。

这段话将上一段关于编码的讨论，具体应用到了图问题上。

1. 图的合理编码：
   • 邻接表 (Adjacency list)：一个数组，每个数组元素对应一个节点，存放一个链表，链表里是所有与该节点相连的节点。
   • 邻接矩阵 (Adjacency matrix)：一个二维方阵，矩阵的第 $(i, j)$ 个元素表示节点 $i$ 和节点 $j$ 之间是否有边。
   • 这两种都是合理的，因为它们的编码大小（空间复杂度）与图的节点数 $V$ 和边数 $E$ 都是多项式关系。邻接表的空间是 $O(V+E)$，邻接矩阵是 $O(V^2)$。
2. 分析图算法的惯例：在分析图算法时，我们通常不直接用输入字符串长度 $n$ 作为变量，而是使用更有意义的图参数：节点数 $V$ (有时用 $m$ 或 $n$) 和 边数 $E$。
3. 惯例的合理性：这样做是允许的，因为输入编码的长度 $n$ 与 $V$ 和 $E$ 是多项式相关的。例如，对于邻接矩阵编码， $n = O(V^2)$。如果一个算法的时间复杂度是 $V$ 和 $E$ 的多项式，比如 $O(V^3 + E \log V)$，那么它也必然是 $n$ 的多项式。
   • $O(V^3) = O((\sqrt{n})^3) = O(n^{1.5})$，这是 $n$ 的多项式。
   • $O(E \log V) = O(V^2 \log V) = O(n \log \sqrt{n}) = O(n \log n)$，这也是 $n$ 的多项式。
   • 因此，整个算法复杂度是输入长度 $n$ 的多项式。
4. 结论：所以，为了方便，我们可以直接分析算法关于 $V$ 和 $E$ 的复杂度。只要它是 $V$ 和 $E$ 的多项式，我们就可以断定该问题属于P类。

这里正式引入了第一个要证明属于P类的问题：PATH 问题。

1. 问题定义：
   • 输入：一个三元组 $\langle G, s, t \rangle$。
   • $G$：一个有向图 (directed graph)。
   • $s$：图 $G$ 中的一个节点，称为起始节点 (start node)。
   • $t$：图 $G$ 中的另一个节点，称为目标节点 (target node)。
   • 问题：判断在图 $G$ 中，是否存在一条从节点 $s$ 出发，沿着边的方向，最终能到达节点 $t$ 的路径 (path)。
2. 语言形式化定义：
   • PATH 是一个语言（问题的集合）。
   • 一个字符串属于 PATH 语言，当且仅当这个字符串是 $\langle G, s, t \rangle$ 的一个“合理编码”，并且在图 $G$ 中确实存在一条从 $s$到 $t$ 的有向路径。
3. 图示：图中展示了一个例子。$s$ 是起始点，$t$ 是目标点。我们可以直观地看到，存在路径 $s \rightarrow a \rightarrow b \rightarrow t$。因此，这个图所对应的编码字符串 $\langle G, s, t \rangle$ 就属于 PATH 语言。

这是一个定理的声明，它的意思是“PATH问题是P类问题”，即存在一个多项式时间的确定型算法来解决PATH问题。接下来的证明部分将构造出这样一个算法并分析其复杂度。

这段话是正式证明前的“思路分析”，它首先否定了一个直观但低效的方法——暴力搜索。

1. 暴力算法思路：
   • 枚举出图中所有可能的路径。
   • 检查这些路径中，有没有一条是从 $s$ 开始，到 $t$ 结束的。
2. 路径长度的界定：如果存在一条 $s \to t$ 的路径，那么一定存在一条不含重复节点的简单路径。在含有 $m$ 个节点的图中，简单路径的长度最多是 $m-1$（即经过 $m$ 个不同的节点）。所以我们只需要检查长度不超过 $m$ 的路径。
3. 暴力算法的复杂度分析：
   • 一条长度为 $k$ 的路径是一个节点序列 $(v_0, v_1, ..., v_k)$。
   • 从 $s$ 出发，第一步可以走到 $s$ 的邻居节点，假设有 $d_s$ 个选择。第二步又可以从这些邻居节点出发，又有若干选择...
   • 粗略地估计，从 $s$ 出发的长度为 $k$ 的路径数量可能是 $d^{k-1}$（其中 $d$ 是节点的平均出度）。如果考虑所有长度到 $m$ 的路径，总数会非常巨大。
   • 作者给出了一个更粗略但更具说明性的上界：$m^m$。想象一条路径是长度为 $m$ 的节点序列，每个位置都可以是 $m$ 个节点中的任意一个，总共就有 $m^m$ 种可能性。这是一个非常宽松的上界，但足以说明路径总数是指数级的。
4. 结论：暴力搜索路径的方法是一个指数时间算法，它不够快，不能用来证明 PATH $\in \mathrm{P}$。

这里提出了解决PATH问题的高效算法的核心思想：图搜索。

1. 核心策略：不再枚举路径，而是枚举节点。我们关心的是“哪些节点可以从 $s$ 到达”，而不是“从 $s$ 出发有哪些路径”。这是一个关键的视角转换。
2. 标记法：算法的核心机制是“标记” (mark)。我们用一个标记来记录所有已经被确认“可以从 $s$ 到达”的节点。
3. 逐步扩展：
   • 初始时，只有 $s$ 本身是可达的，所以标记 $s$。
   • 然后，所有与 $s$ 直接相连的节点（路径长度为1）都变成可达的，标记它们。
   • 然后，所有与这些新标记的节点直接相连的节点（路径长度为2）也变成可达的，标记它们。
   • ... 这个过程不断重复，就像在水面上投下一颗石子，波纹（被标记的节点）一圈一圈地扩散开来。
4. 算法思想来源：这个思想就是经典的广度优先搜索 (Breadth-First Search, BFS) 或 深度优先搜索 (Depth-First Search, DFS)。BFS是按路径长度（距离 $s$ 的远近）逐层标记，DFS是沿着一条路径走到黑再返回。两者都可以解决可达性问题。文中描述的更接近BFS的思想。
5. 多项式时间：作者断言，这种策略的运行时间很容易被限制在多项式时间内。因为图中总共只有 $m$ 个节点，每次标记至少会增加一个新标记的节点，所以标记过程最多进行 $m$ 轮。每一轮需要检查图中的边，边的数量也是有限的。所以总时间是节点数和边数的多项式，而不是指数。

这是PATH问题多项式时间算法 $M$ 的具体步骤描述。

• 输入：一个有向图 $G$ 和两个节点 $s, t$。
• 阶段 1 (初始化)：将起始节点 $s$ 标记为“可达”。这是我们的出发点。
• 阶段 2 (主循环)：这是一个重复执行的过程，是算法的核心。循环的终止条件是“在一整轮扫描后，没有任何新的节点被标记”，这意味着可达节点的集合已经稳定，无法再扩展了。
• 阶段 3 (扩展)：在每一轮循环中，算法会遍历图中的所有边。对于每一条边 $(a, b)$，它会检查：
• 边的起点 $a$ 是否已经被标记？
• 边的终点 $b$ 是否尚未被标记？
• 如果同时满足这两个条件，就意味着我们找到了一个新的可达节点 $b$（因为我们可以从 $s$ 到达 $a$，再从 $a$ 走一步到 $b$）。于是，就将 $b$ 标记起来。
• 阶段 4 (结果判断)：当循环结束后（即所有能从 $s$ 到达的节点都已被标记），检查目标节点 $t$ 是否在被标记的节点集合中。
• 如果 $t$ 被标记了，说明存在一条从 $s$ 到 $t$ 的路径，算法接受输入。
• 如果 $t$ 没有被标记，说明从 $s$ 出发无法到达 $t$，算法拒绝输入。

这是对算法 $M$ 的复杂度分析，遵循了之前提出的“两步证明法”。

1. 第一步：分析阶段数量
   • 阶段 1 和 4：只执行一次，是常数时间。
   • 阶段 2 (主循环)：循环多少次？循环的条件是“有新的节点被标记”。
   • 图 G 中总共有 $m$ 个节点。
   • 每次循环（除了最后一次导致循环终止的空转）都至少会标记一个新的节点。
   • 所以，标记新节点的循环最多发生 $m-1$ 次（因为 $s$ 已经先被标记了）。
   • 加上最后一次空转，主循环最多执行 $m$ 次。
   • 总阶段数：算法执行的“轮数”或“宏观步骤”是 $O(m)$。因为 $m$ （节点数）是输入大小 $n$ 的多项式（通常 $m \le n$），所以总阶段数是多项式的。
2. 第二步：分析单个阶段
   • 阶段 1 和 4：标记一个节点或检查一个节点的标记，这都是非常快速的操作，显然是多项式时间（甚至是常数时间）。
   • 阶段 3 (扫描所有边)：这一步是循环内部的核心操作。
   • 它需要遍历图中的所有边。设边数为 $E$。
   • 对于每一条边 $(a, b)$，需要检查 $a$ 和 $b$ 的标记状态。
   • 在图灵机上，这相当于扫描一遍输入的边列表，并维护一个记录已标记节点的列表或磁带区域。这些操作都可以在输入大小的多项式时间内完成。
   • 如果用邻接矩阵表示，扫描所有边需要 $O(m^2)$ 时间。如果用邻接表，需要 $O(m+E)$ 时间。这些都是关于 $m$ 和 $E$ 的多项式。
3. 结论：
   • 算法的总时间复杂度 = (循环次数) $\times$ (每次循环内部操作的时间)
   • 总时间 $\approx O(m) \times O(E)$ (如果用邻接表，每次扫描是 $O(E)$) $= O(mE)$。
   • 在最坏情况下，一个有 $m$ 个节点的图，边数 $E$ 最多是 $O(m^2)$。
   • 所以总时间复杂度是 $O(m \cdot m^2) = O(m^3)$。
   • 这是一个关于节点数 $m$ 的多项式，因此它也是关于输入长度 $n$ 的多项式。
   • 所以，算法 $M$ 是一个多项式时间算法，从而证明了 PATH $\in \mathrm{P}$。

这里引入了第二个要证明属于P类的问题：RELPRIME 问题。

1. 互质 (Relatively Prime / Coprime) 的定义：如果两个整数 $x$ 和 $y$ 的最大公约数 (Greatest Common Divisor, GCD) 是 1，那么它们就互质。
   • 例子1：10 和 21。10的约数是 {1, 2, 5, 10}，21的约数是 {1, 3, 7, 21}。它们唯一的公约数是1，所以它们互质。注意，10和21都不是素数。
   • 例子2：10 和 22。它们有公约数 2（除了1之外），所以它们不互质。
2. 问题定义：
   • 输入：两个自然数 $x$ 和 $y$ 的编码 $\langle x, y \rangle$。
   • 问题：判断 $x$ 和 $y$ 是否互质。
3. 语言形式化定义：
   • RELPRIME 是一个语言。
   • 一个字符串属于 RELPRIME，当且仅当它是两个互质的整数 $x, y$ 的合理编码。

这是定理声明，意为“RELPRIME问题是P类问题”。需要构造一个多项式时间的算法来证明它。

这段思路分析再次首先否定了暴力搜索方法。

1. 暴力算法思路：
   • 要判断 $\text{gcd}(x, y) = 1$，我们可以去计算 $\text{gcd}(x, y)$ 的值。
   • 一个天真的方法是，找到 $x$ 的所有约数，找到 $y$ 的所有约数，然后找出其中最大的公共的那个。
   • 或者更简单点，从 2 开始，一直到 $\min(x, y)$，逐个检查每个数 $i$ 是否能同时整除 $x$ 和 $y$。如果找到了一个，那么它们就不互质。如果直到最后都没找到，它们就互质。
2. 复杂度分析：
   • 关键点：输入是数字 $x$ 的编码，其长度为 $n \approx \log_2 x$。这意味着数字的值 $x$ 是其输入长度 $n$ 的指数函数 ($x \approx 2^n$)。
   • 暴力搜索的范围是从 2 到 $\min(x, y)$。假设 $x < y$，搜索范围就是到 $x$ পর্যন্ত。
   • 搜索的次数大约是 $x$，即 $2^n$。
   • 这是一个关于输入长度 $n$ 的指数时间算法。因此，它不能用来证明 RELPRIME $\in \mathrm{P}$。

这里提出了解决 RELPRIME 问题的正确方法：欧几里得算法 (Euclidean algorithm)。

1. 欧几里得算法：这是一个非常古老（源于古希腊）且极其高效的算法，用于计算两个整数的最大公约数 (GCD)。
2. GCD：最大公约数，如 $\text{gcd}(18, 24) = 6$。
3. 与问题的关系：判断 $x, y$ 是否互质，等价于计算 $\text{gcd}(x, y)$ 并判断其结果是否为 1。所以，只要我们能高效地计算GCD，就能高效地解决RELPRIME问题。
4. 核心操作: 算法依赖于模运算 (mod function)。$x \bmod y$ 得到的是 $x$ 除以 $y$ 的余数。例如，$24 \bmod 18 = 6$。
5. 核心原理: 欧几里得算法基于一个深刻的数论原理：$\operatorname{gcd}(x, y) = \operatorname{gcd}(y, x \bmod y)$。通过这个递推关系，可以不断地将大数转换成小数，直到其中一个数为0，此时另一个数就是最大公约数。

这里给出了两个算法的具体描述：计算GCD的算法 $E$ 和解决RELPRIME问题的算法 $R$。

• 算法 E (欧几里得算法)
• 输入：两个数 $x, y$。
• 阶段 1 (循环)：当 $y$ 不为 0 时，就一直重复以下操作。
• 阶段 2 (取模)：计算 $x$ 除以 $y$ 的余数，并将这个余数赋值给 $x$。
• 阶段 3 (交换)：交换 $x$ 和 $y$ 的值。
• 阶段 4 (输出)：当循环结束时（即 $y=0$ 时），此时的 $x$ 就是原始输入的最大公约数。
• 算法 R (RELPRIME 判定器)
• 输入：两个数 $x, y$。
• 阶段 1：调用算法 $E$ 作为子程序，计算出 $\text{gcd}(x, y)$。
• 阶段 2：检查 $E$ 的输出结果。如果是 1，就接受；如果不是 1，就拒绝。

这段话将证明的焦点缩小到了算法 $E$ 上。

1. 归约：算法 $R$ 的工作量基本上就是调用一次算法 $E$ 再加上一次比较。所以 $R$ 的时间复杂度主要由 $E$ 的时间复杂度决定。如果 $E$ 是多项式时间的，那么 $R$ 也是。
2. 分析任务：因此，我们只需要分析算法 $E$ 的两个方面：
   • 正确性 (Correctness)：算法 $E$ 是不是真的能计算出最大公约数？
   • 时间复杂度 (Time Complexity)：算法 $E$ 是不是在多项式时间内完成？
3. 省略正确性证明：作者指出，欧几里得算法的正确性是一个非常经典的数论结论（基于 $\text{gcd}(x, y) = \text{gcd}(y, x \bmod y)$），在此不再赘述。
4. 聚焦时间分析：所以，剩下的唯一任务就是分析算法 $E$ 的时间复杂度。

这是对算法 $E$ 时间复杂度的核心分析。其策略是证明在循环中，数值 $x, y$ 的规模在快速缩小。

1. 核心论点：每次循环（严格来说是每两轮循环），数值会显著减小。作者这里给出了一个更强的结论：一次循环后，其中一个数会至少减半。
2. 分析单次循环后的数值变化 (假设初始 $x > y$):
   • x_new = x % y (x_new 是新 x)
   • y_new = y
   • 然后交换，变成 (y, x % y)。
3. 作者的分析思路 (稍微有点绕，我们简化一下)：
   • 考虑算法中的一对变量 $(x, y)$，假设在循环开始时 $x>y$。
   • 经过 x_new = x % y 和交换后，新的变量对是 $(y, x \bmod y)$。
   • 关键是证明其中一个值会快速变小。
   • 拉梅定理 (Lamé's Theorem) 是分析欧几里得算法复杂度的标准方法，它表明算法的步数不会超过较小数的十进制位数的5倍，这是一个对数关系，因此是多项式时间。
   • 作者给出的简化证明：
   • 考虑在第 $i$ 轮循环开始时的值 $(x_i, y_i)$，假设 $x_i > y_i$。
   • 第 $i$ 轮循环后，值变为 $(x_{i+1}, y_{i+1}) = (y_i, x_i \bmod y_i)$。
   • 第 $i+1$ 轮循环后，值变为 $(x_{i+2}, y_{i+2}) = (x_i \bmod y_i, y_i \bmod (x_i \bmod y_i))$。
   • 可以证明 $x_{i+2} < x_i / 2$。
   • 情况1：如果 $y_i \le x_i / 2$。那么 $x_{i+2} = x_i \bmod y_i < y_i \le x_i / 2$。
   • 情况2：如果 $y_i > x_i / 2$。那么 $x_i \bmod y_i = x_i - y_i < x_i - x_i / 2 = x_i / 2$。所以 $x_{i+2} = x_i \bmod y_i < x_i/2$。
   • 结论：在两种情况下，经过两轮循环，原先较大的数 $x_i$ 对应的新数 $x_{i+2}$ 的值至少会减半。

这是基于上一段的分析，对算法 $E$ 的时间复杂度做出的最终结论。

1. 第一步：分析阶段数量（循环次数）
   • 我们已经证明了，每两次循环，数值至少减半。
   • 一个数 $x$ 被反复除以2，需要多少次才能降到1？答案是 $\log_2 x$ 次。
   • 由于是每两次循环减半，所以总循环次数大约是 $2 \log_2 x$ 或 $2 \log_2 y$ 这个量级。
   • 输入数字 $x$ 的二进制表示长度 $n_x \approx \log_2 x$。
   • 因此，循环次数是 $O(\log x) = O(n_x)$。如果总输入长度是 $n = n_x + n_y$，那么循环次数就是 $O(n)$。
   • $O(n)$ 是一个多项式（一次多项式），所以阶段数量满足多项式上界。
2. 第二步：分析单个阶段
   • 循环内部的操作是取模（阶段2）和交换（阶段3）。
   • 在图灵机上，做两个二进制数的除法（以得到余数）是一个标准算术过程，可以用多项式时间（比如 $O(n^2)$）完成。
   • 交换两个数也是多项式时间。
   • 所以，每个阶段的成本是多项式的。
3. 结论：
   • 总时间复杂度 = (循环次数) $\times$ (每次循环的成本)
   • 总时间 $\approx O(n) \times O(n^2) = O(n^3)$。
   • $O(n^3)$ 是一个关于输入长度 $n$ 的多项式。
   • 因此，算法 $E$ 是多项式时间的。由于 $R$ 只是调用 $E$，所以 $R$ 也是多项式时间的。
   • 最终结论：RELPRIME $\in \mathrm{P}$。

这是一个引言，预告了本节将要证明的第三个，也是一个非常普适和重要的结论：所有上下文无关语言 (Context-Free Language, CFL) 都是P类问题。这意味着，由上下文无关文法 (CFG) 所描述的任何语言（比如许多编程语言的语法），其成员资格问题（即判断一个字符串是否符合该语法）都是可以在多项式时间内解决的。

这是定理的正式声明。用语言来说就是，For every language $L$ that is a CFL, $L \in \mathrm{P}$。

证明思路的第一步是回顾之前在“可计算性”章节中学过的内容。

1. 回顾定理 4.9：这个定理（虽然我们这里看不到原文）说明了所有CFL都是可判定的 (decidable)。这意味着存在一个算法，对于任何字符串 $w$，都可以判断 $w$ 是否属于该CFL，并且该算法一定会停机。
2. 检查旧算法：证明定理4.9时，肯定提供了一个具体的判定算法。现在的问题是：那个旧的算法是不是多项式时间的？
   • 如果是，那么定理7.16就直接得证了，无需新算法。
   • 如果不是，我们就需要找到一个更快的、多项式时间的算法。

这里描述了那个旧的、用于证明可判定性的算法。

1. 前提：乔姆斯基范式 (Chomsky Normal Form, CNF)：任何CFL都可以由一个CNF文法生成。CNF的规则只有两种形式：$A \to BC$ 或 $A \to a$（其中 $A, B, C$ 是变量，$a$ 是终结符）。这个范式简化了分析。
2. 推导步数：对于一个长度为 $n$ 的字符串 $w$ ($n>0$)，如果它能被CNF文法 $G$ 生成，那么生成它的推导树一定有 $2n-1$ 步。这是一个可以被证明的、CNF文法的重要性质。
3. 旧算法的思路 (暴力搜索)：
   • 给定输入字符串 $w$ (长度为 $n$)。
   • 算法就去枚举所有长度为 $2n-1$ 的推导序列。
   • 对于每个枚举出的推导，看看它最终生成的字符串是不是 $w$。
   • 如果找到了一个能生成 $w$ 的推导，就接受。
   • 如果试遍了所有可能的 $2n-1$ 步推导，都无法得到 $w$，就拒绝。

这里对旧算法的效率给出了判决：不是多项式时间。

1. 原因：在推导的每一步，我们可能有多种规则可以选择。
   • 比如，从开始符号 $S$ 出发，如果有规则 $S \to AB$ 和 $S \to CD$，就有两种选择。
   • 下一步，从 $A$ 出发可能又有多种选择...
   • 经过 $k$ 步之后，可能的推导序列的数量会随着 $k$ 指数级增长。
2. 复杂度：由于要枚举的推导数量是指数级的，这个暴力算法的时间复杂度是指数时间的。
3. 结论：这个旧算法不够快，不能用来证明 CFL $\in \mathrm{P}$。我们需要一个全新的、更聪明的算法。

这里引入了解决该问题的关键技术：动态规划 (Dynamic Programming)。

1. 动态规划核心思想：
   • 分而治之：将一个大问题分解成许多更小的、相互重叠的子问题。
   • 记忆化/表格法：解决这些子问题，并将它们的解存储起来（通常在一个表格中），以避免重复计算。
   • 自底向上构建：从最小的子问题开始，利用已解出的子问题的答案，逐步构建出更大子问题的答案，直到最终解决原始的大问题。
2. 应用到CFL判定：我们将用动态规划来避免重复地去检查“某个变量能否生成某段子串”这样的问题。

这里具体说明了如何将动态规划应用到CFL判定问题上。

1. 子问题定义：我们的子问题是：“对于输入字符串 $w$ 的任意一个子串 $w[i..j]$ (从第 $i$ 个字符到第 $j$ 个字符)，有哪些变量可以生成它？”
2. 表格设计：
   • 我们创建一个 $n \times n$ 的二维表格，名为 table。
   • table[i][j] 这个单元格用来存储一个变量的集合。
   • 这个集合里的变量，就是所有能够生成子串 $w[i..j]$ 的变量。
   • 表格的下标 $i$ 代表子串的起始位置，$j$ 代表子串的结束位置。
   • 因为子串的起始位置 $i$ 不可能大于结束位置 $j$，所以当 $i>j$ 时，表格项是无用的（可以只用上/下三角部分）。

这段话描述了动态规划的“自底向上”的构建过程。

1. 构建顺序：算法不是随意填充表格的，而是按照子串的长度从小到大来填充。
   • 第1步：处理所有长度为 1 的子串 ($w[1..1], w[2..2], ..., w[n..n]$)，填充表格的对角线 table[i][i]。
   • 第2步：处理所有长度为 2 的子串 ($w[1..2], w[2..3], ...$)，填充 table[i][i+1]。
   • ...
   • 第n步：处理长度为 $n$ 的子串 ($w[1..n]$)，填充最终的目标 table[1][n]。
2. 递推关系（核心思想）：如何利用短子串的解来构建长子串的解？
   • 目标：我们要判断变量 $A$ 能否生成一个长子串 $w[i..j]$。
   • 利用规则 $A \to BC$：根据CNF的规则，如果 $A$ 能生成 $w[i..j]$，那么它一定是先变成了两个变量 $B$ 和 $C$，然后 $B$ 生成了子串的前半部分，C生成了后半部分。
   • 分割子串：所以，我们将子串 $w[i..j]$ 分割成两部分：$w[i..k]$ 和 $w[k+1..j]$，其中 $k$ 是分割点，可以从 $i$ 取到 $j-1$。
   • 查表：对于每一种分割方式，我们去查已经计算好的表格项：
   • 变量 $B$ 在不在 table[i][k] 里？（B 能否生成前半部分？）
   • 变量 $C$ 在不在 table[k+1][j] 里？（C 能否生成后半部分？）
   • 得出结论：如果在所有规则 $A \to BC$ 和所有可能的分割点 $k$ 中，只要有一次，我们发现 B 在 table[i][k] 中 并且 C 在 table[k+1][j] 中，我们就可以断定 $A$ 能够生成 $w[i..j]$，并把 $A$ 加入到 table[i][j] 中。
3. 初始条件（Base Case）：这个递推过程的起点是什么？是长度为 1 的子串。
   • 对于子串 $w[i..i]$（就是一个字符 $b=w_i$），变量 $A$ 能生成它，当且仅当文法中存在规则 $A \to b$。
   • 所以，填充表格对角线 table[i][i] 的过程就是检查所有 $A \to b$ 形式的规则。

这是动态规划算法（CYK算法）的完整伪代码描述。

• 输入: 字符串 $w$。
• 阶段 1 (特殊情况): 处理空字符串 $\varepsilon$。CNF文法通常不允许 $A \to \varepsilon$ 规则，除非是 $S \to \varepsilon$ 且 $S$ 不出现在任何规则的右侧。这里做了简化处理：如果文法允许生成空串，并且输入就是空串，则接受。
• 阶段 2-5 (处理长度为1的子串):
• 这是一个双重循环。外层 for i=1 to n 遍历所有起始位置。
• 内层 for each variable A 遍历所有变量。
• 核心操作 (阶段 4-5): 检查是否存在规则 $A \to w_i$。如果存在，就把变量 $A$ 填入对角线格 table(i, i)。
• 阶段 6-11 (处理长度大于1的子串):
• 这是一个三重嵌套循环，是算法的主体。
• 外层循环 (阶段 6) for l=2 to n: 按子串长度 $l$ 从 2 到 $n$ 迭代。
• 中层循环 (阶段 7) for i=1 to n-l+1: 遍历所有可能的起始位置 $i$，对于给定的长度 $l$。结束位置 $j$ 由 $i$ 和 $l$ 确定 (阶段 8)。
• 内层循环 (阶段 9) for k=i to j-1: 遍历当前子串 $w[i..j]$ 的所有可能分割点 $k$。
• 最内层操作 (阶段 10-11):
• 遍历文法中所有的 $A \to BC$ 规则。
• 对于每个规则，检查 $B$ 是否能生成前半段（查 table(i, k)），以及 $C$ 是否能生成后半段（查 table(k+1, j)）。
• 如果都可以，就把 $A$ 加入 table(i, j)。
• 阶段 12 (最终判断):
• 所有表格填充完毕后，检查 table(1, n) (代表整个字符串 $w$ 的格子)。
• 如果开始符号 $S$ 在这个格子里，说明 $S$ 可以生成 $w$，接受。
• 否则，拒绝。

这是对算法 $D$ (CYK算法) 的时间复杂度分析。

1. 分析前提:
   • $n$ = 输入字符串 $w$ 的长度。
   • $v$ = 文法 $G$ 中变量的数量。
   • $r$ = 文法 $G$ 中规则的数量。
   • 关键：$v$ 和 $r$ 是常数，它们只跟文法有关，跟输入字符串的长度 $n$ 无关。
2. 分析各部分复杂度:
   • 阶段 1: $O(1)$，常数时间。
   • 阶段 2-5 (处理长度1子串):
   • 外层循环 i=1 to n: $n$ 次。
   • 内层循环 each variable A: $v$ 次。
   • 内部操作: $O(1)$。
   • 总时间: $O(n \cdot v)$。因为 $v$ 是常数，所以这部分是 $O(n)$。
   • 阶段 6-11 (处理长子串):
   • 循环 l (长度): from 2 to n -> $O(n)$ 次。
   • 循环 i (起点): from 1 to n-l+1 -> 最多 $O(n)$ 次。
   • 循环 k (分割点): from i to j-1 -> 子串长度最多是 $n$，所以最多 $O(n)$ 次。
   • 循环规则 (阶段 10): each rule A->BC -> $r$ 次。
   • 核心操作 (阶段 11): 查表和插入。可以认为是 $O(1)$。
   • 总时间: 三层关于 $n$ 的循环，所以是 $O(n \cdot n \cdot n) = O(n^3)$。更精确地说是 $O(n^3 \cdot r)$。因为 $r$ 是常数，所以是 $O(n^3)$。
   • 阶段 12: $O(1)$。
3. 结论:
   • 算法中最耗时的部分是阶段 6-11 的三重循环，其时间复杂度是 $O(n^3)$。
   • 因此，整个算法 $D$ 的时间复杂度是 $O(n^3)$。
   • $O(n^3)$ 是一个多项式。
   • 最终结论: 每个 CFL 都存在一个多项式时间的判定算法，因此，每个 CFL 都属于 P 类。证明完毕。

本文档的核心在于建立并论证了计算复杂性理论的基石——P 类。整个论述过程可以看作是为“为什么多项式时间如此特别？”这个问题提供一个全面而有力的答案。其特殊性体现在以下几个层面：

1. 实践层面的巨大鸿沟：文章开篇就用生动的例子（$n^3$ vs $2^n$）展示了多项式增长与指数增长之间存在着天壤之别。对于中等规模的输入，多项式时间算法的计算量是“可管理的”，而指数时间算法的计算量则会暴增到“天荒地老”，甚至超越物理宇宙的极限。这为我们将“多项式时间”与“实际可行”划上等号提供了最直观的依据。
2. 理论层面的模型无关性：文章强调了所有“合理的”确定型计算模型（如图灵机、RAM模型等）都是多项式等价的。这意味着，一个问题是否属于P类，是这个问题内在的、固有的属性，而不依赖于我们选用哪种计算机模型来分析它。这种稳健性 (Robustness) 使得P类成为一个深刻、普适的数学概念，足以作为构建宏大理论的基石。
3. 算法设计上的指引：文章指出，指数时间算法通常来源于对解空间的暴力搜索。而发现一个多项式时间算法，往往意味着我们对问题结构本身有了关键的洞察，找到了避免暴力搜索的“捷径”。从指数时间到多项式时间的跨越，即便最初发现的算法效率不高（如 $O(n^{100})$），也被认为是一个里程碑式的突破，因为它为后续的优化指明了方向，最终往往能引导至真正实用的算法。

文章通过三个来自不同领域的经典例子，生动地展示了P类问题的广泛性和解决它们所需的技术的多样性。

1. PATH 问题 (图论)：这是一个关于图的连通性问题。
   • 解决技术：图搜索算法（如广度优先搜索 BFS 或深度优先搜索 DFS）。其核心思想是通过“标记”和“扩展”来系统地探索所有从起点可达的节点，从而避免了枚举天文数字级别的路径。
   • 体现了：对数据结构进行系统性遍历的思想。
2. RELPRIME 问题 (数论)：这是一个关于整数性质的判定问题。
   • 解决技术：欧几里得算法。它利用了深刻的数论等价关系 $\text{gcd}(x, y) = \text{gcd}(y, x \bmod y)$，通过快速减小问题规模来达到高效计算。其迭代次数与输入数值的对数成正比，因而极其高效。
   • 体现了：利用数学洞察力进行问题转化的思想。
3. CFL 判定问题 (形式语言)：这是一个关于字符串与文法匹配的普适性问题。
   • 解决技术：动态规划（具体为 CYK 算法）。其核心思想是将大问题（整个字符串能否被生成）分解为所有关于子串的子问题，并将子问题的解记录在表格中，通过自底向上、无重复计算的方式构建出最终答案。
   • 体现了：通过“空间换时间”，利用表格记录子问题解来避免重复计算，从而将指数级搜索优化为多项式级填充的思想。