CSCI3130 L14 计算复杂度

课程：CSCI3130 Formal Languages and Automata Theory 本讲：原件 L14-计算复杂度-资料包.pdf（本地课件） p.1–75；原件无 Part Outline，按页序成一份 定位：从资源计数、P 与 NP，走到归约、近似算法和局部搜索。 前后：上一份 归约与不可计算函数；本地没有 L13 原件 承接：#L14-01 至 #L14-14；#L11-13 归约

从能不能算到要算多久（p.1–3）【已会】

p.1 为课程标题页，p.2 为 Computational Complexity 分节页。

p.3 Time Complexity: The number of steps during a computation

p.3 Space Complexity: Space used during a computation

不可计算意味着根本不存在满足要求的统一算法；复杂度在算法存在后计量资源。时间数转移步，空间数使用的带格，不能把文件的字节数直接当成 TM 步数。空间一般区分输入区和工作区，比较时须采用一致约定。

双带机器为何能线性比较（p.4–6）

p.4 We use a multitape Turing machine

p.5 Copy the a on the second tape

p.4 固定多带模型，用大 O 忽略常数。p.5–6 对两段等长语言先复制 a 段到第二带，再将 b 段与之逐个配对，同时检查输入确为先 a 后 b。每格仅被常数次扫描，因此总时间线性。

算一遍：输入 aaabbb，第一阶段在第二带存 aaa；比较时每读一个 b 消耗一个 a，连续三次后两侧同时结束，接受。aabbb 在第三个 b 处发现没有对应 a，拒绝。若将完整输入长度记 N，两次至常数次长度 N 的扫描合计 $O(N)$。公式按讲义重排：$L=\{a^n b^n:n\geq0\}$；这里语言参数 n 与总输入长度 N 不同。

时间类是语言集合（p.7–9）

p.8 A Deterministic Turing Machine accepts each string of length n in time O (n)

p.7 把长度换为一般 n；p.8 定义 DTIME(n)；p.9 把等长两段与复制语言放入同一集合。成员是语言，不是单台机器，同一语言只要存在足够快的算法即可入类，另外写出一个慢算法不使它出类。

补充（严格约定）：通常 DTIME 用对全部输入总停机的判定器定义。讲义只写接受串的时间，若采用此简写，还需统一可计算时钟到界拒绝，才能与判定版本对齐。后文讨论 P/NP 默认所有分支有规定时间界。

多项式时间与 CYK（p.10–12）

p.11 Polynomial time

p.10 将线性界推广为一般 T(n)。p.11 给固定 CFG 的成员测试：转成 CNF 后用 CYK，为每个区间枚举切分点，约有平方个区间、每个至多线性个切分，故 $O(n^3)$，固定文法的规则数并入常数。文法也作输入时须保留该因子。

p.12 给相邻幂次的严格时间层级。不能用“$n^2<n^3$”证明存在只能用更多时间的语言；严格性来自时间层级定理所需的模拟与对角论证，本页未展开。此处按通常适用的时间可构造条件和固定模型理解，非任意实值函数都可直接套用。

P 是所有固定次数多项式时间的并（p.13–15）

p.13 For small k we can compute the result fast

公式按 p.14 重排：$P=\bigcup_{k\geq1}\mathrm{DTIME}(n^k)$。k 是算法固定常数，不能随输入长度增长。p.15 把 CYK、等长两段、复制串归在 P 中。p.13 的 small k 是实际可用性的提醒：$n^{100}$ 虽是多项式，实际可能比某些小输入上的指数算法还慢。“P 等于所有实际快的程序”只是粗略动机。

指数增长与旅行商图（p.16–18）

p.16 Some problem instances may take centuries to solve

题面块（讲义 · TSP 示例 · PDF p.17）：

p.17 What is the least-cost round-trip route that visits each city exactly once and then returns to the starting city?

图（p.17–18）：六个顶点和十条带权无向边；为说明赋名 A=左上、B=上中、C=右上、D=右中、E=左下、F=下方。全部边为 AB5、BC3、AE4、BE2、AD1、CD2、DE6、CF10、DF8、EF3。p.18 红线是 A–B–C–D–F–E–A。看什么：每点恰好一次且最后回起点，代价为 $5+3+2+8+3+4=25$。

这是一条可行路线，但不是此图最优：A–B–E–F–C–D–A 的代价是 $5+2+3+10+2+1=23$。见附录 A1 的穷尽核对。原图标 Cost:25，未明确声称它最优，不能替图加这个结论。

穷举路线的代价（p.19）

p.19 A solution: search exhaustively all hamiltonian cycles

固定起点后排列其余城市，最多检查 $(n-1)!$ 个顺序，无向情况正反重复还可除以 2。每个候选仍需检查边和加总。讲义将阶乘时间粗写成约指数时间；严格地说 $n!$ 不是 $\Theta(2^n)$，其增长量级是 $2^{\Theta(n\log n)}$。穷举算法很慢也不证明问题没有多项式算法。

算一遍：6 城市固定起点最多 120 个顺序，无向去反向重复后 60 个；图不完全时许多顺序缺边而无效。增加到 10 城市时同一计数为 181440，常数优化不能改变阶乘增长。

SAT 先看清否定号（p.20–22）

p.20 Question: is expression T satisfiable?

p.20 的 CNF 是多个子句的合取，每个子句是文字的析取；文字可以是变量，也可以是否定变量。全式真要求每个子句至少一个文字真。

题面块（讲义 · SAT 示例 · PDF p.21–22；公式按已查看的原图重排）：

p.21 Example: $(\overline{x_1}\lor x_2)\land(x_1\lor x_3)$

p.22 Example: $(x_1\lor x_2)\land\overline{x_1}\land\overline{x_2}$

p.21 取 $(x_1,x_2,x_3)=(0,1,1)$，两子句为 $(1\lor1)$ 与 $(0\lor1)$，故全式真。p.22 后两子句强制 x1=x2=0，但第一子句随即为假；若改变任意一个值，又违反对应单文字子句，所以不可满足。PDF 文本抽取丢掉了横线，不能直接把抽取文本当题目。

穷举赋值与非确定时间（p.23–24）

p.23 search exhaustively all the possible binary values of the variables

n 个变量有 $2^n$ 个赋值；逐一求值即可判定 SAT。更精确的时间还乘上检查公式的成本，公式长度 m 不一定与变量数相等。p.24 改为 NTIME：每条计算路径必须满足时间界，有某一接受路径便接受，全部路径拒绝才拒绝；并非现实中免费同时跑完指数台计算机。

猜中点然后验证（p.25–27）

p.25 Guess the middle of the string and copy w on the second tape

p.25 的复制串算法猜分界，将前段复制到第二带，随后逐位比较后段。p.26 每条分支的复制和比较都线性；p.27 因而放进 NTIME(n)。错误分界须在长度不等时拒绝，不能只比较两段较短者。

算一遍：abab 在第二格后分界得 ab/ab，接受；在第一格后分界得 a/bab，拒绝。abba 的所有分界都失败，故拒绝。语言也已有确定线性多带算法，这个例子展示非确定构造，不是展示非确定一定更快。

NP 的 N 不是 not（p.28–30）

p.30 Non-Deterministic Polynomial time

p.28 推广 NTIME(T(n))，p.29 取多项式界，p.30 定义 NP。原页标题是 The class NP，公式左边却印成 P；依标题与文字，应读作 $NP=\bigcup_{k\geq1}\mathrm{NTIME}(n^k)$。这里是注明原页排字问题，不是另造一条定义。

可猜可验的证书（p.31–33）

图（p.31）：标题 “NP = Non-Polynomial??”，教材截图中相应说法被圈出。看什么：这是在提醒缩写误解；NP 不意味着已证明不能多项式求解。

p.32 Guess an assignment of the variables

p.32 Check if this is a satisfying assignment

p.32 给 SAT 的证书为变量赋值，p.33 数猜测与核验时间。假设有 n 个变量、m 个文字出现，猜测需 n 位，检查需扫描 m 个文字，故在合理表示下是多项式，常见界 $O(n+m)$；原页仅用变量数 n 写检查 O(n)，隐含了公式大小的简化。

P 包含于 NP（p.34–35）

p.34 从上一算法得 SAT∈NP。p.35 的确定机可看作每步只有一个选择的非确定机，所以 $P\subseteq NP$。这不依赖任何尚未解决的猜想。

讲义中的开放问题（p.36–37）

p.36 WE DO NOT KNOW THE ANSWER

p.36–37 在这份讲义中把 P=NP、SAT 是否有确定多项式算法列为开放问题。这是原资料的表述，本文没有把尝试很多年未找到算法当作不存在算法的证明。

NP 完全性需要两项（p.38–40）

p.38 It is in NP

p.38 Every NP problem is reduced to it

第二项还要求归约在多项式时间内完成。第一项保证解有短证书可验，第二项保证足够难。p.39 是 Cook 人物介绍页，人物任职等仅为旧课件背景，不用它断言现任身份。p.40 陈述 SAT 的 NP 完全性，给出把 NTM 转成 CNF 的证明方向。

补充（讲义证明方向展开）：对于有多项式时间界的 NTM，用变量描述每个时刻、每个带格的符号及状态/读头位置。子句限制初始输入、每个局部窗口的合法转移和最终接受；存在满足赋值，当且仅当存在接受计算。时间和访问格数都是多项式，表格大小及局部约束数也是多项式。原页没有给出全部编码子句，此处解释为何规模不爆炸，不冒充完整 Cook 定理证明。

p.39 的人物背景按原页保留：Stephen A. Cook，出生年标1939，Harvard 博士、曾列 UC Berkeley、University of Toronto，Turing Award 1982；任职信息仅是旧课件记载。p.40 给的文献是 Cook, “The complexity of theorem-proving procedures,” STOC 1971, pp.151–158，本次未另读该论文。

归约网络与着色（p.41–43）

图（p.41–42）：p.41 是 Karp 21 问题的列表截图；p.42 画 Circuit-SAT→SAT→3SAT，从 3SAT 分到 Clique 与 HC，HC→TSP，Clique 周围连 Independent-Set、Vertex-Cover，再向 Hitting-Set、Subset-Sum 延伸。看什么：箭头传递困难性；仅看网络不等于已读完每条归约的证明。

题面块（讲义 · Chromatic Coloring(k) · PDF p.43）：

p.43 Given a graph G=(V, E) and an integer k, does G have a coloring for k

相邻顶点颜色不同，颜色来自 1 到 k。自取三角形示例：三条边两两连接三个点，用两色必有一条同色边，三色逐点不同则成功。一般输入 k 的问题与固定 k 的版本须区分；特别是 k=2 可用二分图检查，不能说任何固定 k 都 NP 完全。

p.41 截图中的21个问题名（保留原名，作为背景清单，未在此逐一证明）：SAT、0–1 Integer Programming、Clique、Set Packing、Vertex Cover、Set Covering、Feedback Node Set、Feedback Arc Set、Directed Hamilton Circuit、Undirected Hamilton Circuit、3-SAT、Chromatic Number、Clique Cover、Exact Cover、Hitting Set、Steiner Tree、3-Dimensional Matching、Knapsack、Job Sequencing、Partition、Max Cut。截图注明其 Knapsack 名称所指更接近 Subset Sum，不能混同下一页的0/1价值背包。

p.42 箭头的完整读法：Circuit-SAT→SAT→3SAT；3SAT→Clique、3SAT→HC；HC→TSP；Clique 与 Independent-Set、Vertex-Cover 之间有互相转换箭头，Independent-Set 与 Vertex-Cover 之间也双向；Vertex-Cover→Hitting-Set、Vertex-Cover→Subset-Sum。前两条标 local replacement，3SAT 到 Clique 标 component design，部分其他构造标 omitted。没有展开的组件证明不能仅凭箭头补成已证细节。

0/1 背包的数字核对（p.44）

题面块（讲义 · 0/1 Knapsack problem · PDF p.44）：

图/表：P1 至 P8 的价值依次 10、5、1、9、3、4、11、17；重量依次 7、3、3、10、1、9、22、15；M(weight limit)=14。原页给 “best solution: P1, P2, P3, P5(optimal)”。

选这四项重量 $7+3+3+1=14$，价值 $10+5+1+3=19$。P7、P8 单件超重；若选 P4，剩4可最多加P2和P5，价值17；若选P6，剩5可最多加P2和P5，价值12；P4与P6不能同取。不选这两件时，其余可行物品正是四件，全部装入获19，故19确为最优。

原页称此问题 NP-complete，严格类别对应给定价值门槛、问是否达到的判定版；直接求最大价值属于优化问题，通常称 NP-hard。0/1 意味每件只选一次。

划分与美术馆（p.45–46）

题面块（讲义 · Partition 示例 · PDF p.45）：

p.45 e.g. S={1, 7, 10, 9, 5, 8, 3, 13}

目标将全部元素分到互不相交的两组，使和相等。原页 S1={1,10,9,8}、S2={7,5,3,13}，两和均为28，总和56；既核对和值，也核对无重复无遗漏。数字大小与二进制编码长度的区别将在 p.63 再出现。

图（p.46）：有凹入走廊的多边形平面和四个圆形位置标记，标题 Art gallery problem，标有 NP-complete。看什么：守卫的位置需要覆盖多边形内的视线区域。原页没有给守卫位置限制、可见性边界或决策门槛；不能仅凭这张示意图给所有几何变体统一复杂度，也不宣称四个标记为最少守卫的证明。

输入大小和验证算法（p.47–48）

p.47 Size of input: size of encoded “binary” strings.

p.47 将 P 的求解与 NP 的验证联系起来。p.48 的验证器有实例 x 和证书 y 两个输入：对 YES 实例应存在一个多项式长度的证书使它接受；对 NO 实例任何证书都不应骗过它。只有“证书给出后检查很快”还需加上长度有界。

题面块（讲义 · TSP 验证 · PDF p.48）：

p.48 Question: is there a route that starts and ends at a given city, visits every city exactly once, and has total distance ≤ B?

证书是一串城市顺序。验证每城恰一次、回到起点、每条边合法、距离和≤B；假设已有访问标记和距离表，检查是多项式。原页 O(n) 是按城市与单位代价算术的简写；大整数位数也计入输入时，加法与比较需要相应位操作成本。

p.47 另列多项式开销在加法、乘法、复合下仍为多项式，P 对补封闭（交换总停机判定器的输出）。图中如果 P≠NP，P 与 NPC 位于 NP 内的不同区域；若有一个 NP 完全问题属于 P，则 NP 全部属于 P。原图把 P=NP=NPC 简写成一圈，通常的多对一归约下还应排除空语言和全语言这类无法表达两个答案的平凡语言，不能由示意图断言每个语言都 NP 完全。

p.49 的两个问题对照：

生成树覆盖所有点且无环，旅行商巡回是一条经过所有点的闭合路线；两者不能只因都连接所有城市就当作同一个问题。

判定版与优化版之间（p.49–50）

p.50 NP-completeness is associated with decision problems.

p.49 的 MST/TSP 判定问代价是否不超过门槛，优化问最小代价。p.50 说可用二分查找借判定器求最优值：整数非负权、上界可有效确定时，对门槛单调地二分。得到数值不自动得到具体路线，恢复解还需适当的自归约。

算一遍（自取区间）：最优值已知在0至31，查询15若NO则落16至31，查询23若YES则落16至23，继续至单点，至多5次门槛查询。复杂度取决于上界的位数。讲义另提醒“最优算法”有时指算法效率最优，“精确算法”指答案精确，不要混用。

三幅漫画的逻辑差别（p.51–53）

图：p.51 说自己找不到高效算法，p.52 声称高效算法不可能存在，p.53 说著名研究者也找不到。元素：三幅相似的求助场景，第三幅增加同行队伍。看什么：个人失败、数学不可能性、问题与公认难题一样难，是三种不同主张。NP 完全性通常支持第三种联系，不无条件证明第二种。不能由自己的搜索失败推出复杂度下界。

把证书定义的两个方向分别验证（补充）：证明问题在 NP 时，给一个验证器还不够，必须说明：若实例为 YES，存在一个长度多项式有界的证书能通过；若实例为 NO，任何允许的证书都不能骗过它。TSP 的城市排列长度约为 n 个编号，每个编号只需对数位；验证器同时查覆盖全部城市、无重复、每条边存在和总价不超过 B。若只核总代价，一个空路线成本0会错误通过，却没访问城市。

验证某条路线可行且不超 B，不等于验证它已经最优。后者还要排除所有更便宜的路线，并没有由这份路线本身提供短证据。因此正文将 NP 完全性赋给带阈值的判定问题，而将求最优值另外处理。这不是名词挑剔，而是 YES 见证到底要证明什么的差别。

多项式归约增加了资源要求（p.54–55）

p.54 L2 is at least as hard as L1.

公式按讲义重排：$x\in L_1\iff f(x)\in L_2$，且 f 可在输入长度的多项式时间内计算。p.54 的图把转换器 F 接在 L2 算法前；p.55 得出 L2∈P⇒L1∈P，并指出归约可传递。与 L11 只要求有限可计算的转换相比，这里不准转换自身耗指数时间。

若转换耗 $O(n^2)$，输出最多多项式长度，而目标算法耗输入长度三次方，则合成仍为多项式（粗上界 $O(n^6)$）。只写“调用一次”而不计输出长度是不够的。

二分匹配化为最大流（p.56）

p.56 The cardinality of a maximum matching in G = the value of a maximum flow in G′.

左部 L、右部 R 的每条原边定向 L→R；新增源 s→每个左点、每个右点→汇 t，所有容量为1。图中红色匹配有三条互不共享端点的边。每条匹配形成一条 s→左→右→t 的单位流；反向使用整数最大流，每个左/右点受容量1限制，选出的流量1原边必构成匹配。因此两种最优值相同。

算一遍（自取小图）：L={u1,u2}、R={v1,v2}，边 u1v1、u1v2、u2v1。两条流 s–u1–v2–t 与 s–u2–v1–t 给值2；源总容量2同时是上界，故最大匹配2。若先贪心选u1v1，可由残量网络调整而不是误判只能匹配1。

p.56 原二分图转为文字数据：左侧从上到下记 l1,…,l5，右侧从上到下记 r1,…,r4（名称为讲解所加）。边为 l1r1、l2r1、l2r3、l3r2、l3r3、l3r4、l4r3、l5r3；红色匹配是 l2r1、l3r2、l5r3。所有边都被右点 r1、r3 加左点 l3 覆盖，故任何匹配至多3条，而红色确有3条，最优值为3。新增流图的顶点是 V∪{s,t}，边集是所有 s→li、上述 li→rj、所有 rj→t，容量全为1。

HC 到 TSP 的转换（p.57–59）

题面块（讲义 · HC · PDF p.57）：

p.57 Question: is there a cycle in G that includes every vertex exactly once?

p.57 区分 HC 的存在性与 TSP 的门槛判定。p.58 对 n 顶点图建完全距离图：原边权1，非原边权2，门槛 B=n；枚举顶点对可在 $O(n^2)$ 时间完成。p.59 证明正向：原 HC 有 n 条边且都是原边，变换后总成本n，所以是合法 TSP 证书。

图（p.58–59）：原五点图存在圈 1–5–2–3–4–1，转后这五条边各1，其他顶点对为2，阈值5。看什么：不是找原图的最短路距离，而是直接把非边设为2。

反向证明不能省略（p.60–62）

p.60：若新图存在成本≤n的巡回，其 n 条边各至少1。只要一条边权2，总成本就至少n+1，因此所有边权均为1，即全是原图边，构成原 HC。两方向合起来才排除“转换后凭新增边产生虚假 YES”。

p.61 重述 NP 完全的两条件，并把只满足所有 NP 问题可归约到它的对象称为 NP-hard，不要求它自身在 NP。p.62 给证明顺序：证明目标在 NP，选已知 NP 完全源问题，构造映射，证明双向等价，证明多项式开销。不能从目标归约到已知难题来证明目标难。

面对难题有多种选择（p.63）

图/列表（p.63）：近似、伪多项式、输入分布假设、算法内部随机性、特殊实例、指数搜索/分支限界、局部搜索、无保证启发式。看什么：这些方法改善不同目标，不能统称“解决了 NP 完全问题”。

背包 DP 常用 $O(nW)$，W 为容量数值。W 用二进制输入只占约 $\log_2 W$ 位，因此对 W 多项式未必对输入长度多项式。自取 W=1024，只需11位写出，按W建表却需1025列。这就是伪多项式名称的来源。输入随机与算法随机也不同：一个改变实例假设，一个改变算法的决策。

近似比和贪心反例（p.64–65）

公式按 p.64 重排，以 $C_{\rm opt}$ 替代原图带星号的最优值：

这个比值假设相关值为正；零最优值要单独处理。最小化情形可行解C不小于最优，因此主要看 $C/C_{\rm opt}$。例如C=6、最优3，比值2，相对误差1；比值为1才是精确最优。

图（p.65）：十字形图，最大度贪心先选中心，再选四个外围点，共5；原图红色的四个邻近中心点即可覆盖全部边。看什么：一次反例说明它不总最优；原页“没有常数比保证”是更强的渐近结论，不能仅从5/4这个固定实例证明。

p.64 同页的相对误差公式：

在两种目标下都能取右边作为统一误差保证：最小化由 C≤ρCopt 得到误差≤ρ−1；最大化由 C≥Copt/ρ 得到误差≤1−1/ρ≤ρ−1。这里同样假定最优值为正。原页的 ρ(n)≥1、最优算法比值1也由定义直接得到。

任取边的两个端点：2 近似（p.66–67）

p.66 let (u, v) be an arbitrary edge of E′;

p.66 算法初始覆盖C为空；每次取一条尚未删除的边，把两个端点加入C，并删去所有与这两个点相接的边。结束时每条原边曾因某个选中端点而删除，故C覆盖全图。每次选的边互不共享端点，形成匹配A，不要求最大匹配。

图（p.66–67）：示例先取(b,c)，再取(e,f)，最后(d,g)，C={b,c,d,e,f,g}；最优覆盖图标为{b,d,e}。看什么：每条匹配边必须由最优覆盖至少拿一个端点覆盖，互不相交迫使至少拿3个，因此这个图的C为6、最优为3，正好2倍。

一般有 $\operatorname{card}(C)=2\operatorname{card}(A)\leq2\operatorname{card}(C_{\rm opt})$。有效维护边时扫描与删除总开销线性于顶点边规模；原页 O(E) 忽略了独立顶点的输入处理。

p.67 还指出最小顶点覆盖的补集为最大独立集。但取补集会减去规模，不能据此把2近似直接变成独立集2近似：上述7点例中覆盖算法留1点独立集，而最优独立集有4点。

p.66 的完整伪代码与原例：

Approx-Vertex-Cover(G):
    C ← ∅
    E′ ← E(G)
    while E′ 非空:
        从 E′ 任取边 (u,v)
        C ← C ∪ {u,v}
        删除 E′ 中所有与 u 或 v 相接的边
    return C

原图顶点为 a,b,c,d,e,f,g，边为 ab、bc、cd、ce、de、df、ef、dg。取 bc 后删 ab、bc、cd、ce，余 de、df、ef、dg；取 ef 后删 de、df、ef，余 dg；取 dg 后边集空，返回六个端点。最优覆盖 b,d,e 覆盖八条边，三条不相交选择边又证明不可能少于3。

p.67 末尾提问：“最大独立集是否存在常数比的多项式近似算法？”本页没有证明其一般答案；本文已经证明的是顶点覆盖取补不能自动得到同样的近似保证。

度量 TSP 的树上绕行（p.68–69）

p.69 Approx-TSP-Tour with triangle inequality has a ratio bound of 2.

p.68 选根、求 MST、按树的先序列出首次访问顶点，再按此顺序巡回。p.69 的证明需要三角不等式：将树边来回走一次代价为2倍MST；跳过重复顶点相当于用直边代替路径，不会增大距离；最优巡回删去一条边是生成树，所以MST不重于最优巡回。连起来得到巡回成本≤2MST≤2最优。

图（p.68–69）：散点→MST→绕树曲线→跳过重复点后的巡回→最优巡回对照。看什么：图中折线次序是一种可行近似路线，不意味着和最优路线相同。原页所写 $O(V\log V)$ 还依赖所用图表示与MST实现；一般带E条边的实现需计E，完全距离图可能有平方条边。

算一遍（数字为演示自取）：MST重9，绕树重18，捷径后巡回16，若最优为12，则16≤18≤24，近似比为4/3。若距离不满足三角不等式，捷径可能变贵，证明在第一处不等式失效。

p.68 原算法：

Approx-TSP-Tour(G):
    任取顶点 r 作为根
    用 Prim 从 r 求最小生成树 T
    L ← T 的先序遍历中顶点首次出现的列表
    返回依 L 的顺序访问顶点并回到起点的巡回 H

图中 MST 边为 ab、ad、bc、bh、de、ef、eg；以 a 为根按原图方向，首次次序为 a,b,c,h,d,e,f,g，返回 a–b–c–h–d–e–f–g–a。最后的最优对照图是 a–b–c–h–f–g–e–d–a。原图没有给边长数表，因此不能凭截图给二者虚构数值代价；论证依赖三角不等式 $d(u,w)\leq d(u,v)+d(v,w)$。

分支限界为何可以剪枝（p.70）

图（p.70）：同一个TSP实例的上图枚举大量前缀路线，下图给若干节点标代价估计并截去分支。看什么：只有证明某个分支的所有完成方案都不优于当前可行解，才可安全剪枝；不能仅凭当前前缀较贵就剪。

补充算例：最小化时已知完整路线代价27，某前缀已花15，剩余代价的有效下界为14，则该分支至少29，不可能改善27，可以剪。若所谓14只是猜测而非下界，就可能删掉最优解。分支限界保留精确性，但最坏仍可能展开指数多个节点。

p.70 例题的完整边数据：外圈 A–B9、B–C5、C–D2、D–E1、E–A3；中心 F 与 A、B、C、D、E 的边权依次5、4、8、7、5。原图只有这些边，缺边路线不可用。穷举树从 A 开始，首先得到 A–B–C–D–E–F–A，成本27；后来得到 A–E–D–C–B–F–A，成本20。下方剪枝标记包含22+9、21+6、23+8、8+16、11+9、14+10、5+15，表示已付成本加剩余成本估计；原页未单列估计的计算公式，不能把图中的下界数字当作已经证明的通用公式。

模拟退火允许暂时变坏（p.71–73）

图（p.71）：横轴States、纵轴Cost，多处谷底为局部最优，最低谷为全局最优。看什么：只接受下降的邻居会被局部谷底卡住。页内论文名称作为课件背景保留，本文未独立阅读全文。

p.72 Non-Zero probability for “up-hill” moves.

按 p.72–73 重排：若 $\Delta=C(S')-C(S)\leq0$，接受邻居；若Δ>0，以 $e^{-\Delta/T}$ 接受。T>0 为温度，每轮做P次邻居尝试，再用 $T\leftarrow rT$ 降温，需 $0<r<1$。高温较容忍上坡，低温较保守。

算一遍（自取数字）：当前10、邻居12，Δ=2。T=10时接受概率约0.819，T=1时约0.135；若随机数0.5，则前者接受后者拒绝。邻居9时Δ=-1，两个温度都接受。原伪代码返回最后状态；实际若要保留最好结果，可另记历史最优，这是补充而非原图已有步骤。有限次退火不能凭这几行代码保证全局最优。

p.71 原页列出的背景论文：Kirkpatrick、Gelatt、Vecchi, “Optimization by simulated annealing,” Science, May 1983；Chen、Chang, “Modern floorplanning based on fast simulated annealing,” ISPD-05（TCAD, April 2006）。此处只转录课件引用，未独立核验论文内容。

p.73 的伪代码完整展开：

取得初始解 S 和初温 T>0
while 尚未达到冻结/停止条件:
    for i=1,…,P:
        随机选择 S 的邻居 S′
        Δ ← cost(S′) − cost(S)
        if Δ≤0:
            S ← S′
        else:
            以 exp(−Δ/T) 的概率令 S ← S′
    T ← rT
return S

P 是每个温度的尝试次数，不是复杂度类 P。课件只写 not yet frozen，没有给数值停止阈值；具体实现必须选有限预算、最低温度或其他明确停止条件。温度日程为 T_i=r^iT_0，合理降温需0<r<1。

把退火落到具体问题（p.74–75）

图/表（p.74）：物理state对应配置，energy对应成本，ground state对应最优解，quenching对应迭代改善，careful annealing对应模拟退火。看什么：类比帮助理解，不替代正确性或收敛证明。

p.75 How to find a neighboring solution from the current one?

p.75 要给四件东西：可行解空间、邻域、成本、退火日程。以TSP为说明，解可取所有城市排列并闭合，邻居可用交换两个城市，成本为整圈边权和，日程为初温、每温度尝试数、降温率和停止条件。若图非完全，交换可能产生不存在的边，应保持可行或规定罚分；不能只写“随机换一下”就算完整算法。

考试角度：（A 级：期末-2022T1-资料包.pdf Q9–Q10，对应顶点覆盖归约与从判定恢复覆盖；扫描件视觉读取。）见附录 A2。

对输入位数算一遍，而不是对数字大小算一遍（补充）

自取背包容量 $W=2^k$。仅表示 W 就需 k+1 个二进制位，但容量索引 DP 需要 W+1 个格；若物品数固定，$O(nW)$ 中容量这一因子随 k 为 $2^k$，故对编码长度可能是指数增长。W=1024 时11位与1025列的落差只是这个一般关系的一次代入。把输入数字改用一元写法会改变输入长度，复杂度分类也应随表示重新计算，不能在论证中悄悄更换编码。

近似证明则要抓住另一种“下界”：任取互不相交边形成匹配，每条边都迫使任何顶点覆盖至少选一个端点，所以匹配大小是最优覆盖大小的下界。算法选双端点的两倍关系对所有实例成立；某一次算到恰好最优只能验证那次结果，不能替代这个普遍比值证明。

本讲核心考点

• 输入长度、数值大小、机器模型影响复杂度计算（p.3–12、47、63，C 级）。
• P 是确定多项式时间，NP 是非确定多项式时间/短证书可验（p.14、30–35、48，C 级）。
• NP 完全必须同时在 NP 且 NP-hard（p.38、61–62，C 级）。
• 判定版与优化版要区分，归约须多项式且双向保真（p.49–60，C 级）。
• HC→TSP 用权1/2与门槛n（p.57–60，C 级）。
• 顶点覆盖两端点算法与度量TSP树算法都有2近似证明（p.66–69，C 级）。
• 分支限界依赖有效界，退火以温度调节上坡概率（p.70–75，C 级）。

附录

A1 六城市图最优值的有限核对

固定A起点，并将互为反向的路线只计一次。根据正文列出的十条原图边，所有合法路线共有五类：A–B–C–D–F–E–A 成本25、A–B–C–F–E–D–A 成本28、A–B–C–F–D–E–A 成本36、A–B–E–F–C–D–A 成本23、A–D–F–C–B–E–A 成本28。每一类都访问B至F各一次且闭合；其余固定起点排列至少一处缺边。最小为23，其反向 A–D–C–F–E–B–A 同成本。

也可独立穷举固定A后的5!个排列，逐项检查边是否存在，再加权；这只是对六点算例的有限算术核对，不是一般TSP的高效算法。

返回正文

A2 作业/往年题演练（非讲义内容）：顶点覆盖归约与从判定恢复覆盖

题面块（期末-2022T1-资料包.pdf（本地课件） · Q9 · p.6，扫描件视觉读取；公式按原图重排）：

p.6 Prove that the following language is NP-hard by reducing from VC, where $\mathrm{VC}=\{\langle G,k\rangle:G\text{ has a vertex cover of size }k\}$. Recall that a vertex subset S is a vertex cover of G if every edge of G has at least one endpoint in S.

p.6 $L'=\{\langle W_1,\ldots,W_n,U,k\rangle:\text{Sets }W_1,\ldots,W_n\text{ have a cover of }U\text{ of size }k\}$.

p.6 Here each $W_i$ is a subset of U. We say that sets $W_1,\ldots,W_n$ have a cover of U of size k if there are k distinct indices $1\leq i_1<\cdots<i_k\leq n$ such that $W_{i_1}\cup\cdots\cup W_{i_k}=U$.

p.6 Example: Consider sets $W_1=\{a,b,c\}$, $W_2=\{b,e\}$, $W_3=\{d,e\}$ and $U=\{a,b,c,d,e\}$. W1, W2, W3 have a cover of U of size 2 because $W_1\cup W_3=U$ (that is, i1=1, i2=3).

把G的边集合E作全集U。对每个顶点vi，造Wi为所有与vi相接的边，保留同一个k。注意Wi的元素是“边”，不是邻居顶点。若G有恰k个顶点覆盖，取对应k个Wi，每条边至少在一个集合中，故覆盖U；反向若恰k个Wi覆盖U，选对应顶点，每条原边有至少一个端点被选，即顶点覆盖。索引与顶点一一对应，即使两个Wi内容相同也保留不同索引，不会丢失“恰k个”的语义。

构造只扫描有限图并输出关联表，规模与用时均为输入的多项式，因此VC≤pL′，L′是NP-hard。k超出顶点数等非法规模可直接映到固定NO实例；常规合法输入范围0≤k≤顶点数时上述原映射成立。本题只要求NP-hard，无需拿“给定覆盖易核对”替代困难性证明；后者只证明在NP。

题面块（同文件 · Q10 · p.6）：

p.6 Suppose some polynomial-time algorithm A decides L′ as defined above. Using A, design a polynomial-time algorithm that given $\langle W_1,\ldots,W_n,U,k\rangle\in L'$ searches for a sequence $(i_1,\ldots,i_k)$ of indices so that $W_{i_1}\cup\cdots\cup W_{i_k}=U$. Justify your algorithm.

保持已选索引集合C、未覆盖元素R、未决定的集合列表J、尚需选数t，初始C空、R=U、J为全部、t=k。依次取一个候选Wi，暂定选它，问A：“从其他未决定集合与R\Wi的交中，能否选恰t−1个覆盖R\Wi？”若YES，真正把i加入C，R更新为R\Wi，t减1；若NO，丢弃i而不选。无论哪种都从J删除i。t=0时停止，承诺与不变量保证R空；若R已空而t>0，仍从剩余索引选满t个，恰数要求不能省略。

不变量是当前残余问题有恰t个集合的解。选入分支由A的YES保证；拒选分支因为任何包含i的完成方案都被A排除，而原残余有解，所以必有不含i的方案。每次至少去掉一个候选，至多n次多项式判定调用，残余集合大小不增，总时间多项式。

沿原例演算：先试W1，残余{d,e}可由W3单独覆盖，选W1，t=1。再试W2，选它后残余{d}却要求0集合覆盖，A回答NO，跳过。最后选W3，残余空、t=0，返回(1,3)。这给具体覆盖，不只是最优值或YES答案。

回到正文：顶点覆盖归约与从判定恢复覆盖

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 HW01-2025T1-题目.pdf、HW01-2026T1-题目.pdf、HW02-2025T1-题目-更新.pdf、HW03-2025T1-题目.pdf、HW04-2025T1-题目.pdf、HW05-2025T1-题目.pdf、期中练习-含解答-学期待核.pdf、期末-2022T1-资料包.pdf、Final-Exam-2023T1-题目.pdf、Final-Exam-2024T1-题目.pdf、Final-Exam-2025T1-题目.pdf、期末-2023T1-资料包.pdf、期末-2024未核-资料包.pdf；未识别用途的 PDF：无

• 原件：L14-计算复杂度-资料包.pdf（本地课件），PDF p.1–75；p.31、41–75 的图像内容已目视核对。

• 本次独立学习修订：核对75页文本，视觉读取 p.17–18、21–22、31、41–75 的图像内容，补全图数据、算法与公式；未声称读取原页引用的外部论文。