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

$$ **解释**：这是一个标准的合取范式 (CNF) 公式，表示由 k 个子句通过“与”逻辑连接而成，每个子句是三个文字的“或”组合。 2. $$

$$ **解释**：这是一个上下文无关文法 (CFG) 的例子，用于练习题 7.4 中，定义了一套产生式规则。 3. $$

$$ **解释**：这是一个布尔可满足性问题的具体实例，用于练习题 7.5，询问该公式是否可满足。 4. $$

$$ **解释**：这是在 **SUBSET-SUM** 归约中，为变量和子句构造的数字集合 S 的一部分的符号表示。 ## 3.4. 详细证明 [原文] 证明 我们之前已证明 **HAMPATH** 属于 **NP**，因此剩下要做的就是证明 3**SAT** $\leq_{\mathrm{P}}$ **HAMPATH**。对于每个 3 **cnf**-公式 $\phi$，我们展示如何构造一个有向图 $G$，其中包含两个节点 $s$ 和 $t$，当且仅当 $\phi$ 是可满足的时，存在一条从 $s$ 到 $t$ 的哈密顿路径。 我们从包含 $k$ 个子句的 3 **cnf**-公式 $\phi$ 开始， $$

$$ 其中每个 $a, b$ 和 $c$ 是文字 $x_{i}$ 或 $\overline{x_{i}}$。令 $x_{1}, \ldots, x_{l}$ 为 $\phi$ 的 $l$ 个变量。 现在我们展示如何将 $\phi$ 转换为图 $G$。我们构造的图 $G$ 包含用于表示 $\phi$ 中出现的变量和子句的各个部分。 [逐步解释] 这部分正式开始进行 **3SAT 到 HAMPATH** 归约的构造性证明。 1. **“我们之前已证明 HAMPATH 属于 NP...”**: 再次确认 **NP-完全**性证明的第一步已经完成。 2. **“...剩下要做的就是证明 3SAT $\leq_{\mathrm{P}}$ HAMPATH。”**: 明确了当前证明的核心任务：构造一个从 **3SAT** 到 **HAMPATH** 的**多项式时间归约**。 3. **“对于每个 3 cnf-公式 $\phi$，我们展示如何构造一个有向图 $G$，其中包含两个节点 $s$ 和 $t$...”**: 这里描述了归约的输入和输出。 * **输入**: 任意一个 **3SAT** 公式的实例 $\phi$。 * **输出**: 一个**有向图** $G$ 和图中两个特定的节点，起点 $s$ 和终点 $t$。这个构造过程必须是**多项式时间**的，意味着如果 $\phi$ 的大小为 $n$，构造出图 $G$ 的时间复杂度必须是 $n$ 的某个多项式函数，如 $O(n^2)$。 4. **“...当且仅当 $\phi$ 是可满足的时，存在一条从 $s$ 到 $t$ 的哈密顿路径。”**: 这是对归约正确性的黄金标准要求。它必须建立一个完全等价的桥梁，连接逻辑世界和图论世界。 5. **“我们从包含 $k$ 个子句的 3 cnf-公式 $\phi$ 开始...”**: 设定了输入公式 $\phi$ 的一般形式。 * 它是一个合取范式 (Conjunctive Normal Form, CNF)，由 $k$ 个子句通过“与”($\wedge$)连接。 * 每个子句是三个文字的“或”($\vee$)。 * 文字 (literal) 是指一个变量 $x_i$ 或它的否定 $\overline{x_i}$。 * $\phi$ 中总共有 $l$ 个不同的布尔变量 $x_1, \ldots, x_l$。 6. **“现在我们展示如何将 $\phi$ 转换为图 $G$。我们构造的图 $G$ 包含用于表示 $\phi$ 中出现的变量和子句的各个部分。”**: 预告了接下来的内容将是分步构造图 $G$。这个构造是模块化的，会分别处理变量和子句，也就是引入前面提到的“小工具”。 [公式与符号逐项拆解和推导（若本段含公式）] $$

$$ * $\phi$: 整个布尔公式。 * $\wedge$: 逻辑“与” (AND)。整个公式为真，当且仅当所有由 $\wedge$ 连接的部分都为真。 * $(a_j \vee b_j \vee c_j)$: 表示第 $j$ 个子句 (clause)。 * $\vee$: 逻辑“或” (OR)。一个子句为真，当且仅当其中至少有一个文字为真。 * $a_j, b_j, c_j$: 第 $j$ 个子句中的三个文字 (literal)。 * $x_i, \overline{x_i}$: 文字的具体形式。$x_i$ 是一个变量，$\overline{x_i}$ 是它的否定。例如，如果 $x_1$ 为真，则 $\overline{x_1}$ 为假。 * $l$: 公式中独立变量的总数。 * $k$: 公式中子句的总数。 [具体数值示例] * **输入公式 $\phi$**: $\phi = (x_1 \lor \overline{x_2} \lor x_3) \wedge (\overline{x_1} \lor x_2 \lor \overline{x_3})$ * **参数**: * 变量数 $l = 3$ (变量是 $x_1, x_2, x_3$) * 子句数 $k = 2$ (子句是 $c_1, c_2$) * **输出 (目标)**: 一个有向图 $G$ 和起终点 $s,t$。我们要构造这个 $G$，使得： * 如果 $\phi$ 有满足赋值 (例如 $x_1=$真, $x_2=$真, $x_3=$假，可以满足 $\phi$)，那么 $G$ 中一定有一条 $s-t$ 哈密顿路径。 * 反之，如果在 $G$ 中找到一条 $s-t$ 哈密顿路径，我们一定能据此构造出 $\phi$ 的一个满足赋值。 [易错点与边界情况] * **有向图**: 必须时刻记住我们构造的是**有向图**，边的方向至关重要，它将用来强制路径的流动方向。 * **多项式时间**: 整个构造过程的效率是关键。后面会看到，图的大小（节点数和边数）是关于 $l$ 和 $k$ 的多项式函数，因此可以在多项式时间内完成构造。 [总结] 本段为 **HAMPATH** 的 **NP-完全**性证明设置了舞台。它重申了证明策略（通过从 **3SAT** 进行多项式时间归约来证明 **NP-难**度），并精确定义了归约的输入（一个任意的 3-CNF 公式 $\phi$）和输出（一个有向图 $G$）。最终目标是建立 $\phi$ 的可满足性与 $G$ 中 $s-t$ 哈密顿路径的存在性之间的严格等价关系。 [存在目的] 本段的目的是为复杂的构造过程提供一个清晰的引言和框架。它明确了我们将要做什么（将公式转换为图）以及为什么这么做（为了证明 **HAMPATH** 是 **NP-完全**的）。这使得读者在接触到具体的、看似随意的图构造细节时，能够理解这些细节都是为了服务于“模拟布尔逻辑”这一最终目的。 [直觉心智模型] 想象你是一个翻译，要把一本用“逻辑语言”写的小说（**3SAT** 公式）翻译成用“地图和路线语言”写的冒险指南（**HAMPATH** 问题）。 * 本段就是你的翻译项目简介。 * **项目目标**: 翻译必须是“保真”的，即小说有一个美好的结局（公式可满足），当且仅当冒险指南里存在一条能走通所有地点的完美路线（哈密顿路径）。 * **原料**: 小说由章节（子句）构成，章节里的人物有不同的选择（变量赋值）。 * **成品**: 一张包含起点、终点和许多中间地点的有向地图。 * 接下来的内容就是你的翻译手册，教你如何把小说中的每个元素（变量、子句）翻译成地图上的特定结构（小工具）。 [直观想象] 你是一位建筑师，接到一个奇特的设计任务。 * **客户要求**: 设计一个迷宫（有向图 $G$），有唯一的入口（$s$）和出口（$t$）。 * **设计约束**: 这个迷宫的设计图纸必须与一个给定的逻辑谜题（**3SAT** 公式 $\phi$）相关联。 * **核心要求**: 逻辑谜题有解（可满足），当且仅当有人能找到一条穿过迷宫的路线，这条路线必须不重不漏地访问迷宫中的每一个房间（哈密顿路径）。 * 本段就是这个设计任务的说明书。接下来的内容将告诉你如何根据逻辑谜题的结构，来设计迷宫中的“菱形大厅”（变量）和“关键房间”（子句）。 ### 3.4.1. 变量小工具构造 [原文] 我们用一个包含一行水平节点的菱形结构来表示每个变量 $x_{i}$，如下图所示。稍后我们将指定水平行中出现的节点数量。  图 7.47 将变量 $x_{i}$ 表示为菱形结构 [逐步解释] 这部分开始具体介绍第一个**小工具**——用于模拟变量的**菱形结构**。 1. **“我们用一个...菱形结构来表示每个变量 $x_{i}$”**: * 对于公式中的每一个变量 $x_i, x_2, \ldots, x_l$，我们都在图中构建一个独立的、对应的**变量小工具**。 * 这个小工具的整体形状像一个菱形。它有顶部的入口节点和底部的出口节点，中间是一系列节点。 2. **“包含一行水平节点”**: * 菱形的核心是一串水平排列的节点。图 7.47 中，这些是中间那条长长的、由双向箭头连接的节点链。 * **双向箭头**意味着路径可以在这条链上向左走，也可以向右走。 3. **“如下图所示”**: * 图 7.47 展示了这个结构。它有两个主要部分： * **外壳**: 顶部的节点（我们称之为 $u_{i,top}$）和底部的节点（$u_{i,bottom}$），以及连接它们和水平链两端的边。 * **核心**: 中间的水平节点链。 * 路径从 $u_{i,top}$ 进入，必须经过中间的水平链，最终从 $u_{i,bottom}$ 离开（或者反过来，如果全局结构允许的话）。 * 关键在于，要穿过这条水平链并访问其中的所有节点，只有两种基本方式： * **从左到右遍历**: 路径从左端的节点进入水平链，一路向右访问所有节点，从右端节点离开。 * **从右到左遍历**: 路径从右端的节点进入水平链，一路向左访问所有节点，从左端节点离开。 * 这两种唯一的、覆盖所有内部节点的遍历方式，将完美地对应变量 $x_i$ 的两种赋值：真和假。 4. **“稍后我们将指定水平行中出现的节点数量。”**: * 这是一个重要的伏笔。中间这条水平链到底需要多少个节点？这个数量不是随意的，它必须足够“长”，以容纳与所有子句相关的“岔路口”。 * 具体的节点数量取决于公式中**子句的数量 $k$**。这将在后面详细说明。现在我们只需要理解这个菱形结构的核心功能：强制路径二选一。 [具体数值示例] * 假设我们有一个变量 $x_1$。我们为它构建一个菱形小工具。 * **入口/出口**: 节点 $u_{1,top}, u_{1,bottom}$。 * **水平链**: 假设目前我们只需要 3 个水平节点 $h_{1,1}, h_{1,2}, h_{1,3}$。 * **连接**: * 有向边 $u_{1,top} \to h_{1,1}$ 和 $u_{1,top} \to h_{1,3}$。 * 水平链上的双向边 $h_{1,1} \leftrightarrow h_{1,2} \leftrightarrow h_{1,3}$。 * 有向边 $h_{1,1} \to u_{1,bottom}$ 和 $h_{1,3} \to u_{1,bottom}$。 * **路径选择**: 一条从 $u_{1,top}$ 进入并要访问所有水平节点再到 $u_{1,bottom}$ 的路径，必须是以下两种之一： 1. **真赋值路径 (例如，从左到右)**: $u_{1,top} \to h_{1,1} \to h_{1,2} \to h_{1,3} \to u_{1,bottom}$。 2. **假赋值路径 (例如，从右到左)**: $u_{1,top} \to h_{1,3} \to h_{1,2} \to h_{1,1} \to u_{1,bottom}$。 * 任何其他走法，比如 $u_{1,top} \to h_{1,1} \to u_{1,bottom}$，都会漏掉 $h_{1,2}$ 和 $h_{1,3}$，因此不可能是哈密顿路径的一部分。这个结构成功地强制了二选一。 [易错点与边界情况] * **边的方向**: 必须注意图中箭头的方向。例如，从顶部节点只能进入水平链，不能返回。从水平链只能走向底部节点，不能返回。这保证了路径的单向流动性。 * **“菱形”是比喻**: 这个结构在拓扑上像菱形，但重要的是它的连接属性和它如何限制路径的流动，而不是它的几何形状。 [总结] 本段介绍了 **3SAT 到 HAMPATH** 归约中的**变量小工具**。每个变量都被一个“菱形结构”所代表。这个结构的核心是一条水平的节点链，其设计巧妙地迫使任何希望包含其中所有节点的路径，都必须以两种固定方式之一（例如，从左到右或从右到左）来遍历它。这两种遍历方式将被用来完美地模拟相应变量的“真/假”二元赋值。 [存在目的] 本段的目的是引入归约构造的第一个基本构件。它展示了如何将逻辑世界中抽象的“二元选择”（变量赋值）转化为图论世界中具象的“路径选择”。这是整个复杂归约的第一块基石，为后续引入子句并建立逻辑约束奠定了基础。 [直觉心智模型] 想象一条单行道的两端有两个环岛。中间是双向车道。 * **菱形结构**：就是这两个环岛（顶部/底部节点）加上中间的双向车道（水平链）。 * **哈密顿路径**: 你必须开车从一个环岛到另一个环岛，并且必须经过双向车道上的每一个出口。 * **二选一**: 要做到这一点，你只能完整地从头到尾开一遍双向车道。你要么选择从A环岛进入，开到B环岛；要么从B环岛进入，开到A环岛。没有第三种方法能让你不漏掉任何一个出口。 * **赋值**: 这两种开车方向就代表了变量的两种赋值。 [直观想象] 你正在设计一个“二选一”的开关。 * **菱形结构**: 就是你设计的这个开关的内部机械结构。 * **路径**: 一根滑杆必须从开关的一头滑到另一头。 * **内部节点**: 滑杆上有一排必须被拨动的小齿轮。 * **二选一的遍历**: 要拨动所有小齿轮，滑杆必须选择两条预设的轨道之一来滑动。一条轨道对应“开”状态，另一条对应“关”状态。 * 这个机械开关（变量小工具）将被集成到一个更大的机器（整个图）中。 ### 3.4.2. 子句小工具构造 [原文] 我们用一个节点来表示 $\phi$ 的每个子句，如下所示。  图 7.48 将子句 $c_{j}$ 表示为节点 [逐步解释] 这部分描述了第二个**小工具**——用于表示子句的结构。 1. **“我们用一个节点来表示 $\phi$ 的每个子句”**: * 与变量小工具的复杂结构形成鲜明对比，子句小工具的设计在这里异常简单。 * 对于公式中的每一个子句 $c_1, c_2, \ldots, c_k$，我们就在图中创建一个对应的、单独的节点。 * 图 7.48 中，节点 $c_j$ 就代表了第 $j$ 个子句。 2. **小工具的目的**: * 这个节点本身没有任何特殊的内部结构。它的作用完全体现在它将如何与变量小工具连接，以及哈密顿路径对它的要求。 * **哈密顿路径必须访问图中每一个节点**。这意味着，我们最终构造的路径，必须想办法“绕道”去访问每一个这样的子句节点 $c_j$。 * 这个“必须访问”的约束，将被我们用来模拟“子句必须被满足”的逻辑要求。 [具体数值示例] * **公式 $\phi$**: $\phi = (x_1 \lor \overline{x_2}) \wedge (\overline{x_1} \lor x_2)$ * **子句**: $c_1 = (x_1 \lor \overline{x_2})$ 和 $c_2 = (\overline{x_1} \lor x_2)$。 * **子句小工具**: * 我们在图中创建两个节点，一个叫 $C_1$，另一个叫 $C_2$。 * 在哈密顿路径的规划中，我们必须确保路径会经过 $C_1$，也会经过 $C_2$。 [易错点与边界情况] * **不要低估其简单性**: 初学者可能会觉得这个小工具太简单了，是不是有什么隐藏的复杂性。其实没有。它的力量完全来自于它与变量小工具的外部连接，以及哈密顿路径的全局约束。简单，但有效。 * **与 VERTEX-COVER 的对比**: 回想一下，在 **3SAT 到 VERTEX-COVER** 的归约中，子句小工具是一个三角形，有复杂的内部结构。这里的子句小工具只是一个点。这再次提醒我们，不同的归约问题需要完全不同的、量身定做的**小工具**。 [总结] 本段介绍了 **3SAT 到 HAMPATH** 归约中极其简洁的**子句小工具**：每个子句由图中的一个单节点来代表。它的核心作用是成为哈密顿路径必须访问的一个“打卡点”。这个“必须打卡”的图论要求，将通过巧妙的连接，被转化为“子句必须被满足”的逻辑要求。 [存在目的] 本段引入了归约的第二个基本构件。通过呈现一个设计上极其简单的**子句小工具**，它与复杂的**变量小工具**形成对比，并引导读者思考：这两个功能和形态迥异的小工具将如何协同工作，以实现对布尔逻辑的精确模拟？这为下一阶段介绍全局结构和连接方式做好了铺垫。 [直觉心智模型] 回到电路模型： * **子句小工具**：就是一个指示灯。它本身很简单，就是一个灯泡。 * **哈密顿路径要求**: 最终的电路必须能点亮（访问）所有的指示灯。 * 这个灯泡能否被点亮，不取决于它自己，而取决于连接到它的电线（与变量小工具的连接）以及开关的状态（变量赋值）。 [直观想象] 回到特技飞行挑战： * **子句小工具**：就是一个必须撞破的目标气球。它只是一个静静地飘在那里的气球。 * **哈密顿路径要求**: 你的飞行路线必须规划得能撞破所有这些气球。 * 你能否撞到这个气球，取决于你是否能从某个菱形峡谷中找到一条通往它的“侧飞”航线。气球本身是无辜的，关键在于通往它的路。 ### 3.4.3. 图的全局结构 [原文] 下图描绘了 $G$ 的全局结构。它显示了 $G$ 的所有元素及其关系，除了表示变量与包含它们的子句之间关系的边。  图 7.49 $G$ 的高层结构 [逐步解释] 这部分展示了如何将之前介绍的**变量小工具**和**子句小工具**组装成一个完整的图的“骨架”。 1. **“下图描绘了 $G$ 的全局结构”**: * 图 7.49 不是最终的图，而是高层次的蓝图。它展示了各个主要部件是如何串联起来的。 2. **起点 $s$ 和终点 $t$**: * 图的顶部有一个全局的起点 $s$，底部有一个全局的终点 $t$。哈密顿路径必须从 $s$ 开始，到 $t$ 结束。 3. **变量小工具的串联**: * 所有的**变量小工具**（菱形结构）被像串珠子一样一个接一个地串联起来。 * 路径从起点 $s$ 出发，首先进入第一个变量小工具（代表 $x_1$）。 * 从第一个变量小工具的底部出来后，进入第二个变量小工具（代表 $x_2$）的顶部。 * 这个过程一直持续，直到路径从最后一个变量小工具（代表 $x_l$）的底部出来。 * 最后，从最后一个变量小工具的底部，有一条边指向全局终点 $t$。 * 这种串联结构强制哈密顿路径必须按顺序依次穿过每一个变量小工具。它不能跳过任何一个菱形，也不能打乱顺序。 4. **子句小工具的位置**: * 所有的**子句小工具**（单个节点 $c_1, \ldots, c_k$）被放置在一边，目前看起来是孤立的。它们还没有与主路径连接起来。 5. **缺失的边**: * **“除了表示变量与包含它们的子句之间关系的边”**: 这是本图的关键说明。这张图故意省略了最重要的连接——那些能让路径从**变量小工具**“绕道”去访问**子句小工具**的边。 * 这些缺失的边才是整个归约的灵魂，它们将根据公式 $\phi$ 的具体内容（即哪个子句包含哪个文字）来添加。 [具体数值示例] * **公式**: $\phi$ 有两个变量 $x_1, x_2$ 和三个子句 $c_1, c_2, c_3$。 * **全局结构**: * 一个起点 $s$ 和一个终点 $t$。 * $s$ 连接到 $x_1$ 菱形的顶部。 * $x_1$ 菱形的底部连接到 $x_2$ 菱形的顶部。 * $x_2$ 菱形的底部连接到 $t$。 * 主路径的骨架是: $s \to \text{菱形}_1 \to \text{菱形}_2 \to t$。 * 旁边放着三个孤立的节点: $C_1, C_2, C_3$。 * 下一步的工作就是设计从 $\text{菱形}_1$ 和 $\text{菱形}_2$ 内部的特定位置，引出边来连接 $C_1, C_2, C_3$。 [易错点与边界情况] * **这只是骨架**: 必须清楚这还不是完整的图。如果只看这张图，哈密顿路径是 $s \to ... \to t$，它根本没有访问任何子句节点，所以它不可能是哈密tonian的。这张图只是为了展示主要组件的排列方式。 * **路径的强制流向**: 串联结构和边的方向性共同确保了路径的主干流是固定的、不可更改的，为后续的“绕行”提供了稳定的基础。 [总结] 本段通过图 7.49 展示了所构造的图 $G$ 的高层骨架。它由一个全局的起点 $s$ 和终点 $t$、一串依次串联的变量小工具（菱形结构）、以及一组目前孤立的子句小工具（单个节点）组成。这种布局强制任何从 $s$ 到 $t$ 的哈密顿路径都必须按顺序穿越每一个变量小工具。图中尚未画出的是连接变量和子句小工具的关键边，这些边将赋予图完整的逻辑功能。 [存在目的] 本段的目的是从宏观上展示图的组织结构，让读者对路径的基本流向有一个整体的认识。通过先呈现一个清晰、有序的“骨架”，再在后续步骤中添加复杂的“血肉”（连接边），可以使整个构造过程更有层次感，更易于理解。这是一种“由粗到精”的教学方法。 [直觉心-模型] 想象你在设计一个闯关游戏。 * **全局结构**: 游戏的主线是一条笔直的大道，从起点通往终点。 * **变量小工具**: 大道被分成了 $l$ 个赛段（菱形），你必须按顺序通过每一个赛段。 * **子句小工具**: 在大道两旁，有 $k$ 个必须拾取的宝藏（子句节点）。 * **当前状态**: 你已经铺好了主干道和各个赛段，也把宝藏放在了路边。但你还没有修建任何从主干道通往宝藏的岔路。现在的地图上，你只能沿着主干道走，拿不到任何宝藏。 [直观想象] 你正在组装一根复杂的“魔法棒”。 * **全局结构**: 魔法棒的主体由 $l$ 节“能量核心”（变量小工具）依次串联而成，两端是握柄（$s$）和顶端宝石（$t$）。 * **子句小工具**: 棒身旁边还预留了 $k$ 个插槽，需要镶嵌“符文石”（子句节点）。 * **当前状态**: 你已经把主体的能量核心都串好了，符文石也放在了旁边。但还没有连接任何导线，将能量核心的能量引导至符文石插槽。现在的魔法棒，能量只能从头传到尾，无法激活任何符文石。 ### 3.4.4. 菱形结构内部细节 [原文] 接下来，我们展示如何将表示变量的菱形连接到表示子句的节点。每个菱形结构都包含一行水平节点，这些节点由双向边连接。水平行除了菱形两端的两个节点外，还包含 $3k+1$ 个节点。这些节点被分组为相邻对，每个子句一对，并在每对旁边附加分隔节点，如下图所示。  图 7.50 菱形结构中的水平节点 [逐步解释] 这部分揭示了之前被“藏起来”的菱形结构内部的精确设计，这是整个归约最精巧的部分之一。 1. **“每个菱形结构都包含一行水平节点...”**: 重申了菱形的核心是水平链。 2. **“水平行除了菱形两端的两个节点外，还包含 $3k+1$ 个节点。”**: 这里终于给出了水平链的精确长度。 * $k$ 是公式中子句的数量。 * 这条链的长度与子句数量 $k$ 相关，这暗示了它的设计目的就是为了与所有 $k$ 个子句产生联系。 * 为什么是 $3k+1$？这个数字不是随意的。 3. **“这些节点被分组为相邻对，每个子句一对...”**: * 在这一长串水平节点中，我们为**每一个**子句 $c_1, c_2, \ldots, c_k$ 都预留了一对相邻的节点。 * 例如，图 7.50 中，标有“for $c_1$”的那两个节点，就是为子句 $c_1$ 准备的“岔路口”。标有“for $c_j$”的两个节点是为子句 $c_j$ 准备的，以此类推。 * 总共有 $k$ 个子句，所以需要 $k$ 对节点，即 $2k$ 个节点。 4. **“...并在每对旁边附加分隔节点...”**: * 在每两对“子句节点对”之间，以及在链的两端，都插入了一个“分隔节点 (separator node)”。 * 看图 7.50，左右两端各有一个分隔节点，每两个“for $c_j$”的节点对之间也有一个分隔节点。 * 如果有 $k$ 个节点对，那么它们之间就有 $k-1$ 个空隙，需要 $k-1$ 个分隔节点。再加上两端各一个，总共需要 $(k-1)+2 = k+1$ 个分隔节点。 * **总节点数验证**: $k$ 个节点对（$2k$ 个节点） + $(k+1)$ 个分隔节点 = $3k+1$ 个节点。这与前面给出的数字完全吻合。 5. **分隔节点的目的**: * 分隔节点的作用是**隔离**。它们确保从一个“子句节点对”出发的绕行，必须回到这个节点对本身，而不能“跳”到相邻的另一个节点对去。它们像防火墙一样，保证了每个子句的逻辑是独立处理的。这是防止出现意外“短路”的关键设计。 [具体数值示例] * **公式**: $\phi$ 有 $l=2$ 个变量 ($x_1, x_2$) 和 $k=3$ 个子句 ($c_1, c_2, c_3$)。 * **考虑变量 $x_1$ 的菱形小工具**: * 它的水平链需要有 $3k+1 = 3*3+1 = 10$ 个中间节点。 * **结构**: * 分隔节点1 * 为 $c_1$ 准备的节点对 (2个) * 分隔节点2 * 为 $c_2$ 准备的节点对 (2个) * 分隔节点3 * 为 $c_3$ 准备的节点对 (2个) * 分隔节点4 * 总节点数: $1+2+1+2+1+2+1 = 10$。 * 这 10 个节点和菱形两端的出入节点，共同构成了 $x_1$ 的变量小工具。变量 $x_2$ 的小工具也具有完全相同的内部结构。 [易错点与边界情况] * **每个变量都有完整的结构**: 必须理解，是**每一个**菱形小工具内部都包含了为**所有** $k$ 个子句准备的节点对。变量 $x_1$ 的菱形里有为 $c_1, c_2, ..., c_k$ 准备的岔路口；变量 $x_2$ 的菱形里也有一套完整的、为 $c_1, c_2, ..., c_k$ 准备的岔路口。 * **分隔节点的重要性**: 如果没有分隔节点，那么当路径从 $c_j$ 的节点对绕行出去后，可能会错误地返回到 $c_{j+1}$ 的节点对中，这将导致逻辑混乱，归约失败。 [总结] 本段详细揭示了**变量小工具**中水平节点链的精密内部结构。这条链的长度被确定为 $3k+1$（其中 $k$ 是子句总数），并被划分为 $k$ 个“子句节点对”和 $k+1$ 个“分隔节点”。每个节点对都将作为与特定子句进行交互的“接口”或“岔路口”，而分隔节点则起到了关键的隔离作用，确保不同子句的逻辑不会互相干扰。这个设计为将变量的路径选择与所有子句的满足状态联系起来做好了准备。 [存在目的] 本段的目的是深入到**小工具**设计的核心，展示其复杂性和精巧性。它回答了“菱形中间那条线到底是什么”的问题。通过揭示这个由节点对和分隔符组成的重复结构，它为下一步连接变量和子句的操作提供了具体的“锚点”，让读者明白连接将发生在这些预留好的“接口”上。 [直觉心-模型] 回到闯关游戏的主干道赛段（菱形）。 * **水平链的结构**: 每个赛段（变量）的道路不是平坦的，而是由一系列“特殊区域”组成的。 * **子句节点对**: 对应子句 $c_j$ 的“特殊区域”，是一个包含两个并排停车位的“服务区”。这是唯一可以临时离开主路的地方。 * **分隔节点**: 每两个服务区之间都有一个“收费站”。你必须通过收费站才能到下一个服务区。这个收费站确保你从一个服务区离开后，不能直接开到另一个服务区的停车场里，只能回到主路上。 * 这个设计意味着，如果你想从赛段 $x_i$ 的主路去拿宝藏 $c_j$，你必须在为 $c_j$ 预留的那个服务区驶离主路。 [直观想象] 回到魔法棒的能量核心（菱形）。 * **水平链的结构**: 能量核心的内部是一串水晶。 * **子句节点对**: 其中某些成对的水晶是“接口水晶”，它们是为特定的符文石（子句）准备的能量输出端口。 * **分隔节点**: 在每对“接口水晶”之间，都有一种“绝缘水晶”，防止能量从一个端口泄漏到另一个端口。 * 当能量（路径）流过这串水晶时，它可以在“接口水晶”的位置被引导出去，为对应的符文石充能。绝缘水晶保证了能量流的精确控制。 ### 3.4.5. 连接小工具：正文字 [原文] 如果变量 $x_{i}$ 出现在子句 $c_{j}$ 中，我们从第 $i$ 个菱形中的第 $j$ 对向第 $j$ 个子句节点添加以下两条边。  图 7.51 当子句 $c_{j}$ 包含 $x_{i}$ 时附加的边 [逐步解释] 这部分和下一部分是归约的“点睛之笔”，它们最终将**变量小工具**和**子句小工具**连接起来，从而注入布尔逻辑。 1. **“如果变量 $x_{i}$ 出现在子句 $c_{j}$ 中...”**: * 这是添加边的**条件**。我们现在开始根据公式 $\phi$ 的具体内容来画边。 * 我们检查每一个子句 $c_j$ 中的每一个文字。这个规则处理的是**正文字**（没有“非”的变量，如 $x_i$）。 2. **“...我们从第 $i$ 个菱形中的第 $j$ 对...”**: * **第 $i$ 个菱形**: 指的是代表变量 $x_i$ 的那个**变量小工具**。 * **第 $j$ 对**: 指的是在该菱形的水平链上，我们为子句 $c_j$ 预留的那一对相邻的节点。 3. **“...向第 $j$ 个子句节点添加以下两条边。”**: * **第 $j$ 个子句节点**: 指的是代表子句 $c_j$ 的那个单节点（我们称之为 $C_j$）。 * 我们添加的不是一条边，而是**两条有向边**，形成一个“绕行”的回路。 4. **图 7.51 的解释**: * 图中展示了变量 $x_i$ 菱形中为子句 $c_j$ 准备的节点对，我们称它们为 $u_{i,j,left}$ 和 $u_{i,j,right}$。 * 添加的边是： * 一条从 $u_{i,j,left}$ 指向子句节点 $C_j$ 的有向边。 * 一条从子句节点 $C_j$ 指向 $u_{i,j,right}$ 的有向边。 * 这两条边形成了一个路径片段: $... \to u_{i,j,left} \to C_j \to u_{i,j,right} \to ...$ 5. **这个连接的逻辑含义**: * 这两条边的方向是关键。它们允许路径在从左到右经过这对节点时，顺畅地“绕道”访问 $C_j$。 * 回忆一下，我们将变量小工具的“从左到右”遍历与变量赋值为“真”相关联。 * 因此，这个连接结构意味着：**如果 $x_i$ 被赋值为真（路径从左到右走），那么在经过为子句 $c_j$ 预留的岔路口时，路径就有机会去访问 $c_j$ 对应的子句节点。** * 如果路径是“从右到左”走的（$x_i$ 赋值为假），那么在经过这对节点时，流向是 $... \to u_{i,j,right} \to u_{i,j,left} \to ...$。此时，边 $u_{i,j,left} \to C_j$ 是顺行的，但 $C_j \to u_{i,j,right}$ 是逆行的。路径无法从 $C_j$ 返回到主路上，所以这条绕行路径是**不可用**的。 [具体数值示例] * **公式**: $\phi$ 包含子句 $c_2 = (x_1 \lor x_3 \lor \overline{x_4})$。 * **我们关注文字 $x_1$ 和子句 $c_2$**: * 因为 $c_2$ 包含正文字 $x_1$。 * **操作**: * 找到代表变量 $x_1$ 的第 1 个菱形。 * 在这个菱形的水平链上，找到为子句 $c_2$ 预留的第 2 对节点。我们称之为 $(u_{1,2,L}, u_{1,2,R})$。 * 找到代表子句 $c_2$ 的单节点 $C_2$。 * 添加两条有向边：$u_{1,2,L} \to C_2$ 和 $C_2 \to u_{1,2,R}$。 * **结果**: * 如果我们将 $x_1$ 赋值为真，那么哈密顿路径将从左到右穿过 $x_1$ 的菱形。当它走到 $u_{1,2,L}$ 时，它可以选择岔路 $u_{1,2,L} \to C_2 \to u_{1,2,R}$，这样就成功访问了 $C_2$，然后再继续向右走。 * 如果我们将 $x_1$ 赋值为假，路径从右到左走。当它走到 $u_{1,2,R}$ 时，它无法使用这条岔路，因为它无法从 $C_2$ 回到 $u_{1,2,R}$（箭头方向反了）。 [易错点与边界情况] * **边的方向至关重要**: 哪怕只有一条边的方向画反，整个归约的逻辑就会崩溃。这个“左进右出”的设计是专门为“从左到右”的路径服务的。 * **一一对应**: 必须为公式中每一个正文字的每一次出现，都添加这样一对边。如果一个变量 $x_i$ 出现在多个子句中，那么在 $x_i$ 的菱形里，将会有多个节点对引出边，分别连向不同的子句节点。 [总结] 本段描述了如何为公式中的**正文字**添加连接边。当子句 $c_j$ 包含变量 $x_i$ 时，就在 $x_i$ 的变量小工具中为 $c_j$ 预留的节点对上，构建一个“左进右出”的、通向子句节点 $C_j$ 的有向回路。这个结构的功能是：只有当 $x_i$ 被赋值为“真”（对应于路径从左到右遍历）时，哈密顿路径才能利用这个回路去“访问”子句节点 $C_j$。这成功地将逻辑“或”的一部分——“如果 $x_i$ 为真，则 $c_j$ 满足”——翻译成了图论中的路径可能性。 [存在目的] 本段的目的是开始填充图的“血肉”，注入具体的逻辑关系。它是将之前孤立的变量和子句小工具联系起来的第一步。通过展示这个非对称的、依赖于路径方向的连接方式，它揭示了整个归约机制的核心：利用有向边来模拟逻辑蕴含。 [直觉心智模型] 回到闯关游戏： * **条件**: 宝藏 $c_j$ 的说明书上写着：“需要 $x_i$ 的‘真能量’才能获取”。 * **操作**: 在赛段 $x_i$ 的主干道上，为 $c_j$ 预留的服务区，你修建了一条单行道的岔路。这条岔路从服务区的入口（左边停车位）出发，绕到宝藏 $c_j$ 的位置，再从服务区的出口（右边停车位）汇入主路。 * **效果**: 只有当你选择“从左到右”通过这个赛段时（$x_i$ 为真），你才能顺畅地开上这条岔路，拿到宝藏，再开回主路。如果你是“从右到左”开的，这条岔路就是逆行，你上不去。 [直观想象] 回到魔法棒： * **条件**: 符文石 $c_j$ 需要由能量核心 $x_i$ 在“正向转动”（$x_i$=真）时产生的能量来激活。 * **操作**: 在能量核心 $x_i$ 内部，为符文石 $c_j$ 预留的“接口水晶”对上，你连接了两根特殊的单向“能量导管”。一根从左边水晶导出能量到符文石，另一根从符文石导回能量到右边水晶。 * **效果**: 只有当能量是“从左到右”流过核心时（$x_i$=真），能量才能顺着导管流出去，激活符文石，再流回来。如果能量是反向流动的，导管的单向阀会阻止能量的激活回路。 ### 3.4.6. 连接小工具：负文字 [原文] 如果 $\overline{x_{i}}$ 出现在子句 $c_{j}$ 中，我们从第 $i$ 个菱形中的第 $j$ 对向第 $j$ 个子句节点添加两条边，如图 7.52 所示。 在我们添加完与每个 $x_{i}$ 或 $\overline{x_{i}}$ 在每个子句中出现的对应边后，$G$ 的构造就完成了。为了证明这个构造是有效的，我们论证如果 $\phi$ 是可满足的，则存在从 $s$ 到 $t$ 的哈密顿路径；反之，如果存在这样的路径，则 $\phi$ 是可满足的。  图 7.52 当子句 $c_{j}$ 包含 $\overline{x_{i}}$ 时附加的边 [逐步解释] 这部分与上一部分对称，处理的是**负文字**（带“非”的变量，如 $\overline{x_i}$）的情况。 1. **“如果 $\overline{x_{i}}$ 出现在子句 $c_{j}$ 中...”**: * 这是添加边的另一个**条件**，针对负文字。 2. **“...我们从第 $i$ 个菱形中的第 $j$ 对向第 $j$ 个子句节点添加两条边，如图 7.52 所示。”**: * 与正文字情况类似，我们同样在变量 $x_i$ 的菱形中，找到为子句 $c_j$ 预留的那对节点。 * 但是，这次添加的边的方向**正好相反**。 3. **图 7.52 的解释**: * 我们仍然使用节点对 $u_{i,j,left}$ 和 $u_{i,j,right}$。 * 添加的边是： * 一条从 $u_{i,j,right}$ 指向子句节点 $C_j$ 的有向边。 * 一条从子句节点 $C_j$ 指向 $u_{i,j,left}$ 的有向边。 * 这两条边形成了一个路径片段: $... \to u_{i,j,right} \to C_j \to u_{i,j,left} \to ...$ 4. **这个连接的逻辑含义**: * 这个“右进左出”的结构，是专门为“从右到左”的路径服务的。 * 我们将变量小工具的“从右到左”遍历与变量赋值为“假”相关联。 * 因此，这个连接结构意味着：**如果 $x_i$ 被赋值为假（即 $\overline{x_i}$ 为真，路径从右到左走），那么在经过为子句 $c_j$ 预留的岔路口时，路径就有机会去访问 $c_j$ 对应的子句节点。** * 如果路径是“从左到右”走的（$x_i$ 赋值为真），那么在经过这对节点时，流向是 $... \to u_{i,j,left} \to u_{i,j,right} \to ...$。此时，通往 $C_j$ 的岔路是逆行的，**不可用**。 5. **“在我们添加完...对应边后，$G$ 的构造就完成了。”**: * 这是一个重要的阶段性总结。我们已经描述了图中所有的节点和边：起点/终点，串联的变量小工具（内部有精细结构），孤立的子句节点，以及根据公式内容添加的、连接变量和子句的“逻辑边”。至此，从公式 $\phi$ 到图 $G$ 的转换算法已经完整描述完毕。 6. **“为了证明这个构造是有效的...”**: * 预告了接下来的内容将是证明这个构造确实建立了“可满足性”与“哈密顿路径”之间的等价关系。这将是整个定理证明的高潮部分。 [具体数值示例] * **公式**: $\phi$ 包含子句 $c_2 = (x_1 \lor x_3 \lor \overline{x_4})$。 * **我们关注文字 $\overline{x_4}$ 和子句 $c_2$**: * 因为 $c_2$ 包含负文字 $\overline{x_4}$。 * **操作**: * 找到代表变量 $x_4$ 的第 4 个菱形。 * 在这个菱形的水平链上，找到为子句 $c_2$ 预留的第 2 对节点。我们称之为 $(u_{4,2,L}, u_{4,2,R})$。 * 找到代表子句 $c_2$ 的单节点 $C_2$。 * 添加两条有向边：$u_{4,2,R} \to C_2$ 和 $C_2 \to u_{4,2,L}$。 * **结果**: * 如果我们将 $x_4$ 赋值为假 ($\overline{x_4}$ 为真)，那么哈密顿路径将从右到左穿过 $x_4$ 的菱形。当它走到 $u_{4,2,R}$ 时，它可以选择岔路 $u_{4,2,R} \to C_2 \to u_{4,2,L}$，成功访问 $C_2$，然后再继续向左走。 * 如果我们将 $x_4$ 赋值为真，路径从左到右走。当它走到 $u_{4,2,L}$ 时，它无法使用这条岔路。 [易错点与边界情况] * **对称性**: 正文字和负文字的连接方式是中心对称的，一个服务于“左到右”路径，另一个服务于“右到左”路径。这种对称性是模拟布尔逻辑“真/假”的关键。 * **一个节点对，多种可能**: 在一个变量 $x_i$ 的菱形中，为子句 $c_j$ 预留的节点对 $(u_{i,j,L}, u_{i,j,R})$，最多只会引出一种岔路。如果 $c_j$ 中同时包含 $x_i$ 和 $\overline{x_i}$（虽然在 3SAT 中不常见，但理论上可能），那么这个归约可能会出问题。但标准的 3SAT 问题通常假设每个子句中的文字对应的变量是不同的。 [总结] 本段完整了连接边的构造，描述了如何为**负文字**添加边。当子句 $c_j$ 包含 $\overline{x_i}$ 时，就在 $x_i$ 菱形中为 $c_j$ 预留的节点对上，构建一个“右进左出”的、通向子句节点 $C_j$ 的有向回路。这个结构确保了只有当 $x_i$ 被赋值为“假”（对应路径从右到左遍历）时，才有机会访问 $C_j$。至此，从 3-CNF 公式 $\phi$ 到有向图 $G$ 的完整构造过程已经全部描述完毕，下一步将是对其正确性进行严格证明。 [存在目的] 本段的目的是完成图的构造，并建立与正文字情况完全对称的逻辑。它使得变量的两种赋值（两种遍历方向）都能有选择地、正确地影响子句的满足状态。在完成了所有部分的构造后，本段也起到了一个承上启下的作用，宣告物理构造阶段结束，逻辑证明阶段即将开始。 [直觉心智模型] 回到闯关游戏： * **条件**: 宝藏 $c_j$ 的说明书上写着：“需要 $x_i$ 的‘假能量’才能获取”。 * **操作**: 在赛段 $x_i$ 的主干道上，为 $c_j$ 预留的服务区，你修建了另一条单行道岔路。这条路从服务区的出口（右边停车位）出发，绕到宝藏，再从入口（左边停车位）汇入主路。 * **效果**: 只有当你选择“从右到左”通过这个赛段时（$x_i$ 为假），你才能顺畅地使用这条岔路。如果你是“从左到右”开的，这条路就是逆行。 [直观想象] 回到魔法棒： * **条件**: 符文石 $c_j$ 需要由能量核心 $x_i$ 在“反向转动”（$x_i$=假）时产生的能量来激活。 * **操作**: 在为 $c_j$ 预留的“接口水晶”对上，你连接了两根方向相反的“能量导管”：一根从右边水晶导出能量，另一根导回能量到左边水晶。 * **效果**: 只有当能量是“从右到左”流过核心时（$x_i$=假），能量才能激活符文石。 * **构造完成**: 现在，魔法棒上所有的导线都已连接完毕。每个能量核心（变量）的转动方向（赋值），都决定了它能为哪些符文石（子句）提供能量。 ### 3.4.7. 正确性证明（一）：可满足 $\Rightarrow$ 哈密顿路径 [原文] 假设 $\phi$ 是可满足的。为了演示一条从 $s$ 到 $t$ 的哈密顿路径，我们首先忽略子句节点。路径从 $s$ 开始，依次经过每个菱形，并最终到达 $t$。要经过菱形中的水平节点，路径要么从左到右之字形行进，要么从右到左之字形行进；$\phi$ 的满足赋值决定了哪种方式。如果 $x_{i}$ 被赋值为真，路径之字形穿过相应的菱形。如果 $x_{i}$ 被赋值为假，路径反之字形行进。我们将在下图中展示两种可能性。  图 7.53 由满足赋值决定的菱形之字形和反之字形遍历 到目前为止，这条路径覆盖了 $G$ 中除了子句节点外的所有节点。我们可以通过在水平节点处增加绕行轻松地包含它们。在每个子句中，我们选择一个通过满足赋值被赋值为 TRUE 的文字。 如果我们在子句 $c_{j}$ 中选择了 $x_{i}$，我们可以在第 $i$ 个菱形中的第 $j$ 对处绕行。这样做是可能的，因为 $x_{i}$ 必须为 TRUE，所以路径以之字形从左到右穿过相应的菱形。因此，通往 $c_{j}$ 节点的边顺序正确，允许绕行并返回。 类似地，如果我们在子句 $c_{j}$ 中选择了 $\overline{x_{i}}$，我们可以在第 $i$ 个菱形中的第 $j$ 对处绕行，因为 $x_{i}$ 必须为 FALSE，所以路径以反之字形从右到左穿过相应的菱形。因此，通往 $c_{j}$ 节点的边同样顺序正确，允许绕行并返回。（请注意，子句中的每个真文字都提供了绕行以到达子句节点的一个选项。因此，如果一个子句中有多个文字为真，则只进行一次绕行。）因此，我们构造了所需的哈密顿路径。 [逐步解释] 这部分开始证明的第一个方向：如果 $\phi$ 可满足，那么我们一定能在图 $G$ 中构造出一条哈密顿路径。 1. **“假设 $\phi$ 是可满足的。”**: 这是证明的前提。我们已经有了一个确定的、能让所有子句都为真的赋值方案。 2. **“路径从 $s$ 开始，依次经过每个菱形，并最终到达 $t$。”**: 我们先规划路径的主干。根据全局结构，路径必须是 $s \to \text{菱形}_1 \to \text{菱形}_2 \to \cdots \to \text{菱形}_l \to t$。 3. **“$\phi$ 的满足赋值决定了哪种方式。”**: 这是关键的第一步。我们根据已知的满足赋值，来确定穿越每个菱形的方式。 * **如果 $x_i$ 为真**: 路径“从左到右”穿过第 $i$ 个菱形。原文用“之字形 (zig-zag)”来描述，如图 7.53 上半部分所示，路径在水平链的上下两层节点（原文之前的图示比较模糊，这里才揭示水平链其实有两层，或者说这里的“之字形”是指在节点对之间移动）之间交替前进。简单理解就是“左到右”遍历。 * **如果 $x_i$ 为假**: 路径“从右到左”穿过第 $i$ 个菱形。原文用“反之字形 (zag-zig)”描述，如图 7.53 下半部分所示。简单理解就是“右到左”遍历。 4. **“到目前为止，这条路径覆盖了 $G$ 中除了子句节点外的所有节点。”**: 我们沿着这个由赋值决定的主干路径走，已经访问了 $s, t$ 以及所有变量小工具内部的全部节点。唯一被遗漏的，就是那些代表子句的单节点。 5. **“我们可以通过在水平节点处增加绕行轻松地包含它们。”**: 下一步就是修改主干路径，加入对子句节点的访问。 6. **“在每个子句中，我们选择一个通过满足赋值被赋值为 TRUE 的文字。”**: * 因为 $\phi$ 是可满足的，所以每个子句 $c_j$ 都至少有一个真文字。我们随便选一个。 * 对于每个子句 $c_j$，我们指定一个“负责”满足它的真文字，记为 $L_j$。 7. **“如果我们在子句 $c_j$ 中选择了 $x_i$...”**: * 这意味着 $L_j = x_i$。根据赋值，$x_i$ 必须为真。 * 因此，路径在穿过第 $i$ 个菱形时，是“从左到右”走的。 * 当路径走到为 $c_j$ 预留的节点对 $(u_{i,j,L}, u_{i,j,R})$ 时，由于路径是“从左到右”，并且我们之前为正文字 $x_i$ 添加了 $u_{i,j,L} \to C_j \to u_{i,j,R}$ 的边，所以路径可以自然地扩展为：$... \to u_{i,j,L} \to C_j \to u_{i,j,R} \to ...$。 * 我们通过这个“绕行”，成功地将子句节点 $C_j$ 加入了路径。 8. **“类似地，如果我们在子句 $c_j$ 中选择了 $\overline{x_i}$...”**: * 这意味着 $L_j = \overline{x_i}$。根据赋值，$x_i$ 必须为假。 * 因此，路径在穿过第 $i$ 个菱形时，是“从右到左”走的。 * 当路径走到为 $c_j$ 预留的节点对 $(u_{i,j,L}, u_{i,j,R})$ 时，由于路径是“从右到左”，并且我们之前为负文字 $\overline{x_i}$ 添加了 $u_{i,j,R} \to C_j \to u_{i,j,L}$ 的边，所以路径可以自然地扩展为：$... \to u_{i,j,R} \to C_j \to u_{i,j,L} \to ...$。 * 我们同样通过这个“绕行”，成功地将子句节点 $C_j$ 加入了路径。 9. **“如果一个子句中有多个文字为真，则只进行一次绕行。”**: * 这是一个重要的澄清。一个子句可能被多个真文字满足，这意味着我们有多个“绕行”的机会。例如，如果 $c_j=(x_1 \lor x_2 \lor ...)$ 且 $x_1, x_2$ 都为真，我们既可以在 $x_1$ 菱形里绕行访问 $C_j$，也可以在 $x_2$ 菱形里绕行访问。 * 为了构造一条哈密顿路径（每个节点只访问一次），我们只需要为每个子句节点 $C_j$ **选择一次**绕行即可。随便选哪个可用的机会都行。 10. **“因此，我们构造了所需的哈密顿路径。”**: * 我们从一个满足赋值出发，构造了一条路径。这条路径从 $s$ 到 $t$，按顺序访问了所有菱形内部的全部节点，并且通过为每个子句选择一个满足它的真文字，找到了一条对应的绕行路径，从而访问了所有子句节点。 * 最终，这条路径访问了图中的所有节点，且每个节点恰好一次。因此，它是一条哈密顿路径。证明完毕。 [具体数值示例] * **公式**: $\phi = (x_1 \lor \overline{x_2}) \wedge (x_2 \lor x_3)$ * **满足赋值**: $x_1=$ 真, $x_2=$ 真, $x_3=$ 假。 * **路径构造**: 1. **主干路径方向**: * $x_1$ 为真：在菱形1中“从左到右”走。 * $x_2$ 为真：在菱形2中“从左到右”走。 * $x_3$ 为假：在菱形3中“从右到左”走。 2. **子句满足情况**: * $c_1 = (x_1 \lor \overline{x_2})$: $x_1$ 为真，满足 $c_1$。 * $c_2 = (x_2 \lor x_3)$: $x_2$ 为真，满足 $c_2$。 3. **选择绕行**: * **对于 $C_1$**: 我们选择用真文字 $x_1$ 来访问它。因为 $x_1$ 为真，路径在菱形1中从左到右走。当走到为 $c_1$ 预留的节点对时，路径可以使用“左进右出”的岔路去访问 $C_1$。 * **对于 $C_2$**: 我们选择用真文字 $x_2$ 来访问它。因为 $x_2$ 为真，路径在菱形2中从左到右走。当走到为 $c_2$ 预留的节点对时，路径可以使用“左进右出”的岔路去访问 $C_2$。 * **最终路径**: 一条从 $s$ 开始，按“左到右”方式穿过菱形1（中途绕行访问 $C_1$），然后按“左到右”方式穿过菱形2（中途绕行访问 $C_2$），再按“右到左”方式穿过菱形3，最后到达 $t$ 的路径。这条路径访问了所有节点，是一条哈密顿路径。 [易错点与边界情况] * **“之字形”的误导**: 图 7.53 中画出的“之字形”路径可能暗示水平链有两行节点。更简单的理解是，无论内部如何“之字”，其关键作用就是提供了两种从头到尾的遍历方式（左到右/右到左），并且路径方向决定了哪种岔路（正文字/负文字）是可用的。 * **只绕行一次**: 强调只为每个子句节点选择一次绕行，是保证路径简单性（不重复访问节点）的关键。 [总结] 本段完成了 **HAMPATH** 归约正确性证明的第一个方向。它展示了如何将一个已知的 **3SAT** 满足赋值，系统地“翻译”成一条哈密顿路径。该过程分为两步：首先，根据变量的真假值确定穿越每个菱形主干道的方向（左到右/右到左）；然后，利用每个子句都至少有一个真文字这一事实，为每个子句节点选择一个可用的“绕行岔路”将其并入主路径。最终构造出的路径覆盖了图中所有节点，从而证明了哈密顿路径的存在性。 [存在目的] 本段的目的是为了严谨地证明“可满足 $\Rightarrow$ 哈密顿路径”。它将之前描述的、看似静态的图结构动态化，展示了路径如何在这些结构中流动，以及这种流动是如何精确地被布尔赋值所控制的。这是连接逻辑世界和图论世界的关键桥梁之一。 [直觉心-模型] 回到特技飞行挑战： * **前提**: 你已经找到了一套完美的航线选择方案（满足赋值），可以让你撞破所有气球。 * **路径构造**: 1. 你为每个菱形峡谷（变量）确定了飞行方式（“Z”字形或反“Z”字形），对应变量的真假。 2. 对于每个目标气球（子句），因为你的方案是完美的，所以你至少有一条通往它的“侧飞”航线是可用的。 3. 你为每个气球只选择一条侧飞航线来撞破它。 4. 你将所有这些飞行路线（主航线+侧飞）串联起来，就得到了一条从起点到终点，飞越所有峡谷，撞破所有气球的完整、不重复的飞行路径。这就是哈密顿路径。 [直观想象] 你是一位城市规划师，正在验证一份“完美交通流”方案（满足赋值）。 * **方案**: 方案为城市里每条“二选一”的单行道（变量菱形）都指定了当天的行驶方向。 * **验证**: 1. 你根据方案，绘制出主干道的交通流。 2. 这个城市里有 $k$ 个必须打卡的“地标”（子句节点）。 3. 由于方案是完美的，对于每个地标，都至少有一条从主干道出发的“观景环路”是顺行的。 4. 你规划一条公交线路：沿着主干道交通流行驶，每到一个地标对应的“观景环路”路口，如果环路是顺行的，就开进去打个卡再出来（只为每个地标打卡一次）。 5. 你最终画出的这条公交线路，就是一条访问了城市里所有路口（节点）的哈密顿路径。 ### 3.4.8. 正确性证明（二）：哈密顿路径 $\Rightarrow$ 可满足 [原文] 对于反方向，如果 $G$ 有一条从 $s$ 到 $t$ 的哈密顿路径，我们演示 $\phi$ 的一个满足赋值。如果哈密顿路径是正常的——即，除了到子句节点的绕行之外，它按顺序从上到下穿过菱形——我们可以很容易地获得满足赋值。如果路径之字形穿过菱形，我们将相应的变量赋值为 TRUE；如果它反之字形穿过，我们赋值为 FALSE。因为每个子句节点都出现在路径上，通过观察它是如何绕行到达的，我们可以确定相应子句中的哪个文字为真。 剩下的就是证明哈密顿路径必须是正常的。非正常情况只可能发生：路径从一个菱形进入一个子句节点，但返回到另一个菱形，如下图所示。  图 7.54 这种情况不可能发生 路径从节点 $a_{1}$ 到 $c$；但它不是返回到同一菱形中的 $a_{2}$，而是返回到不同菱形中的 $b_{2}$。如果发生这种情况，$a_{2}$ 或 $a_{3}$ 必须是分隔节点。如果 $a_{2}$ 是分隔节点，那么进入 $a_{2}$ 的唯一边将来自 $a_{1}$ 和 $a_{3}$。如果 $a_{3}$ 是分隔节点，$a_{1}$ 和 $a_{2}$ 将在同一子句对中，因此进入 $a_{2}$ 的唯一边将来自 $a_{1}$、$a_{3}$ 和 $c$。在任何一种情况下，路径都不能包含节点 $a_{2}$。路径不能从 $c$ 或 $a_{1}$ 进入 $a_{2}$，因为路径从这些节点去往别处。路径不能从 $a_{3}$ 进入 $a_{2}$，因为 $a_{3}$ 是 $a_{2}$ 指向的唯一可用节点，所以路径必须通过 $a_{3}$ 离开 $a_{2}$。因此，哈密顿路径必须是正常的。这个归约显然在多项式时间内完成，证明完毕。 [逐步解释] 这部分证明了更难的另一个方向：如果图中存在一条哈密顿路径，那么我们一定能据此构造出 $\phi$ 的一个满足赋值。 1. **“如果 $G$ 有一条从 $s$ 到 $t$ 的哈密顿路径，我们演示 $\phi$ 的一个满足赋值。”**: 这是本部分的目标。 2. **“如果哈密顿路径是正常的...我们可以很容易地获得满足赋值。”**: * 首先，定义什么是“**正常路径**”：一条路径，它严格按照 $s \to \text{菱形}_1 \to \text{菱形}_2 \to \cdots \to t$ 的顺序前进，唯一的“偏离”是从某个菱形内部出去访问一个子句节点，然后**必须立即返回**到它出发的那个菱形中，继续前进。 * 如果路径是“正常的”，构造赋值就非常直接： * **赋值**: 观察路径穿过每个菱形 $i$ 的方向。如果它是“从左到右”走的，我们就令 $x_i = $ 真。如果它是“从右到左”走的，我们就令 $x_i = $ 假。 * **验证满足性**: 因为路径是哈密顿路径，它必须访问了每一个子句节点 $C_j$。由于路径是“正常的”，对 $C_j$ 的访问必然是通过某个菱形 $i$ 中的岔路完成的。 * 如果这个岔路是“左进右出”型的，说明路径在菱形 $i$ 中是“从左到右”走的，我们已令 $x_i=$ 真。而这个岔路的存在本身就意味着子句 $c_j$ 包含正文字 $x_i$。因此，该赋值满足 $c_j$。 * 如果这个岔路是“右进左出”型的，说明路径在菱形 $i$ 中是“从右到左”走的，我们已令 $x_i=$ 假。而这个岔路的存在意味着子句 $c_j$ 包含负文字 $\overline{x_i}$。因此，该赋值也满足 $c_j$。 * 由于每个子句节点都被访问了，所以每个子句都被满足了。因此 $\phi$ 可满足。 3. **“剩下的就是证明哈密顿路径必须是正常的。”**: * 这是证明的 crux (关键点)。我们必须排除所有“非正常”走法的可能性。 * **什么是非正常路径？** 最主要的非正常情况是：路径从一个菱形（比如菱形 $i$）出发访问了子句节点 $C_j$，但没有返回菱形 $i$，而是“跳”到了另一个菱形（比如菱形 $k$）中。如图 7.54 所示。 4. **对图 7.54 的分析（排除非正常路径）**: * **场景**: 路径沿着 $... \to a_1 \to c$ 行进，其中 $a_1$ 在一个菱形里， $c$ 是子句节点。然后路径没有走 $c \to a_2$ 返回同一个菱形，而是走了 $c \to b_2$ 跳到了另一个菱形的 $b_2$ 节点。 * **问题**: 节点 $a_2$ 怎么办？由于这是一条哈密顿路径，它最终必须以某种方式访问 $a_2$。 * **分析 $a_2$ 的入度**: 有哪些边是指向 $a_2$ 的？ * 来自它在水平链上的邻居，即 $a_1$ 和 $a_3$ (这里的 $a_3$ 是 $a_2$ 在链上的另一个邻居)。 * 可能来自某个子句节点的返回边，例如 $c \to a_2$。 * **路径的约束**: * 路径已经从 $a_1$ 走到了 $c$，所以不可能再从 $a_1$ 走到 $a_2$ 了（一个节点只有一个后继）。 * 路径已经从 $c$ 走到了 $b_2$，所以不可能再从 $c$ 走到 $a_2$ 了。 * 所以，要访问 $a_2$，路径必须从它的另一个邻居 $a_3$ 进入，即 $... \to a_3 \to a_2$。 * **矛盾所在**: * 原文的论证有点绕，但核心思想是：**分隔节点 (separator node)** 的设计使得这种跳跃不可能。 * 让我们更清晰地阐述：在节点对 $(a_1, a_2)$ 和 $(b_1, b_2)$ 之间，必然存在至少一个分隔节点。分隔节点的特殊之处在于，它在水平链上的入度和出度都是1（只和左右两个邻居相连）。它没有任何连接到子句节点的“岔路”。 * 如果路径要从 $c$ 跳到 $b_2$，那么它之后必须继续走完 $b$ 菱形剩下的部分。然后它需要再跳回到 $a$ 菱形，去收拾剩下的节点（比如 $a_2$）。 * 但分隔节点的设计使得这种“菱形间”的跳跃只能通过子句节点进行。当你用完了所有子句节点的“桥梁”后，你可能会发现自己被困在一个菱形里，无法去访问另一个菱形里剩下的“孤岛”节点。 * 原文的论证“路径不能从 $a_3$ 进入 $a_2$，因为 $a_3$ 是 $a_2$ 指向的唯一可用节点，所以路径必须通过 $a_3$ 离开 $a_2$” 比较费解，但其本质是，一旦路径的选择使得 $a_2$ 这样的节点被“孤立”出来（它的所有入口都被之前的路径占用了），那么哈密顿路径就不可能存在。分隔节点的设计，就是为了确保任何试图“跳跃”的路径都会导致某些节点被如此“孤立”。 5. **“因此，哈密顿路径必须是正常的。”**: 基于上述（虽然原文描述得有些晦涩）的排除法，我们得出结论，任何存在于该图中的哈密顿路径都必须遵循我们定义的“正常”模式。 6. **“这个归约显然在多项式时间内完成，证明完毕。”**: * **多项式时间**: 构造图 $G$ 的时间复杂度是多少？ * 节点数: $2 + l \times (3k+1+2) + k \approx O(lk)$。 * 边数: 也大致是 $O(lk)$ 级别。 * 公式 $\phi$ 的大小 $n$ 大致是 $l+k$。因此图的大小是关于 $n$ 的二次多项式。构造过程是简单的节点和边添加，所以是多项式时间的。 * **证明完毕**: 两个方向的等价性都已证明，且归约是多项式时间的，因此 **3SAT** $\le_P$ **HAMPATH** 成立。结合 **HAMPATH** $\in$ **NP**，定理 7.46 得证。 [易错点与边界情况] * **对“正常路径”的理解**: 理解“正常路径”的定义，以及为什么它是我们能够从路径反推赋值的关键，是理解本部分证明的核心。 * **分隔节点的作用**: 本部分证明的难点在于理解分隔节点是如何防止“跳跃”的。虽然原文的解释不易懂，但其核心作用是**局部化**子句的绕行，确保“出差”访问子句节点后必须“返回原单位”。 * **归约的艺术性**: 这个归约非常精妙，它用图的拓扑结构（连接性、方向性）完美地模拟了抽象的逻辑约束。它的正确性高度依赖于每一个细节（节点数、边的方向、分隔节点）都恰到好处。 [总结] 本段证明了 **HAMPATH** 归约的第二个、也是更困难的方向：从一条已知的哈密顿路径反向构造出原 **3SAT** 公式的满足赋值。证明的关键在于，首先论证了任何存在于此图中的哈密顿路径都必须是“正常的”（即严格按顺序穿越菱形，且对子句的访问是“哪里去哪里回”的绕行）。基于此，我们可以根据路径穿越每个菱形的方向（左到右/右到左）来确定变量的真假赋值。因为路径访问了所有子句节点，这意味着每个子句都通过某个可用的绕行被“满足”了，从而证明了该赋值方案的有效性。最后，它确认了整个归约构造过程能在多项式时间内完成，从而完成了 **HAMPATH** 的 **NP-完全**性证明。 [存在目的] 本段的目的是为归约的正确性提供最后也是最关键的一块拼图。它确保了我们构造的图不会因为存在某些“取巧”的路径（非正常路径）而导致逻辑等价性被破坏。通过严格证明所有可能的路径都必须是我们期望的“正常”形式，它封堵了所有可能的漏洞，使得从路径到赋值的映射成为可能，从而完成了整个双向的逻辑链条。 [直觉心智模型] 回到特技飞行挑战： * **前提**: 你找到了一条能飞越所有峡谷、撞破所有气球的哈密顿飞行路径。 * **证明路径必须正常**: 你发现，因为峡谷之间的连接非常稀疏（只有主航道），而且每个峡谷内部的航线设计（特别是分隔区域）让你无法在一个峡谷的“侧飞点”出去后，飞到另一个峡谷的“侧飞点”去。任何这样尝试的后果，都会导致你漏掉出发峡谷里的某个区域无法返回。因此，你得出结论：任何成功的完整路径，都必须是“进入峡谷A-飞完峡谷A（中途可侧飞撞气球并返回）-离开峡谷A进入峡谷B...”。 * **构造赋值**: 1. 你记录下你的路径在每个峡谷里的飞行方式（“Z”形还是反“Z”形）。这就是你的变量赋值。 2. 因为你撞破了所有气球，你知道这个赋值方案是有效的，它为每个气球都提供了至少一条可用的侧飞航线。 3. 因此，你从一条成功的飞行路径，反向推导出了一个可行的航线选择方案（满足赋值）。 [直观想象] 你得到了一份完整的、通过了迷宫的路线图（哈密顿路径）。 * **路径的正常性**: 你研究地图后发现，迷宫的设计（特别是那些狭窄的“隔离走廊”，即分隔节点）使得你不可能从一个大厅（菱形）的某个房间（节点对）出去后，直接跑到另一个大厅的房间里。唯一的通道就是预设的主路。所以，路线图必然是完整地走完一个大厅，再走向下一个大厅。 * **推导谜题答案**: 1. 你根据路线图在每个“菱形大厅”里是“从左到右”还是“从右到左”走的，来确定逻辑谜题中每个变量的答案（真或假）。 2. 你看到路线图访问了所有的“关键房间”（子句节点）。你检查它是从哪个大厅的哪条路绕过去访问的，这正好告诉你，你推导出的这个答案，是如何满足谜题中对应的那个条件的。 3. 最终，你从一张行走路线图，成功地破解了整个逻辑谜题的答案。 # 4. 无向哈密顿路径问题 ## 4.1. UHAMPATH 的 NP-完全性 [原文] ## 定理 7.55 **UHAMPATH** 是 **NP**-完全的。 证明 归约接受一个带有节点 $s$ 和 $t$ 的有向图 $G$，并构造一个带有节点 $s^{\prime}$ 和 $t^{\prime}$ 的无向图 $G^{\prime}$。图 $G$ 具有从 $s$ 到 $t$ 的哈密顿路径当且仅当 $G^{\prime}$ 具有从 $s^{\prime}$ 到 $t^{\prime}$ 的哈密顿路径。我们描述 $G^{\prime}$ 如下。 $G$ 的每个节点 $u$，除了 $s$ 和 $t$，都被 $G^{\prime}$ 中的三元组节点 $u^{\text {in }}$、$u^{\text {mid }}$ 和 $u^{\text {out }}$ 替换。$G$ 中的节点 $s$ 和 $t$ 被 $G^{\prime}$ 中的节点 $s^{\text {out }}=s^{\prime}$ 和 $t^{\text {in }}=t^{\prime}$ 替换。$G^{\prime}$ 中出现两种类型的边。首先，边连接 $u^{\text {mid }}$ 与 $u^{\text {in }}$ 和 $u^{\text {out }}$。其次，如果 $G$ 中有从 $u$ 到 $v$ 的边，则边连接 $u^{\text {out }}$ 与 $v^{\text {in }}$。这样就完成了 $G^{\prime}$ 的构造。 [逐步解释] 这部分开始证明 **哈密顿路径问题** 的无向版本（**UHAMPATH**）也是 **NP-完全**的。其采用的策略是从已知的 **NP-完全**问题 **HAMPATH** (有向版) 进行归约。 1. **“定理 7.55 UHAMPATH 是 NP-完全的。”**: * **UHAMPATH**: 输入是一个**无向图** $G$ 和两个节点 $s, t$，问是否存在一条从 $s$ 到 $t$ 的、经过所有节点恰好一次的路径。 * 这个定理宣告了，即使把边的方向去掉，问题本质的难度并未降低。 2. **“证明 归约接受一个带有节点 $s$ 和 $t$ 的有向图 $G$，并构造一个...无向图 $G^{\prime}$...”**: * **归约方向**: **HAMPATH** $\le_P$ **UHAMPATH**。 * **输入**: 一个 **HAMPATH** 问题的实例，即一个有向图 $G$ 和起终点 $s, t$。 * **输出**: 一个 **UHAMPATH** 问题的实例，即一个无向图 $G'$ 和起终点 $s', t'$。 * **目标**: 证明 $G$ 有哈密顿路径 $\iff G'$ 有哈密顿路径。 3. **$G'$ 的构造——节点替换**: * 这是一个典型的“节点小工具”构造。我们用一个更复杂的结构来替换原来图中的每个简单节点，以在无向图中模拟有向图的行为。 * **对于中间节点**: $G$ 中的每个普通节点 $u$ (既不是 $s$ 也不是 $t$)，在 $G'$ 中都被替换成一个由三个节点组成的“三元组”：$u^{in}, u^{mid}, u^{out}$。 * **对于起点 $s$**: $G$ 中的起点 $s$ 在 $G'$ 中被替换成一个单节点 $s^{out}$，这个节点同时也是 $G'$ 的新起点 $s'$。 * **对于终点 $t$**: $G$ 中的终点 $t$ 在 $G'$ 中被替换成一个单节点 $t^{in}$，这个节点同时也是 $G'$ 的新终点 $t'$。 4. **$G'$ 的构造——边的添加**: * **第一类边 (内部连接)**: 在每个三元组内部，我们将中间节点 $u^{mid}$ 与它的两个“邻居” $u^{in}$ 和 $u^{out}$ 连接。由于 $G'$ 是无向图，这两条边是 $(u^{mid}, u^{in})$ 和 $(u^{mid}, u^{out})$。这形成了一个形如 $u^{in} - u^{mid} - u^{out}$ 的短路径。 * **第二类边 (外部连接)**: 这类边模拟了原图 $G$ 的有向边。如果 $G$ 中有一条有向边 $u \to v$，我们就在 $G'$ 中添加一条无向边，连接 $u$ 的“出口”和 $v$ 的“入口”，即边 $(u^{out}, v^{in})$。 5. **构造完成**: * 将 $G$ 的所有节点按规则替换，并根据 $G$ 的所有有向边添加对应的无向边后，$G'$ 的构造就完成了。这个过程显然是多项式时间的。 [具体数值示例] * **输入有向图 $G$**: 节点 $\{s, u, v, t\}$，有向边 $s \to u, u \to v, v \to t$。这是一个简单的有向路径。 * **输出无向图 $G'$**: * **节点 (8个)**: * $s$ 替换为 $s^{out}$ (即 $s'$) * $u$ 替换为 $u^{in}, u^{mid}, u^{out}$ * $v$ 替换为 $v^{in}, v^{mid}, v^{out}$ * $t$ 替换为 $t^{in}$ (即 $t'$) * **边**: * **内部边**: $(u^{in}, u^{mid}), (u^{mid}, u^{out}), (v^{in}, v^{mid}), (v^{mid}, v^{out})$。 * **外部边**: * 因为 $s \to u$，添加边 $(s^{out}, u^{in})$。 * 因为 $u \to v$，添加边 $(u^{out}, v^{in})$。 * 因为 $v \to t$，添加边 $(v^{out}, t^{in})$。 * **$G'$ 的样子**: 整个图 $G'$ 看起来像一条链: $s^{out} - u^{in} - u^{mid} - u^{out} - v^{in} - v^{mid} - v^{out} - t^{in}$。 这显然是一条哈密顿路径。 [易错点与边界情况] * **小工具的目的**: 这个 $u^{in} - u^{mid} - u^{out}$ 结构的核心作用是在无向图中强加一个“方向”。任何想要访问 $u^{mid}$ 的哈密顿路径，都必须从 $u^{in}$ 和 $u^{out}$ 中的一个进入，并从另一个离开。它不能从别的地方跳到 $u^{mid}$。这模拟了路径必须“流经”节点 $u$ 的行为。 * **起点和终点的特殊处理**: 起点 $s$ 只有“出口” $s^{out}$，终点 $t$ 只有“入口” $t^{in}$。这确保了路径在 $G'$ 中也必须从 $s$ 的对应部分开始，在 $t$ 的对应部分结束。 [总结] 本段提出了 **UHAMPATH** 的 **NP-完全**性证明，其策略是构造一个从 **HAMPATH** 到 **UHAMPATH** 的多项式时间归约。该归约的核心是设计了一个“三元组”节点小工具 $(u^{in}, u^{mid}, u^{out})$ 来替换原图中的每个节点 $u$。这个小工具通过内部连接 $(u^{in} - u^{mid} - u^{out})$ 强制路径必须“流经”它，而外部连接则通过连接前后节点的“出口”和“入口” $(u^{out}, v^{in})$ 来模拟原图中的有向边。这样，一个有向图就被转换成了一个行为上等价的无向图。 [存在目的] 本段的目的是展示 **NP-完全**性的“传染”过程。一旦我们有了一个已知的 **NP-完全**问题（**HAMPATH**），我们就可以利用它作为“跳板”，去证明其他相关问题的 **NP-完全**性。这个证明比从 **3SAT** 直接归约到 **UHAMPATH** 要简单得多，因为它处理的是两个结构相似的图论问题。它也再次展示了“小工具”思想的强大威力，即通过设计局部结构来模拟和强制特定的行为。 [直觉心智模型] 想象你要把一个“单行道”网络（有向图）改造成一个“双行道”网络（无向图），但又要保留原来的单向交通流规则。 * **节点改造（三元组小工具）**: 你把原来的每个十字路口 $u$，都改造成一个微型环岛，有三个出入口：一个“入口匝道”($u^{in}$)，一个“环岛主体”($u^{mid}$)，一个“出口匝道”($u^{out}$)。车流必须从入口匝道进，经过环岛主体，再从出口匝道出。 * **道路改造（外部连接）**: 原来从路口 $u$ 到路口 $v$ 的一条单行道，现在你把它改建成一条连接 $u$ 的“出口匝道”和 $v$ 的“入口匝道”的双行道。 * **效果**: 虽然所有道路都是双行的，但由于每个路口都被改造成了“必须按顺序通过”的微型环岛，任何想要走遍所有路口的司机，实际上还是被迫遵循了原来单行道网络的流向。 [直观想象] 你有一串磁珠，磁珠有 N 极和 S 极（有向）。你想用一串不分极性的普通铁珠（无向）来模拟它。 * **磁珠 $u$ 的替换**: 你用三颗铁珠来代替一颗磁珠 $u$：一颗叫 $u_{in}$，一颗叫 $u_{mid}$，一颗叫 $u_{out}$。你用短线把它们串成 $u_{in}-u_{mid}-u_{out}$。 * **连接**: 原来磁珠 $u$ 的 S 极连接到磁珠 $v$ 的 N 极，现在你用一根长线把铁珠串 $u$ 的尾巴（$u_{out}$）和铁珠串 $v$ 的头（$v_{in}$）连起来。 * **效果**: 虽然所有铁珠和线都是无方向的，但任何一条想要走遍所有铁珠的路径，都必须沿着 $u_{in} \to u_{mid} \to u_{out}$ 的顺序穿过每一个三珠串。这就在无方向的系统中，重现了有方向的流动。 ## 4.2. UHAMPATH 归约的正确性证明 [原文] 我们可以通过证明 $G$ 具有从 $s$ 到 $t$ 的哈密顿路径当且仅当 $G^{\prime}$ 具有从 $s^{\text {out }}$ 到 $t^{\text {in }}$ 的哈密顿路径来证明这个构造是有效的。为了证明一个方向，我们观察到 $G$ 中的哈密顿路径 $P$， $$

$$ 在 $G^{\prime}$ 中有相应的哈密顿路径 $P^{\prime}$， $$

$$ 为了证明另一个方向，我们声称 $G^{\prime}$ 中从 $s^{\text{out}}$ 到 $t^{\text{in}}$ 的任何哈密顿路径必须从一个三元组节点到另一个三元组节点，除了起点和终点，就像我们刚刚描述的路径 $P^{\prime}$ 一样。这将完成证明，因为任何这样的路径在 $G$ 中都有相应的哈密顿路径。我们通过从节点 $s^{\text{out}}$ 开始跟踪路径来证明这个论断。观察到路径中的下一个节点必须是某个 $i$ 的 $u_{i}^{\text{in}}$，因为只有这些节点与 $s^{\text{out}}$ 连接。下一个节点必须是 $u_{i}^{\text{mid}}$，因为没有其他方式可以将 $u_{i}^{\text{mid}}$ 包含在哈密顿路径中。在 $u_{i}^{\text{mid}}$ 之后是 $u_{i}^{\text{out}}$，因为这是 $u_{i}^{\text{mid}}$ 连接的唯一其他节点。下一个节点必须是某个 $j$ 的 $u_{j}^{\text{in}}$，因为没有其他可用节点连接到 $u_{i}^{\text{out}}$。论证然后重复直到到达 $t^{\text{in}}$。 [逐步解释] 这部分对 **HAMPATH 到 UHAMPATH** 的归约进行了双向的正确性证明。 **第一部分：证明 $G$ 有哈密顿路径 $\Rightarrow G'$ 有哈密顿路径** 1. **“我们观察到 $G$ 中的哈密顿路径 $P$...在 $G'$ 中有相应的哈密顿路径 $P'$”**: 这是一个构造性的证明。 2. **给定的 $G$ 中的路径 $P$**: $s, u_1, u_2, \ldots, u_k, t$。这表示 $G$ 中存在有向边 $s \to u_1$, $u_1 \to u_2$, ..., $u_k \to t$。 3. **构造 $G'$ 中的路径 $P'$**: 我们将 $P$ 中的每个节点“展开”。 * $s$ 变成 $s^{out}$。 * 每个 $u_i$ 变成路径片段 $u_i^{in} - u_i^{mid} - u_i^{out}$。 * $t$ 变成 $t^{in}$。 4. **拼接路径 $P'$**: * 路径从 $s^{out}$ 开始。 * 由于 $G$ 中有边 $s \to u_1$，根据构造，$G'$ 中有边 $(s^{out}, u_1^{in})$。所以路径可以走到 $u_1^{in}$。 * 然后路径必须走完 $u_1$ 的三元组：$u_1^{in} - u_1^{mid} - u_1^{out}$。 * 由于 $G$ 中有边 $u_1 \to u_2$，根据构造，$G'$ 中有边 $(u_1^{out}, u_2^{in})$。所以路径可以从 $u_1$ 的出口走到 $u_2$ 的入口。 * 这个过程不断重复，直到路径走到 $u_k^{out}$。 * 由于 $G$ 中有边 $u_k \to t$，根据构造，$G'$ 中有边 $(u_k^{out}, t^{in})$。路径最终到达 $t^{in}$。 5. **验证 $P'$ 是哈密顿路径**: * **覆盖所有节点**: 原始路径 $P$ 覆盖了 $G$ 的所有节点。我们构造的 $P'$ 相应地访问了 $s^{out}, t^{in}$ 以及每一个三元组 $u_i^{in}, u_i^{mid}, u_i^{out}$。由于 $G'$ 的节点就是由这些部分组成的，所以 $P'$ 覆盖了 $G'$ 的所有节点。 * **每个节点一次**: 构造过程是线性的，没有回头路，所以每个节点只访问一次。 * 因此，$P'$ 是一条 $G'$ 中的哈密顿路径。 **第二部分：证明 $G'$ 有哈密顿路径 $\Rightarrow G$ 有哈密顿路径** 1. **“我们声称 $G'$ 中从 $s^{\text{out}}$ 到 $t^{\text{in}}$ 的任何哈密顿路径必须...就像我们刚刚描述的路径 $P'$ 一样。”**: 这是关键断言。它说明 $G'$ 的结构非常严格，只允许一种“标准形式”的哈密顿路径。 2. **证明这个断言 (通过追踪路径)**: * **起点**: 路径从 $s^{out}$ 开始。 * **第1步**: $s^{out}$ 的邻居有哪些？根据构造，它只与那些满足“$G$ 中有边 $s \to u_i$”的节点的入口 $u_i^{in}$ 相连。所以路径的下一个节点**必须**是某个 $u_i^{in}$。 * **第2步**: 现在路径在 $u_i^{in}$。它的邻居是 $s^{out}$ (已访问) 和 $u_i^{mid}$。为了能继续前进并最终访问所有节点，它必须走向 $u_i^{mid}$。更重要的是，节点 $u_i^{mid}$ 的度为2，它的邻居只有 $u_i^{in}$ 和 $u_i^{out}$。任何哈密顿路径要访问 $u_i^{mid}$，都必须从一端进，另一端出，形成 $...-u_i^{in}-u_i^{mid}-u_i^{out}-...$ 或 $...-u_i^{out}-u_i^{mid}-u_i^{in}-...$ 的子路径。由于路径刚从 $s^{out}$ 到达 $u_i^{in}$，所以它别无选择，只能走向 $u_i^{mid}$。 * **第3步**: 路径在 $u_i^{mid}$。它的另一个邻居是 $u_i^{out}$。路径必须走向 $u_i^{out}$。 * **第4步**: 路径在 $u_i^{out}$。它的邻居有哪些？有 $u_i^{mid}$ (已访问)，以及所有满足“$G$ 中有边 $u_i \to u_j$”的节点的入口 $u_j^{in}$。为了继续哈密顿路径，它必须走向某个新的、未访问的 $u_j^{in}$。 * **重复**: 这个 $u_j^{in} \to u_j^{mid} \to u_j^{out}$ 的过程会一直重复。 * **结论**: 这证明了 $G'$ 中的任何哈密顿路径都必须遵循“从一个三元组的出口，跳到下一个三元组的入口”的模式。 3. **从 $G'$ 的路径构造 $G$ 的路径**: * 既然 $G'$ 的哈密顿路径形如 $s^{out} - (u_1 \text{三元组}) - (u_2 \text{三元组}) - \dots - t^{in}$，我们可以直接从中读取出 $G$ 中的路径。 * $s^{out}$ 对应 $s$。 * $(u_1 \text{三元组})$ 对应 $u_1$。 * ... * $t^{in}$ 对应 $t$。 * $G'$ 中存在边 $(u_i^{out}, u_{i+1}^{in})$，这根据构造规则，意味着 $G$ 中存在有向边 $u_i \to u_{i+1}$。 * 因此，我们从 $G'$ 的路径 $P'$ 中提取出的节点序列 $s, u_1, u_2, \ldots, t$ 在 $G$ 中是一条合法的路径。 * 由于 $P'$ 访问了所有三元组，所以提取出的路径也访问了 $G$ 的所有节点。因此，它是 $G$ 中的一条哈密顿路径。 [总结] 本段严谨地证明了 **HAMPATH 到 UHAMPATH** 归约的正确性。 * **正向证明**通过一个直接的构造，展示了如何将有向图中的一条哈密顿路径“翻译”成无向图中一条等价的哈密顿路径，方法是简单地展开每个节点为三元组。 * **反向证明**则通过分析无向图 $G'$ 的结构约束，论证了任何存在于 $G'$ 中的哈密顿路径都必须遵循一种固定的“流式”模式。这种模式使得我们可以从中唯一地反向“读取”出一条在原有向图 $G$ 中合法的哈密顿路径。两个方向的证明共同确立了两个问题实例之间的等价性。 [存在目的] 本段的目的是完成 **UHAMPATH** 的 **NP-完全**性证明。在上一段描述了归约的“如何做”（构造方法）之后，这一段回答了“为什么行”（正确性证明）。这是任何归约证明中必不可少的核心部分，它确保了我们建立的“问题转换机”是可靠的，没有逻辑漏洞。 [直觉心智模型] 回到改造单行道网络的比喻： * **正向证明**: 如果你有一张地图，标明了如何在单行道网络里走遍所有路口。你只要按照这个顺序，依次穿过每个路口改造后的“微型环岛”（入口匝道-环岛主体-出口匝道），就能在新的双行道网络里，同样走遍所有地方。 * **反向证明**: 如果你在新的双行道网络里找到了一条走遍所有地方的路线。你观察这条路线，发现它在每个“微型环岛”处，都只能是“从入口匝道进，从出口匝道出”。你把这些“环岛”的名字按顺序记下来，就得到了一条在原始单行道网络里完全合法的路线。因为你在新网络里走了所有地方，所以这条原始路线也一定经过了所有路口。 [直观想象] 回到用铁珠模拟磁珠的比喻： * **正向证明**: 如果你有一串按特定顺序排列的磁珠链。你只要把每个磁珠都换成对应的“三珠串”，再把这些三珠串按原来的顺序连起来，你就得到了一条包含所有铁珠的、完整的铁珠链。 * **反向证明**: 现在你手里有一条由许多“三珠串”和连接线组成的、完整的铁珠长链。你观察发现，这条长链的路径在每个“三珠串”内部，都必须是 $in \to mid \to out$。于是你把每个“三珠串”都看作一个整体，你得到的序列就对应一条原始的磁珠链。因为铁珠链是完整的，所以磁珠链也一定是完整的。 # 5. 子集和问题 ## 5.1. 问题定义回顾 [原文] ## **子集和问题** 回想一下第 297 页定义的 **子集和问题**。在该问题中，我们给定一组数字 $x_{1}, \ldots, x_{k}$ 以及一个目标数字 $t$，并要求确定该集合是否包含一个子集合，其元素之和为 $t$。现在我们证明这个问题是 **NP**-完全的。 [逐步解释] 这部分再次引入了一个新的问题——**子集和问题 (SUBSET-SUM)**，并预告了将要证明其 **NP-完全**性。 1. **“子集和问题 (SUBSET-SUM)”**: 问题的名称。这是一个经典的组合优化和计算复杂性问题。 2. **“回想一下第 297 页定义的...”**: 表明这个问题在本书前面已经介绍过。 3. **问题定义**: * **输入**: 1. 一个集合（或多重集）$S = \{x_1, x_2, \ldots, x_k\}$，由 $k$ 个数字组成。这些数字可以是整数，通常是非负整数。 2. 一个目标值 $t$。 * **问题**: 判断是否存在 $S$ 的一个子集 $S' \subseteq S$，使得 $S'$ 中所有元素的和恰好等于 $t$。 * 这是一个**判定问题**，答案是“是”或“否”。 4. **“现在我们证明这个问题是 NP-完全的。”**: 明确了本节的目标。 [具体数值示例] * **示例1：存在解** * **输入**: 集合 $S = \{3, 8, 4, 5, 2\}$，目标值 $t=10$。 * **问题**: 是否存在和为 10 的子集？ * **解**: 是。子集 $\{8, 2\}$ 的和是 $8+2=10$。另一个解是 $\{3, 5, 2\}$，其和也是 $3+5+2=10$。 * **示例2：不存在解** * **输入**: 集合 $S = \{3, 8, 4, 5, 2\}$，目标值 $t=11$。 * **问题**: 是否存在和为 11 的子集？ * **解**: 否。你可以尝试所有组合，都无法得到和为 11。例如，$\{8, 3\}$ 的和是 11，但 3 不在集合 S 中。哦，3 在集合 S 中，所以 $\{8,3\}$ 是一个解，和为 11。让我们换个目标值。 * **修正后的示例2**: * **输入**: 集合 $S = \{3, 8, 4, 5, 2\}$，目标值 $t=18$。 * **解**: 否。集合中所有数字的和是 $3+8+4+5+2=22$。最大的几个数 $\{8,5,4\}$ 和为 17，加上 3 就超过 18了。无法凑出 18。 [易错点与边界情况] * **判定问题 vs 优化问题**: **SUBSET-SUM** 是判定问题。它的优化版本是“背包问题 (Knapsack Problem)”，即在不超过某个容量 $t$ 的前提下，让子集的和最大。这两个问题密切相关。 * **数字的大小**: 这个问题的难度与输入数字的大小密切相关。如果数字都非常大（例如，用很多位来表示），问题会变得很困难。后面会看到，我们构造的归约正是利用了非常大的数字。存在一个伪多项式时间算法（使用动态规划）可以解决子集和问题，其时间复杂度与目标值 $t$ 和元素数量 $k$ 相关。如果 $t$ 的值相对于输入规模（数字的位数）是指数级的，那么这个算法就是指数时间的。**NP-完全**性证明说明了不存在一个时间复杂度只与 $k$ 和数字的**位数**呈多项式关系的算法。 [总结] 本段重新引入了**子集和问题 (SUBSET-SUM)** 的定义，并宣告了本节的证明目标：证明 **SUBSET-SUM** 是 **NP-完全**的。该问题询问一个给定的数字集合中，是否存在一个子集，其元素之和恰好等于一个给定的目标值。 [存在目的] 本段的作用是为后续的归约证明设定目标问题。在完成了两个图论问题的证明后，现在转向一个算术和数论风格的问题。这展示了 **NP-完全**现象的广泛性，它不仅仅局限于图论。清晰地重申问题定义，是开始一个全新风格归约证明的必要步骤。 [直觉心智模型] 想象你在超市购物，有一张面额为 $t$ 的代金券，必须正好用完，不能找零。 * **集合 S**: 超市货架上所有商品的价格标签。 * **子集和问题**: 你能否挑选一篮子商品，使得它们的价格总和正好等于你的代金券面额 $t$？ * **NP-完全的含义**: 当商品种类繁多，价格各异，代金券面额也很大时，快速找到一个完美的凑单方案是非常困难的。不存在一个通用的、在所有情况下都很快的“凑单计算器”。 [直观想象] 你是一名药剂师，需要精确地配制一份重量为 $t$ 的药剂。 * **集合 S**: 你手头有各种不同重量的砝码。 * **子集和问题**: 你能否选出一些砝码，放在天平的一端，使得它们的总重量正好是 $t$？ * 这个看似简单的配重问题，其内在的计算复杂性，将被证明和解决 **3SAT** 问题一样困难。 ## 5.2. 定理与证明思路 [原文] ## 定理 7.56 **SUBSET-SUM** 是 **NP**-完全的。 证明思路 我们已在定理 7.25 中证明了 **SUBSET-SUM** 属于 **NP**。我们通过将 **NP**-完全语言 3**SAT** 归约到 **SUBSET-SUM** 来证明 **NP** 中的所有语言都可以多项式时间归约到 **SUBSET-SUM**。给定一个 3 **cnf**-公式 $\phi$，我们构造一个 **SUBSET-SUM** 问题的实例，该实例包含一个子集合，其元素之和为 $t$，当且仅当 $\phi$ 是可满足的。称此子集合为 $T$。 为了实现这个归约，我们寻找 **SUBSET-SUM** 问题的结构来表示变量和子句。我们构造的 **SUBSET-SUM** 问题实例包含以十进制表示的大数字。我们用成对的数字表示变量，用十进制表示中的某些位置表示子句。 我们用两个数字 $y_{i}$ 和 $z_{i}$ 来表示变量 $x_{i}$。我们证明对于每个 $i$，要么 $y_{i}$ 要么 $z_{i}$ 必须在 $T$ 中，这建立了满足赋值中 $x_{i}$ 真值的编码。 每个子句位置在目标 $t$ 中包含一个特定值，这给子集 $T$ 施加了一个要求。我们证明这个要求与相应子句中的要求相同——即该子句中的一个文字被赋值为真。 [逐步解释] 这部分首先陈述定理，然后概述了证明 **SUBSET-SUM** 是 **NP-完全**的思路，这是一个非常巧妙的、基于数字构造的归约。 1. **“定理 7.56 SUBSET-SUM 是 NP-完全的。”**: 明确陈述最终结论。 2. **“我们已在定理 7.25 中证明了 SUBSET-SUM 属于 NP。”**: 确认了 **NP-完全**性证明的第一步已完成。验证一个子集的和是否等于 $t$ 是容易的，只需把子集中的数加起来再比较即可。 3. **“我们通过将...3SAT 归约到 SUBSET-SUM...”**: 明确了证明 **NP-难**的策略，即构造 **3SAT** $\le_P$ **SUBSET-SUM**。 4. **“...我们构造一个 SUBSET-SUM 问题的实例...当且仅当 $\phi$ 是可满足的。”**: 重申了归约的输入、输出和正确性要求。 5. **“...我们构造的 SUBSET-SUM 问题实例包含以十进制表示的大数字。”**: 揭示了**小工具**的载体。这次我们不用图的节点和边，而是用**大数字的位值**来模拟逻辑。 6. **“我们用成对的数字表示变量，用十进制表示中的某些位置表示子句。”**: 这是对**小工具**设计的核心概括。 * **变量小工具**: 一对数字 $(y_i, z_i)$。 * **子句小工具**: 数字的特定“列”或“位”。 7. **“我们用两个数字 $y_{i}$ 和 $z_{i}$ 来表示变量 $x_{i}$...”**: * 这一对数字的设计，将用来模拟变量 $x_i$ 的二元选择。 * **“要么 $y_{i}$ 要么 $z_{i}$ 必须在 $T$ 中”**: 证明的关键一步，将论证为了凑出目标和 $t$，对于每一对 $(y_i, z_i)$，我们必须且只能选择其中一个放入子集 $T$。 * 这个“二选一”的行为就完美地对应了变量 $x_i$ 必须赋值为“真”或“假”。例如，选 $y_i$ 代表 $x_i=$ 真，选 $z_i$ 代表 $x_i=$ 假。 8. **“每个子句位置在目标 $t$ 中包含一个特定值...”**: * 在大数字的表示中，我们会为每个子句 $c_j$ 分配一个专属的“数位”或“列”。 * 目标和 $t$ 在这一列上的数字是精心设置的。 * **“...这给子集 $T$ 施加了一个要求。”**: 子集 $T$ 中所有数字在这一列上的数字加起来，必须等于 $t$ 在这一列的数字。 9. **“我们证明这个要求与相应子句中的要求相同——即该子句中的一个文字被赋值为真。”**: * 这是归约的“画龙点睛”之笔。数字的设计将保证： * 只有当子句 $c_j$ 被满足时（即至少有一个对应的真文字被选中），$T$ 中数字在 $c_j$ 列上的和才能凑出 $t$ 在该列的数字。 * 这通常通过一种“无进位加法”来实现，即保证每一列的数字和不会超过9，从而不会影响到其他列，使得每一列的逻辑约束都是独立的。 [具体数值示例] * **一个极简的模拟**: * **公式**: $(x_1)$。变量 $x_1$，子句 $c_1=(x_1)$。 * **构造**: * **变量 $x_1$**: 对应两个数字 $y_1, z_1$。 * **子句 $c_1$**: 对应个位。 * **变量列**: 对应十位。 * **数字设计**: * $y_1 = 11$ (十位是1代表变量，个位是1代表它出现在$c_1$中作为$x_1$) * $z_1 = 10$ (十位是1代表变量，个位是0代表它没出现在$c_1$中作为$\overline{x_1}$) * **目标和 $t$**: $t=11$ (十位是1要求选一个变量，个位是1要求$c_1$被满足) * **求解**: * 集合 $S = \{11, 10\}$，目标 $t=11$。 * 唯一的解是子集 $\{11\}$。 * **反向推导**: * 我们选了 $y_1=11$。因为我们把“选$y_i$”对应为“$x_i$=真”。 * 所以我们得到赋值 $x_1$=真。 * 这个赋值确实满足了原公式 $(x_1)$。 * 这个例子非常简化，但展示了用不同数位来编码不同约束的基本思想。 [易错点与边界情况] * **数字的基数**: 虽然原文说“十进制”，但任何足够大的基数都可以。关键是保证在相加时，任何一列的和都不会超过基数，以避免产生进位，破坏列之间的独立性。 * **“垃圾”数字**: 后面会看到，为了让每列的和精确地达到目标值，我们还需要引入一些“填充”或“松弛”数字（slack variables），它们的作用就像是找零钱，用来补足差额。 [总结] 本段概述了将 **3SAT** 归约到 **SUBSET-SUM** 的证明思路。其核心思想是利用大数的位值来模拟逻辑：用一对数字 $(y_i, z_i)$ 的“二选一”来编码变量 $x_i$ 的赋值；用数字的特定列来代表每个子句，并通过设置目标和 $t$ 在该列的数值，来施加该子句必须被满足的约束。整个设计的精髓在于通过精巧的数字构造，使得子集的数字求和运算能够等价于布尔公式的逻辑求值，特别是通过防止进位来确保每个逻辑约束（每列）的独立性。 [存在目的] 本段的目的是在展示具体的、令人望而生畏的大数字表格之前，提供一个高层次的、概念性的解释。它告诉读者这些数字不是随机的，而是被赋予了深刻的逻辑含义。每一对数字都是一个“变量开关”，每一列都是一个“子句检查器”。这个思路解释为读者理解后续复杂的数字表格提供了“解码密钥”。 [直觉心-模型] 想象一个“配料”问题。 * **目标 $t$**: 一份最终的“魔法药水”，它要求包含：1份龙鳞，1份凤羽，...（对应变量列），以及3份A成分，3份B成分，...（对应子句列）。 * **变量 $x_i$**: 你有两瓶原料，$y_i$ 和 $z_i$。 * $y_i$ 瓶里有：1份龙鳞，以及若干其他成分（如果$x_i$出现在某个子句里）。 * $z_i$ 瓶里有：1份龙鳞，以及若干其他成分（如果$\overline{x_i}$出现在某个子句里）。 * **逻辑**: 为了凑够每种“鳞/羽”各1份，你必须从每对 $(y_i, z_i)$ 中二选一。这个选择就对应了变量赋值。 * **子句约束**: 目标药水要求A成分有3份。你通过选择 $(y,z)$ 对，可能凑了1份或2份A成分。这还不够。 * **填充数字**: 你还有一些“纯净”的A成分原料（$g_j, h_j$），每份只含1份A成分。你可以用它们来补足差额，凑够3份。 * **等价性**: 你能成功配出魔法药水 $\iff$ 你对 $(y,z)$ 对的选择（变量赋值），使得每个子句列的成分初始就有至少1份，这样你才能用填充数字补到3。如果初始是0份，你最多只能补到2，任务失败。 [直观想象] 你正在填写一张特殊的调查问卷，问卷的答案需要以数字形式提交。 * **变量 $x_i$**: 对应问题“你是否同意观点 $i$？”。你有两个预设的答案数字可以选：$y_i$（代表同意）和 $z_i$（代表不同意）。 * **问卷结构**: 答案数字非常长。 * 左边的列，是“身份校验区”。 * 右边的列，是“逻辑自洽检查区”，每一列对应一个逻辑约束（子句）。 * **目标和 $t$**: 一个标准的、正确的答案总和。 * **填写规则**: * 为了通过“身份校验”（左边列的和为 $11...1$），你必须对每个问题都二选一作答。 * 为了通过“逻辑自洽检查”（右边每列的和都为3），你的选择组合必须满足所有内在的逻辑约束。例如，如果你选了代表“同意A”的数字，它会在某个检查列上加1。你必须保证每个检查列的初始和都至少是1，因为你最多只能再额外“手动”加2（通过填充数字）。 * 你能提交一份总和正确的问卷（找到子集和），当且仅当你的选择（赋值）满足了所有逻辑约束（公式可满足）。 ## 5.3. 详细证明 [原文] 证明 我们已经知道 **SUBSET-SUM** $\in \mathrm{NP}$，所以我们现在证明 3**SAT** $\leq_{\mathrm{P}}$ **SUBSET-SUM**。 令 $\phi$ 为一个布尔公式，变量为 $x_{1}, \ldots, x_{l}$，子句为 $c_{1}, \ldots, c_{k}$。归约将 $\phi$ 转换为 **SUBSET-SUM** 问题的实例 $\langle S, t\rangle$，其中 $S$ 的元素和数字 $t$ 是图 7.57 中表格的行，以普通十进制表示。双线以上的行被标记为 $$

$$ 并构成 $S$ 的元素。双线以下的行是 $t$。 因此，$S$ 为 $\phi$ 中的每个变量 $x_{i}$ 包含一对数字 $y_{i}, z_{i}$。这些数字的十进制表示分为两部分，如表中所示。左侧部分由一个 1 后面跟着 $l-i$ 个 0 组成。右侧部分为每个子句包含一位数字，其中 $y_{i}$ 在 $c_{j}$ 列中的数字为 1，如果子句 $c_{j}$ 包含文字 $x_{i}$；$z_{i}$ 在 $c_{j}$ 列中的数字为 1，如果子句 $c_{j}$ 包含文字 $\overline{x_{i}}$。未指定为 1 的数字为 0。 该表已部分填充，以说明示例子句 $c_{1}$、$c_{2}$ 和 $c_{k}$： $$

$$ 此外，$S$ 为每个子句 $c_{j}$ 包含一对数字 $g_{j}, h_{j}$。这两个数字相等，由一个 1 后面跟着 $k-j$ 个 0 组成。 最后，目标数字 $t$，即表格的最后一行，由 $l$ 个 1 后面跟着 $k$ 个 3 组成。 | | 12 | … | $c_{1}$ | $c_{2}$ | ⋯ | $c_{k}$ | | :--- | :--- | :--- | :--- | :--- | :--- | :--- | | $y_{1}$ | 1 | ⋯ | 1 | 0 | ⋯ | 0 | | $z_{1}$ | 1 | ... | 0 | 0 | … | 0 | | $y_{2}$ | 1 | ⋯ | 0 | 1 | … | 0 | | $z_{2}$ | 1 | ... | 1 | 0 | … | 0 | | $y_{3}$ | 1 | ⋯ | 1 | 1 | ⋯ | 0 | | $z_{3}$ | 1 | ⋯ | 0 | 0 | ⋯ | 1 | | ⋮ | | ⋱ | ⋮ | | ⋮ | ⋮ | | $y_{l}$ | | 1 | 0 | 0 | ⋯ | 0 | | $z_{l}$ | | 1 | 0 | 0 | … | 0 | | $g_{1}$ | | | 1 | 0 | ⋯ | 0 | | $h_{1}$ | | | 1 | 0 | ⋯ | 0 | | $g_{2}$ | | | | 1 | ⋯ | 0 | | $h_{2}$ | | | | 1 | ⋯ | 0 | | ⋮ | | | | | ⋱ | ⋮ | | $g_{k}$ | | | | | | 1 | | $h_{k}$ | | | | | | 1 | | $t$ | 1 | ⋯ | 3 | 3 | ⋯ | 3 | 图 7.57 将 3**SAT** 归约到 **SUBSET-SUM** [逐步解释] 这部分详细描述了用于归约的数字表格的构造方法。 1. **输入和输出**: * 输入: 布尔公式 $\phi$ (有 $l$ 个变量, $k$ 个子句)。 * 输出: 一个 SUBSET-SUM 实例 $\langle S, t \rangle$。 * $S$ 和 $t$ 都是由下面表格的行定义的大数。 2. **表格结构**: * 这是一个大表格，每一行代表一个数字，每一列代表一个十进制位。 * **列的划分**: * 左边有 $l$ 列，标记为 $1, 2, \ldots, l$。这些是“**变量列**”。 * 右边有 $k$ 列，标记为 $c_1, c_2, \ldots, c_k$。这些是“**子句列**”。 * **行的划分**: * $2l$ 行，代表 $y_1, z_1, y_2, z_2, \ldots, y_l, z_l$。这些是“**变量数字**”。 * $2k$ 行，代表 $g_1, h_1, g_2, h_2, \ldots, g_k, h_k$。这些是“**填充数字**”或“**松弛数字**”。 * 最后一行是目标和 $t$。 3. **数字的构造规则**: * **变量数字 ($y_i, z_i$)**: * **变量列部分 (左侧)**: 对于数字 $y_i$ 和 $z_i$，它们在第 $i$ 列的值都是 1，在其他变量列的值都是 0。这确保了为了在第 $i$ 列凑出和为 1，必须从 $(y_i, z_i)$ 中二选一。 * **子句列部分 (右侧)**: * 对于数字 $y_i$，如果变量 $x_i$ 出现在子句 $c_j$ 中，那么 $y_i$ 在 $c_j$ 列的值为 1，否则为 0。 * 对于数字 $z_i$，如果文字 $\overline{x_i}$ 出现在子句 $c_j$ 中，那么 $z_i$ 在 $c_j$ 列的值为 1，否则为 0。 * **填充数字 ($g_j, h_j$)**: * 这些数字在所有的变量列（左侧）都为 0。 * 对于数字 $g_j$ 和 $h_j$，它们在子句列 $c_j$ 的值为 1，在其他所有子句列的值都为 0。它们是“纯净”的，只对一列有贡献。 * **目标和 ($t$)**: * **变量列部分 (左侧)**: 所有 $l$ 列的值都是 1。 * **子句列部分 (右侧)**: 所有 $k$ 列的值都是 3。 4. **表格示例的解读**: * 该表是根据示例子句 $c_1=(x_1 \vee \overline{x_2} \vee x_3), c_2=(x_2 \vee x_3 \vee \dots), c_k=(\overline{x_3} \vee \dots)$ 填充的。 * **$y_1$ 行**: 在变量列 '1' 处为 1。因为它代表 $x_1$，且 $x_1$ 出现在 $c_1$ 中，所以在子句列 '$c_1$' 处为 1。 * **$z_2$ 行**: 在变量列 '2' 处为 1。因为它代表 $\overline{x_2}$，且 $\overline{x_2}$ 出现在 $c_1$ 中，所以在子句列 '$c_1$' 处为 1。 * **$y_3$ 行**: 在变量列 '3' 处为 1。因为它代表 $x_3$，且 $x_3$ 同时出现在 $c_1$ 和 $c_2$ 中，所以它在 '$c_1$' 和 '$c_2$' 列都为 1。 * **$z_3$ 行**: 在变量列 '3' 处为 1。因为它代表 $\overline{x_3}$，且 $\overline{x_3}$ 出现在 $c_k$ 中，所以在 '$c_k$' 列为 1。 * **$g_1, h_1$ 行**: 只在子句列 '$c_1$' 处为 1。 * **$t$ 行**: 左边 $l$ 列全是 1，右边 $k$ 列全是 3。 5. **无进位设计的关键**: * 在任意一个子句列（例如 $c_j$），一个变量 $x_i$ 或 $\overline{x_i}$ 最多只出现一次（这是 3SAT 的标准形式）。因此，如果我们选择了 $l$ 个变量数字（每对二选一），在 $c_j$ 这一列上，来自这些变量数字的和最多是 3 (因为 $c_j$ 只有三个文字)。 * 再加上来自填充数字 $g_j, h_j$ 的贡献（最多是 2），这一列的总和最多是 $3+2=5$。 * 由于每一列的最大和是 5，远小于 10，所以在做加法时，**绝对不会发生进位**。这保证了每一列的求和计算都是独立的，互不干扰。变量列的计算不会影响子句列，一个子句列的计算也不会影响另一个子句列。这正是用数字的“列”来模拟独立的逻辑“子句”的关键所在。 [总结] 本段给出了 **3SAT 到 SUBSET-SUM** 归约的核心构造：一个详细的数字表格。表格中的每一行是一个大数，列代表不同的数位。归约通过以下方式编码逻辑： 1. **变量**：由一对数字 $(y_i, z_i)$ 表示，它们在专属的“变量列”上都有一个 1，强制了“二选一”。 2. **子句**: 由专属的“子句列”表示。 3. **逻辑关系**: 变量数字在子句列上的 0/1 值，反映了该变量/文字是否出现在该子句中。 4. **约束**: 目标和 $t$ 在变量列上为 1，在子句列上为 3。 5. **填充**: 引入额外的“填充数字”$(g_j, h_j)$，它们只对单个子句列有贡献，用于补足差额。 整个设计的基石是“无进位加法”，通过限制每列最大和不超过基数（这里是10），确保了各列（即各逻辑约束）之间的独立性。 [存在目的] 本段的目的是将之前抽象的证明思路，转化为一个具体的、可执行的算法。它提供了从任意 3SAT 公式 $\phi$ 生成 SUBSET-SUM 实例 $\langle S, t \rangle$ 的完整、精确的说明。这个表格是整个证明的核心，后续的正确性论证都将围绕这个表格的数学属性展开。 [直觉心智模型] 想象你在为一个由 $l$ 个部门和 $k$ 个项目组成的公司做预算。 * **$t$ (目标预算)**: 总预算。要求：每个部门经费都是1个单位；每个项目经费都是3个单位。 * **$y_i, z_i$ (决策选项)**: 每个部门 $i$ 有两个互斥的行动方案 $y_i, z_i$。 * **部门经费**: 无论选 $y_i$ 还是 $z_i$，都会消耗部门 $i$ 的1个单位经费。 * **项目经费**: 选择方案 $y_i$ (或 $z_i$) 可能会同时为某些项目贡献1个单位的经费，具体取决于方案内容（即变量是否出现在子句中）。 * **$g_j, h_j$ (备用金)**: 每个项目 $j$ 还有两笔额度为1的备用金。 * **问题**: 是否能为每个部门都选择一个行动方案，并合理使用备用金，使得最终的总开销不多不少，正好等于总预算 $t$？ * **无进位**: 部门经费和项目经费是分开记账的，不会混淆。每个项目的经费也是独立核算的。这对应了无进位。 [直观想象] 你正在玩一个精密的密码锁，锁有很多行和很多列的拨轮。 * **$t$ (正确密码)**: 密码锁打开时的状态。第一组拨轮显示 "111..."，第二组拨轮显示 "333..."。 * **$S$ (你的操作)**: 你不能直接拨动拨轮，你只能选择按下一些按钮。 * **$y_i, z_i$ 按钮**: 一组成对的按钮。每对中你必须按一个。按下按钮 $y_i$ 会让第一组的第 $i$ 个拨轮加1，并可能让第二组的某些拨轮也加1。 * **$g_j, h_j$ 按钮**: 另一组“微调”按钮。按下 $g_j$ 或 $h_j$ 只会让第二组的第 $j$ 个拨轮加1。 * **无进位**: 拨轮是10进制的，但设计保证了任何一列的和都不会超过5，所以没有进位。 * **问题**: 能否通过按下按钮（选择子集），让所有拨轮最终显示正确的密码 $t$？ * 这个问题的解，直接对应了 3SAT 问题的解。 ## 5.4. 正确性证明 [原文] 接下来，我们展示这个构造为什么有效。我们证明 $\phi$ 是可满足的当且仅当 $S$ 的某个子集之和为 $t$。 假设 $\phi$ 是可满足的。我们构造 $S$ 的一个子集如下。如果在满足赋值中 $x_{i}$ 被赋值为 TRUE，我们选择 $y_{i}$；如果 $x_{i}$ 被赋值为 FALSE，我们选择 $z_{i}$。如果我们把目前选择的加起来，我们会在前 $l$ 位得到一个 1，因为我们为每个 $i$ 选择了一个 $y_{i}$ 或 $z_{i}$。此外，后 $k$ 位中的每一位都是 1 到 3 之间的数字，因为每个子句都得到满足，因此包含 1 到 3 个真文字。我们另外选择足够多的 $g$ 和 $h$ 数字，使后 $k$ 位中的每一位都达到 3，从而达到目标。 假设 $S$ 的一个子集之和为 $t$。我们通过几次观察来构造 $\phi$ 的一个满足赋值。首先，$S$ 成员中的所有数字都是 0 或 1。此外，描述 $S$ 的表格中的每一列最多包含五个 1。因此，当 $S$ 的一个子集相加时，绝不会发生进位到下一列。为了在前 $l$ 列中得到一个 1，该子集必须为每个 $i$ 包含 $y_{i}$ 或 $z_{i}$，但不能两者都包含。 现在我们进行满足赋值。如果子集包含 $y_{i}$，我们将 $x_{i}$ 赋值为 TRUE；否则，我们将其赋值为 FALSE。这个赋值必须满足 $\phi$，因为在最后 $k$ 列中的每一列，和总是 3。在列 $c_{j}$ 中，最多 2 可以来自 $g_{j}$ 和 $h_{j}$，因此该列中至少有 1 必须来自子集中的某个 $y_{i}$ 或 $z_{i}$。如果是 $y_{i}$，则 $x_{i}$ 出现在 $c_{j}$ 中并被赋值为真，因此 $c_{j}$ 得到满足。如果是 $z_{i}$，则 $\overline{x_{i}}$ 出现在 $c_{j}$ 中并且 $x_{i}$ 被赋值为假，因此 $c_{j}$ 得到满足。因此，$\phi$ 得到满足。 最后，我们必须确保归约可以在多项式时间内完成。该表格的大小大约为 $(k+l)^{2}$，并且对于任何 $\phi$，每个条目都可以轻松计算。因此，总时间是 $O\left(n^{2}\right)$ 的简单阶段。 [逐步解释] 这部分对 **SUBSET-SUM** 归约的正确性进行了双向证明。 **第一部分：证明 $\phi$ 可满足 $\Rightarrow$ 存在和为 $t$ 的子集** 1. **“假设 $\phi$ 是可满足的。”**: 我们从一个已知的满足赋值开始。 2. **构造子集 - 第一步 (变量数字)**: * 根据赋值来选择变量数字： * 如果 $x_i$ 为真，选择 $y_i$ 放入子集。 * 如果 $x_i$ 为假，选择 $z_i$ 放入子集。 * 这一步我们选了 $l$ 个数字。 3. **部分和的分析**: * **变量列 (左侧)**: 对于每一列 $i$，我们都从 $(y_i, z_i)$ 中选了一个，且只选了一个。这两个数字在第 $i$ 列都是 1。因此，我们选出的 $l$ 个数字在每一列变量列上的和都恰好是 1。这与目标 $t$ 的左半部分完全匹配。 * **子句列 (右侧)**: 对于每一列 $c_j$，其和是多少？这个和等于我们选出的 $l$ 个变量数字中，在 $c_j$ 列为 1 的个数。这等价于在子句 $c_j$ 中，被赋值为真的文字的数量。因为我们假设 $\phi$ 是可满足的，所以每个子句都至少有一个真文字。因此，对于每一列 $c_j$，目前来自变量数字的和是一个在 1 到 3 之间的整数。 4. **构造子集 - 第二步 (填充数字)**: * 我们的目标是让每个子句列的和都达到 3。 * 对于每个子句列 $c_j$： * 如果来自变量数字的和是 1，我们就需要再补 2。我们把 $g_j$ 和 $h_j$ 都选入子集（它们各贡献1）。 * 如果来自变量数字的和是 2，我们就需要再补 1。我们只选择 $g_j$（或 $h_j$）放入子集。 * 如果来自变量数字的和是 3，我们什么都不用补。我们不选择 $g_j$ 和 $h_j$。 5. **最终验证**: * 我们构造的子集包含了 $l$ 个变量数字和一些填充数字。 * 将子集中的所有数字相加。由于无进位，我们可以按列检查： * 左边 $l$ 个变量列，每一列的和都是 1。 * 右边 $k$ 个子句列，每一列的和都被我们精确地补到了 3。 * 这个总和与目标和 $t$ 完全相同。因此，我们成功找到了一个和为 $t$ 的子集。 **第二部分：证明 存在和为 $t$ 的子集 $\Rightarrow \phi$ 可满足** 1. **“假设 $S$ 的一个子集之和为 $t$。”**: 我们从一个已知的解（一个和为 $t$ 的子集）开始。 2. **“首先...绝不会发生进位到下一列。”**: 这是整个反向证明的基石。因为每列的和最多是 5 (3个来自变量，2个来自填充)，所以求和时不同列之间是完全独立的。我们可以像解方程组一样，独立地看每一列。 3. **分析变量列 (左侧)**: * 目标 $t$ 在变量列 $i$ 的值是 1。 * 在整个集合 $S$ 中，只有 $y_i$ 和 $z_i$ 在这一列有非零值 (都是1)。 * 为了让第 $i$ 列的和为 1，我们必须且只能从 $\{y_i, z_i\}$ 中选择一个放入子集。不能都不选（和为0），也不能都选（和为2）。 * 这对所有 $l$ 个变量列都成立。因此，解子集必须包含 $l$ 个变量数字，每对 $(y_i, z_i)$ 中恰好一个。 4. **构造赋值**: * 基于上面的观察，我们这样定义赋值： * 如果解子集中包含 $y_i$，则令 $x_i = $ 真。 * 如果解子集中包含 $z_i$，则令 $x_i = $ 假。 * 这是一个明确、无矛盾的赋值。 5. **验证赋值的满足性**: * 我们现在需要证明这个赋值能满足所有子句。 * 分析任意一个子句列 $c_j$。我们知道解子集在这一列的和必须是 3。 * 这个和来自两部分：来自所选的 $l$ 个变量数字的贡献，和来自填充数字 $g_j, h_j$ 的贡献。 * 填充数字 $g_j, h_j$ 在 $c_j$ 列最多只能贡献 2 (如果两个都选)。 * 因此，为了凑够 3，来自**变量数字**的贡献必须**至少是 1**。 * 来自变量数字在 $c_j$ 列的贡献是什么？就是我们根据赋值选中的那些 $y_i$ 或 $z_i$ 中，在 $c_j$ 列为 1 的个数。 * 这个贡献至少是 1，意味着至少有一个被选中的变量数字，在 $c_j$ 列为 1。 * 如果这个数字是 $y_i$，意味着我们选了 $y_i$ (即 $x_i=$ 真)，并且 $y_i$ 在 $c_j$ 列为 1 (即 $x_i$ 出现在 $c_j$ 中)。所以 $c_j$ 被满足。 * 如果这个数字是 $z_i$，意味着我们选了 $z_i$ (即 $x_i=$ 假)，并且 $z_i$ 在 $c_j$ 列为 1 (即 $\overline{x_i}$ 出现在 $c_j$ 中)。所以 $c_j$ 也被满足。 * 既然对任意子句 $c_j$ 都成立，那么整个公式 $\phi$ 都被满足。 6. **多项式时间分析**: * 构造表格需要多少时间？表格有 $2l+2k+1$ 行， $l+k$ 列。大小是 $O((l+k)^2)$。 * 每个格子的数字是 0 或 1，计算很简单。 * 将这些 0/1 序列转换为十进制大数，所需的时间也与数字的位数（即 $l+k$）成多项式关系。 * 公式大小 $n \approx l+k$，所以构造时间是 $O(n^2)$ 级别，是多项式时间的。 [总结] 本段完美地完成了 **SUBSET-SUM** 归约的正确性证明。 * **正向证明**展示了如何从一个满足赋值出发，通过“按值选变量，按需选填充”的策略，精确地构造出一个和为 $t$ 的数字子集。 * **反向证明**利用了“无进位”这一关键特性，首先证明了任何解子集都必须对每对变量数字作“二选一”，从而建立了一个从解到赋值的唯一映射。然后通过分析子句列的和，证明了这个赋值必须满足所有子句。 * 最后，分析了构造过程的时间复杂度，确认其为多项式级别。至此，**SUBSET-SUM** 是 **NP-完全**的结论被牢固确立。 [存在目的] 本段是 **SUBSET-SUM** 归约的逻辑核心。它用严谨的数学推导，验证了上一节中精巧的数字构造确实达到了预期的目的。它展示了算术运算（求和）是如何在特定的约束（无进位）下，完美地模拟了布尔逻辑运算。这是 **NP-完全**性理论中一个极具代表性和启发性的证明。 [直觉心智模型] 回到预算问题： * **正向证明**: 如果你有一个可行的公司运营方案（满足赋值），那么你就能制定出一份完美的预算执行单。你先根据方案选择必须执行的部门行动（选 $y_i, z_i$），然后发现每个项目都至少有了一笔启动资金。最后你再从备用金里拨款，把每个项目的经费都补足到3个单位。最终总开销正好等于总预算。 * **反向证明**: 你拿到了一份据说是完美的预算执行单（解子集）。你检查后发现：1. 每个部门的经费正好是1，这说明每个部门都恰好执行了一个行动方案。你据此可以反推出公司的运营方案。2. 你发现每个项目的经费都是3，而备用金最多只能提供2，所以每个项目一开始就必须从部门的行动方案里至少获得1个单位的经费。这说明你反推出的这个运营方案，保证了每个项目都能启动，是可行的。 [直观想象] 回到密码锁问题： * **正向证明**: 如果你知道谜题的正确答案（满足赋值），你就可以按答案去按动对应的 $y_i, z_i$ 按钮。然后你观察第二组拨轮的状态，发现每个拨轮显示的数字都是1、2或3。你再按动相应的微调按钮 $g_j, h_j$ 一次或两次，就能把所有拨轮都调到3。此时，你看整个密码锁，它显示的就是正确的密码 $t$。 * **反向证明**: 你发现了一组能打开锁的按钮组合（解子集）。你分析后发现：1. 要让第一组拨轮显示 "111..."，你必须在每对 $(y_i, z_i)$ 按钮中只按一个。这给了你一个谜题的答案。2. 你又发现，要让第二组的第 $j$ 个拨轮显示3，光靠微调按钮（最多加2）是不够的，必须有某个你按下的 $y_i/z_i$ 按钮为它贡献了至少1。这说明你的答案让谜题的第 $j$ 个逻辑约束被满足了。这对所有逻辑约束都成立，所以你的答案是正确的。 # 6. 练习题解析 ## 6.1. 练习 7.1 [原文] 7.1 回答每个部分“真”或“假”。 a. $2 n=O(n)$。 **A**d. $n \log n=O\left(n^{2}\right)$。 b. $n^{2}=O(n)$。 e. $3^{n}=2^{O(n)}$。 **A**c. $n^{2}=O\left(n \log ^{2} n\right)$。 f. $2^{2^{n}}=O\left(2^{2^{n}}\right)$。 [逐步解释] 这个练习考察对大O符号 (Big-O notation) 的基本理解。大O符号描述了函数增长的**上界**。$f(n) = O(g(n))$ 意味着函数 $f(n)$ 的增长速度不快于函数 $g(n)$（在某个常数因子下）。 * **a. $2n = O(n)$**: **真**。 * **解释**: $2n$ 和 $n$ 是线性关系。根据大O定义，存在常数 $c=3$ 和 $n_0=1$，使得对于所有 $n \ge n_0$，都有 $2n \le c \cdot n$。常数因子在O表示法中被忽略。 * **b. $n^2 = O(n)$**: **假**。 * **解释**: $n^2$ (二次方) 的增长速度**快于** $n$ (线性)。不存在任何常数 $c$，使得当 $n$ 足够大时，$n^2 \le c \cdot n$ 成立。因为该不等式化简为 $n \le c$，而 $n$ 是可以无限增长的。 * **c. $n^2 = O(n \log^2 n)$**: **假**。 * **解释**: $n^2$ 的增长速度**快于** $n \log^2 n$。比较 $n^2$ 和 $n \log^2 n$，可以消去一个 $n$，变成比较 $n$ 和 $\log^2 n$。$n$ 的增长速度远快于 $\log^2 n$。 * **d. $n \log n = O(n^2)$**: **真**。 * **解释**: $n \log n$ 的增长速度**慢于** $n^2$。比较 $n \log n$ 和 $n^2$，消去 $n$ 后变成比较 $\log n$ 和 $n$。$n$ 的增长速度远快于 $\log n$。因此 $n \log n$ 被 $n^2$ "压住"了。 * **e. $3^n = 2^{O(n)}$**: **真**。 * **解释**: 这是一个关于指数函数底数变换的问题。$3^n = (2^{\log_2 3})^n = 2^{n \log_2 3}$。因为 $\log_2 3$ 是一个常数 (大约 1.58)，所以 $n \log_2 3$ 是 $n$ 的线性函数，即 $n \log_2 3 = O(n)$。因此，整个表达式可以写成 $2^{O(n)}$。 * **f. $2^{2^n} = O(2^{2^n})$**: **真**。 * **解释**: 任何函数都是其自身的上界（当常数 $c \ge 1$ 时）。$f(n) = O(f(n))$ 总是成立的。这在考察大O定义的边界情况。 ## 6.2. 练习 7.2 [原文] 7.2 回答每个部分“真”或“假”。 a. $n=o(2 n)$。 ${ }^{\text {A }}$d. $1=o(n)$。 b. $2 n=o\left(n^{2}\right)$。 e. $n=o(\log n)$。 **A**c. $2^{n}=o\left(3^{n}\right)$。 f. $1=o(1 / n)$。 [逐步解释] 这个练习考察对小o符号 (little-o notation) 的理解。小o符号描述了函数增长的**严格上界**。$f(n) = o(g(n))$ 意味着函数 $f(n)$ 的增长速度**远慢于**函数 $g(n)$。形式上，$\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$。 * **a. $n=o(2 n)$**: **假**。 * **解释**: $n$ 和 $2n$ 的增长速度是同阶的（线性）。它们的比值 $\frac{n}{2n} = \frac{1}{2}$，极限不为 0。 * **b. $2n=o(n^2)$**: **真**。 * **解释**: 线性增长远慢于二次方增长。它们的比值 $\frac{2n}{n^2} = \frac{2}{n}$，当 $n \to \infty$ 时，极限为 0。 * **c. $2^n=o(3^n)$**: **真**。 * **解释**: 指数函数，底数越大增长越快。它们的比值 $\frac{2^n}{3^n} = (\frac{2}{3})^n$。因为 $\frac{2}{3} < 1$，当 $n \to \infty$ 时，极限为 0。 * **d. $1=o(n)$**: **真**。 * **解释**: 常数增长远慢于线性增长。它们的比值 $\frac{1}{n}$，当 $n \to \infty$ 时，极限为 0。 * **e. $n=o(\log n)$**: **假**。 * **解释**: 线性增长**快于**对数增长。它们的比值 $\frac{n}{\log n}$，当 $n \to \infty$ 时，极限为 $\infty$。应该是 $\log n = o(n)$。 * **f. $1=o(1/n)$**: **假**。 * **解释**: 当 $n \to \infty$ 时，$1/n$ 趋近于 0。常数 1 比一个趋近于 0 的函数增长得**快得多**。它们的比值 $\frac{1}{1/n} = n$，极限为 $\infty$。 ## 6.3. 练习 7.3 - 7.12 [逐步解释] * **7.3 互质判断**: 要求使用欧几里得算法（辗转相除法）来计算两对数的最大公约数 (GCD)。如果 GCD 为 1，则两数互质。这是一个 **P** 类问题。 * **7.4 CFG 动态规划**: 要求手动执行 CYK 算法（或类似的基于动态规划的上下文无关文法识别算法），填写一个表格来判断字符串 "baba" 是否能被给定的文法 $G$ 生成。这也是一个 **P** 类问题。 * **7.5 公式可满足性**: 询问公式 $(x \vee y) \wedge(x \vee \bar{y}) \wedge(\bar{x} \vee y) \wedge(\bar{x} \vee \bar{y})$ 是否可满足。可以通过观察发现： * $(x \vee y) \wedge(x \vee \bar{y})$ 等价于 $x$。 * $(\bar{x} \vee y) \wedge(\bar{x} \vee \bar{y})$ 等价于 $\bar{x}$。 * 所以整个公式等价于 $x \wedge \bar{x}$，这永远为假。因此公式**不可满足**。 * **7.6 P 的封闭性**: 要求证明 **P** 类在并集、连接和补集运算下是封闭的。 * **并集**: 运行两个多项式时间算法，如果任何一个接受，则接受。总时间是多项式。 * **连接**: 假设字符串 $w$ 可以分割成 $w=uv$，其中 $u$ 在语言 A, $v$ 在语言 B。可以遍历所有可能的分割点，对每个分割点运行两个多项式算法。分割点有 $n+1$ 个，总时间是多项式。 * **补集**: 运行原来的多项式时间算法，如果它接受则拒绝，如果它拒绝则接受。时间不变。 * **7.7 NP 的封闭性**: 要求证明 **NP** 在并集和连接下是封闭的。 * **并集**: 非确定性地猜测输入 $w$ 属于哪个语言，然后使用该语言的验证器来验证。 * **连接**: 非确定性地猜测 $w$ 的分割点，然后非确定性地为两部分猜测证书，并同时验证。 * **7.8 CONNECTED in P**: 要求分析图的连通性算法（如广度优先搜索 BFS 或深度优先搜索 DFS），证明它在多项式时间内运行，因此 **CONNECTED** 问题属于 **P** 类。BFS/DFS 的时间复杂度是 $O(V+E)$，其中 V 是节点数，E 是边数，这是多项式的。 * **7.9 TRIANGLE in P**: 要求证明在图中寻找一个三角形（3-团）是 **P** 类问题。可以通过遍历所有三元组节点 $\{i, j, k\}$，检查它们之间是否两两都有边。节点数为 $n$ 时，有 $O(n^3)$ 个三元组，这是一个多项式时间算法。 * **7.10 $ALL_{DFA}$ in P**: $ALL_{DFA} = \{\langle A \rangle \mid A \text{ is a DFA and } L(A) = \Sigma^*\}$。要判断一个 DFA 是否接受所有字符串，等价于判断其补语言是否为空。构造 DFA $A$ 的补 DFA（接受状态变非接受，反之亦然）是容易的。然后判断这个补 DFA 的语言是否为空，只需检查从起始状态是否能到达任何一个接受状态。这可以用 BFS/DFS 在多项式时间内完成。 * **7.11 算法时间复杂性分析**: * **a. $EQ_{DFA} \in P$**: 判断两个 DFA $A$ 和 $B$ 是否等价。可以构造一个新的 DFA $C$，它接受的语言是 $(L(A) \cap \overline{L(B)}) \cup (\overline{L(A)} \cap L(B))$（对称差）。这可以通过标准的DFA乘积和补运算构造出来。然后判断 $L(C)$ 是否为空即可。所有步骤都是多项式时间的。 * **b. 星封闭语言**: 判断 DFA $A$ 的语言是否满足 $L(A) = (L(A))^*$。这等价于判断 $L(A)$ 是否等于 $L(A^*)$。我们可以为 $L(A)$ 构造一个识别 $L(A)^*$ 的 NFA（通过在 $A$ 的接受状态到开始状态加 $\epsilon$ 边等方法），然后将其确定化为 DFA $B$。最后判断 DFA $A$ 和 DFA $B$ 是否等价，这又回到了 (a) 中的 $EQ_{DFA}$ 问题。 * **7.12 ISO in NP**: $ISO = \{\langle G, H \rangle \mid G, H \text{ 是同构图}\}$。要求证明图同构问题属于 **NP**。给定一个声称是同构的节点映射 $f: V_G \to V_H$ 作为证书。我们可以在多项式时间内验证它：1. 检查 $f$是否是一个双射（一一对应）。2. 检查对于 $G$ 中的任意两个节点 $u, v$，边 $(u,v)$ 存在当且仅当边 $(f(u), f(v))$ 在 $H$ 中存在。这个验证过程是多项式时间的，因此 $ISO \in \mathrm{NP}$。（注意：$ISO$ 是否在P或NP-complete中，是著名的未解难题。） # 7. 行间公式索引 1. $$

$$ **解释**：一个泛化的 3-CNF 布尔公式 $\phi$ 的结构，由 $k$ 个子句通过逻辑与连接而成。 2. $$

$$ **解释**：一条通过有向图 $G$ 的哈密顿路径 $P$ 的节点序列。 3. $$

$$ **解释**：在无向图 $G'$ 中，与有向图 $G$ 的哈密顿路径 $P$ 相对应的哈密顿路径 $P'$ 的节点序列。 4. $$

$$ **解释**：在 **3SAT** 到 **SUBSET-SUM** 的归约中，所构造的数字集合 $S$ 的元素构成，分为变量数字和填充数字。 5. $$

$$ **解释**：一个具体的 3-CNF 公式例子，用于说明 **SUBSET-SUM** 归约中数字表格的填充方法。 6. $$

$$ **解释**：练习题 7.4 中给出的一个上下文无关文法 (CFG)，用于识别特定语言。 7. $$

$$ **解释**：练习题 7.5 中给出的一个布尔公式，要求判断其是否可满足。 [[END_OF_RESPONSE]]所有解释内容已全部输出完毕。``` $$