算法理论知识点

1. 概述与学习目标

1.1 什么是算法理论

算法理论（Algorithm Theory）是研究算法的计算能力、求解效率与本质限界的数学理论体系，其核心包含三大支柱：

1. 可计算性理论（Computability Theory）：研究哪些问题可以用算法求解。奠基者是 Turing 1936 图灵机模型与 Church 1936 λ-演算，回答”什么是可计算”这一根本问题。Gödel 1931 不完备性定理与 Turing 1936 停机问题不可判定性是这一领域的两大负面结果——存在不可解的问题。

2. 计算复杂性理论（Computational Complexity Theory）：研究可解问题的求解难度。奠基者是 Hartmanis-Stearns 1965 复杂性类与 Cobham 1964/Edmonds 1965 P 类定义。复杂性理论的核心是复杂性类（complexity class）——按求解所需资源（时间、空间、随机性、交互性）将问题分类。

3. 算法设计与分析（Algorithm Design and Analysis）：研究如何高效求解具体问题。包括分治、贪心、动态规划、回溯、分支限界等设计范式，以及摊还分析、竞争分析等分析方法。

算法理论层次模型：

                            算法理论
                                |
        ┌────────────────────┬────────────────────┐
   可计算性理论          计算复杂性理论          算法设计与分析
        │                    │                       │
   ┌────┴────┐         ┌─────┴─────┐           ┌────┴────┐
  图灵机      λ-演算    P/NP/NPC    PSPACE      摊还分析   竞争分析
  Church-Turing         EXPTIME    BPP/QC      聚合/核/势能 在线算法
  停机问题              P vs NP    PCP 定理     数据流      近似算法
  Rice 定理             归约        不可近似性   随机化      启发式

为什么算法理论重要？算法理论为工程师提供”判断问题难度”的科学依据。当你面对一个新问题：

• 若证明其为 NP-Hard，则不应追求多项式时间精确算法（除非 P=NP），应转向近似算法、启发式或指数级精确算法
• 若证明其为 P，则应寻找高效多项式算法，避免过度工程化
• 若证明其 不可判定（如停机问题变体），则应放弃追求完美算法，转而设计部分解或保守近似

算法理论在工业界的应用：

1.2 算法理论的学习路径

入门（可计算性）：
  Turing 机 → Church-Turing 论题 → 停机问题 → Rice 定理
                ↓
进阶（复杂性类）：
  P/NP 定义 → 多项式归约 → Cook-Levin 定理 → Karp 21 NP 完全问题
                ↓
高级（结构理论）：
  Savitch 定理 → 层次定理 → Ladner 定理 → Baker-Gill-Solovay → PCP 定理
                ↓
应用（算法设计）：
  摊还分析 → 竞争分析 → 近似算法 → 随机化算法 → 在线算法
                ↓
前沿（现代方向）：
  量子复杂性（BQP）→ 交互式证明（IP=PSPACE）→ 不可近似性（UGC）→ 元复杂性

1.3 学习目标

完成本章学习后，读者应能够：

1. 记忆（Remember）：Turing 1936 图灵机、Church 1936 λ-演算、Gödel 1931 不完备性、Cook 1971 Cook-Levin 定理、Karp 1972 21 NP 完全问题、Levin 1973 独立发现、Savitch 1970 定理、Baker-Gill-Solovay 1975 相对化屏障、Ladner 1975 NP-intermediate、PCP 定理（Arora-Safra 1998、Dinur 2007）的历史脉络
2. 理解（Understand）：P/NP/NP-Hard/NP-Complete 形式化定义、多项式归约的数学语义、Cook-Levin 定理证明思路、Savitch 定理 NSPACE ⊆ DSPACE 平方关系、Baker-Gill-Solovay 为何阻拦 P vs NP 传统证明、PCP 定理与不可近似性联系
3. 应用（Apply）：使用 4 步法证明新问题 NP 完全、使用聚合/核算/势能三方法分析摊还代价、使用竞争分析评估在线算法、设计 2-近似度量 TSP 与 Christofides 1.5-近似算法
4. 分析（Analyze）：经典归约链 SAT → 3-SAT → CLIQUE → VERTEX-COVER → HAMILTONIAN-CYCLE → TSP 的正确性、Count-Min Sketch 与 HyperLogLog 的空间复杂度、LRU k-竞争证明
5. 评估（Evaluate）：各复杂性类（P/NP/co-NP/NPC/NP-Hard/PSPACE/EXPTIME）包含关系、P vs NP 为何难解、摊还分析三方法适用场景、确定性 vs 随机化在线算法竞争比差距
6. 对比（Compare）：摊还 vs 平均 vs 最坏情况分析、精确 vs 近似 vs 启发式算法、DPLL/CDCL SAT 求解 vs CP-SAT vs ILP 求解器在工业级组合优化上的优劣
7. 创造（Create）：设计基于复杂性理论的工业解决方案——SAT 求解器用于芯片验证、CP-SAT 用于员工排班、近似算法用于物流路径、数据流算法用于实时监控

2. 历史动机与演进

2.1 可计算性理论的奠基（1930s）

2.1.1 Hilbert 的判定问题与 Gödel 不完备性

1900 年 David Hilbert 在巴黎国际数学家大会上提出 23 个未解决问题，其中第 10 问题（判定 Diophantus 方程是否有解）与第 2 问题（算术的一致性）奠定了可计算性理论的动机。1928 年 Hilbert 与 Wilhelm Ackermann 在《Grundzüge der theoretischen Logik》中明确提出判定问题（Entscheidungsproblem）：

是否存在一个算法，能够判定一阶谓词逻辑中的任意命题是否可证？

这一问题深刻影响了 1930s 的数理逻辑发展。1931 年 Kurt Gödel 在《Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I》（Monatshefte für Mathematik und Physik 38(1):173-198, DOI:10.1007/BF01700692）中证明了不完备性定理：

任何包含初等算术的一致形式系统都存在真但不可证的命题；且该系统的一致性不能在系统内部证明。

Gödel 的证明使用了Gödel 编码——将形式系统的命题与证明编码为自然数，从而让系统”谈论自身”。这一技巧直接启发了后来的 Turing 与 Church。

2.1.2 Turing 1936 图灵机

1936 年 Alan Turing 在《On Computable Numbers, with an Application to the Entscheidungsproblem》（Proceedings of the London Mathematical Society s2-42(1):230-265, DOI:10.1112/plms/s2-42.1.230）中给出了判定问题的负面解答。Turing 的核心贡献是引入了图灵机（Turing Machine）作为可计算性的形式化模型：

图灵机形式定义：
  M = (Q, Σ, Γ, δ, q0, q_accept, q_reject)

  其中：
    Q          有限状态集
    Σ          输入字母表（不含空白符）
    Γ          带字母表（Σ ∪ {空白符}）
    δ: Q × Γ → Q × Γ × {L, R}   转移函数
    q0 ∈ Q     初始状态
    q_accept   接受状态
    q_reject   拒绝状态

图灵机由无限长磁带、读写头、有限状态控制器组成，每步根据当前状态与磁带符号决定下一状态、写入符号与读写头移动方向。Turing 证明了图灵机可模拟任意”机械化计算过程”，并提出 Church-Turing 论题：图灵机可计算的函数 = 直观可计算的函数。

Turing 同篇论文证明了停机问题不可判定：

不存在图灵机 H，使得对任意图灵机 M 与输入 w，H 能判定 M 在 w 上是否停机。

证明使用对角线法：假设 H 存在，构造对角机器 D(M) = 如果 H(M, M) = 停机则不停机，否则停机；则 D(D) 产生矛盾。

1937 年 Turing 在《Computability and λ-definability》（Journal of Symbolic Logic 2(4):153-163）中证明图灵机可计算 = Church λ-可定义，二者等价，确立 Church-Turing 论题。

2.1.3 Church 1936 λ-演算

1936 年 Alonzo Church 在《An Unsolvable Problem of Elementary Number Theory》（American Journal of Mathematics 58(2):345-363, DOI:10.2307/2371045）中独立给出判定问题的负面解答，使用 λ-演算（lambda calculus）作为可计算性模型。λ-演算是函数式编程的理论基础：

λ-演算语法（BNF）：
  <expr> ::= <var>
          | λ<var>.<expr>
          | <expr> <expr>

  规约规则：
    α-变换：λx.M → λy.M[x:=y]   （变量重命名）
    β-归约：(λx.M) N → M[x:=N]   （函数应用）
    η-变换：λx.M x → M           （外延性）

Church-Turing 论题断言：图灵机可计算 = λ-可定义 = 一般递归 = 直观可计算。这一论题虽不可严格证明（“直观可计算”非形式化），但所有已知计算模型（递归函数、Post 系统算子、Markov 算法、量子计算机）在多项式时间内可互相模拟，强有力地支持了论题。

2.2 复杂性理论的诞生（1960s）

2.2.1 Hartmanis-Stearns 1965 复杂性类

1965 年 Juris Hartmanis 与 Richard Stearns 在《On the Computational Complexity of Algorithms》（Transactions of the American Mathematical Society 117:285-306, DOI:10.1090/S0002-9947-1965-0170805-7）中奠定了计算复杂性理论的数学基础。他们引入：

1. 多带图灵机（Multi-tape Turing Machine）：每条带独立读写头，比单带更接近实际计算机
2. 时间复杂性类 TIME(f(n))：在 $O(f(n))$ 时间内可判定的语言类
3. 层次定理（Hierarchy Theorem）：若 $f$ 可构造且 $g = \omega(f \log f)$，则 TIME(f(n)) ⊊ TIME(g(n))——更多时间允许判定更多语言

Hartmanis-Stearns 因这一奠基性工作获 1993 年 Turing Award。该论文确立了”算法难度可按渐近资源消耗分类”的范式，是复杂性理论的开山之作。

2.2.2 Cobham 1964 / Edmonds 1965 P 类定义

1964 年 Alan Cobham 在《The intrinsic computational difficulty of functions》（Proc. 1964 Int. Congr. Logic Method. Phil. Sci., North-Holland, pp. 24-30）中首次将多项式时间（polynomial time）作为可处理性的形式化标准，定义 P 类：

1965 年 Jack Edmonds 在《Paths, trees, and flowers》（Canadian Journal of Mathematics 17:449-467, DOI:10.4153/CJM-1965-045-4）中独立提出多项式时间作为”好算法”的标准，并给出最大匹配的多项式算法。Edmonds 同时引入了”NP”的非形式化概念，预言了 NP 完全性的发现。

Cobham-Edmonds 论题：P 类 = 实际可处理的计算问题。这一论题虽是经验性的（多项式时间算法的高次项在大规模下仍不实际），但提供了复杂性分类的实用基准。

2.3 NP 完全性的发现（1970s）

2.3.1 Cook 1971 Cook-Levin 定理

1971 年 Stephen Cook 在《The Complexity of Theorem-Proving Procedures》（Proc. 3rd Annual ACM Symposium on Theory of Computing (STOC 71), pp. 151-158, DOI:10.1145/800157.805047）中证明：

SAT（布尔可满足性问题）是 NP 完全的。

即：对任意 NP 问题 L，存在多项式时间归约 $L \leq_p \mathrm{SAT}$。Cook 的证明思路：

1. 任取 $L \in \mathrm{NP}$，存在非确定图灵机 M 在多项式时间判定 L
2. 对输入 w，构造布尔公式 $\phi_{M,w}$ 编码 “M 接受 w” 的计算 tableau
3. $\phi_{M,w}$ 的变量表示 tableau 中每个格子的状态、符号、读写头位置
4. $\phi_{M,w}$ 的子句编码：(a) 初始格局正确；(b) 转移函数合法；(c) 接受状态可达
5. $\phi_{M,w}$ 可满足 ⟺ M 接受 w
6. 构造时间为 $|\phi_{M,w}| = O(|w|^{O(1)})$，即多项式

Cook 因此获 1982 年 Turing Award。这一定理确立了 SAT 作为 NP 完全性归约的”种子问题”地位。

2.3.2 Karp 1972 21 NP 完全问题

1972 年 Richard Karp 在《Reducibility Among Combinatorial Problems》（Proc. Symp. Complexity of Computer Computations, IBM Thomas J. Watson Research Center, March 20-22, 1972; in R.E. Miller, J.W. Thatcher (eds.), The Complexity of Computer Computations, Plenum Press, New York, pp. 85-103）中证明 21 个经典组合问题 NP 完全：

1. SATISFIABILITY
2. 0-1 INTEGER PROGRAMMING
3. CLIQUE
4. SET PACKING
5. VERTEX COVER
6. SET COVERING
7. FEEDBACK NODE SET
8. FEEDBACK ARC SET
9. DIRECTED HAMILTONIAN CYCLE
10. UNDIRECTED HAMILTONIAN CYCLE
11. 3-SAT
12. CHROMATIC NUMBER
13. CLIQUE COVER
14. EXACT COVER
15. HITTING SET
16. STEINER TREE
17. 3-DIMENSIONAL MATCHING
18. KNAPSACK
19. JOB SEQUENCING
20. PARTITION
21. MAX-CUT

Karp 的归约链：

SAT → 3-SAT → CLIQUE → VERTEX COVER → FEEDBACK ARC SET
              ↓                       ↓
            SET PACKING           HAMILTONIAN CYCLE
                                    ↓
                                  TSP
3-SAT → EXACT COVER → 3-DIM MATCHING → KNAPSACK → PARTITION

Karp 因 NP 完全性与组合优化贡献获 1985 年 Turing Award。Karp 21 问题使 NP 完全性从理论概念变为工程实践工具——工程师遇到新问题，可尝试归约到这 21 个问题之一。

2.3.3 Levin 1973 独立发现

1973 年 Leonid Levin 在《Universal Search Problems》（Проблемы передачи информации 9(3):115-116）中独立证明 SAT 的 NP 完全性。Levin 在苏联独立于 Cook 与 Karp 完成 NP 完全性理论，定义了 6 个”通用搜索问题”（universal perebor problems）。Levin 的工作因语言障碍与冷战延误，直到 1970s 末才被西方学者认识。

Cook-Levin 定理以二位独立发现者命名，体现了科学发现的同时性。Levin 后续在不可近似性、平均情况复杂性等方向有重要贡献。

2.4 结构理论的深化（1970s-1990s）

2.4.1 Savitch 1970 空间复杂性

1970 年 Walter Savitch 在《Relationships Between Nondeterministic and Deterministic Tape Complexities》（Journal of Computer and System Sciences 4(2):177-192, DOI:10.1016/S0022-0000(70)80006-X）中证明：

Savitch 定理：对任意可构造 $f(n) \geq \log n$，$\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)$。

证明使用可达性算法（reachability）：非确定图灵机的接受计算可视为配置图中的路径问题，使用分治判定 s 到 t 是否可达，递归深度 $O(\log N)$，每层存储 $O(f(n))$ 配置，总空间 $O(f(n)^2)$。

Savitch 定理蕴含 $\mathrm{NPSPACE} = \mathrm{PSPACE}$——非确定性在空间资源上仅平方损失，与时间资源的指数差距（P vs NP 疑题）形成鲜明对比。

2.4.2 Baker-Gill-Solovay 1975 相对化屏障

1975 年 Theodore Baker、John Gill、Robert Solovay 在《Relativizations of the P=?NP Question》（SIAM Journal on Computing 4(4):431-442, DOI:10.1137/0204037）中证明：

存在 oracle A 使得 $\mathrm{P}^A = \mathrm{NP}^A$；也存在 oracle B 使得 $\mathrm{P}^B \neq \mathrm{NP}^B$。

具体构造：

• $A$ 为 PSPACE 完全语言 $QBF$，则 $\mathrm{P}^A = \mathrm{NP}^A = \mathrm{PSPACE}$
• $B$ 为随机 oracle，Bennett-Gill 1981 证明对随机 B 几乎必然 $\mathrm{P}^B \neq \mathrm{NP}^B$

相对化屏障的含义：任何”对 oracle 保持不变”的证明技术（即所谓 relativizing proof）都无法解决 P vs NP 问题。这阻拦了大量传统证明技术：

• 对角线法（diagonalization）
• 层次定理证明
• 模拟论证（simulation argument）

P vs NP 的解决需要”非相对化”新技术。

2.4.3 Ladner 1975 NP-intermediate

1975 年 Richard Ladner 在《On the Structure of Polynomial Time Reducibility》（Journal of the ACM 22(1):155-171, DOI:10.1145/321864.321877）中证明：

Ladner 定理：若 $\mathrm{P} \neq \mathrm{NP}$，则存在 $L \in \mathrm{NP} \setminus \mathrm{P}$ 既非 P 中也非 NP 完全。

即 NP 中存在”中间难度”问题（NP-intermediate）。候选 NP-intermediate 问题包括：

• 图同构问题（Graph Isomorphism）：Babai 2015 给出准多项式时间算法 $2^{O((\log n)^5)}$
• 离散对数（Discrete Logarithm）：在经典计算机上无多项式算法，但量子计算机 Shor 算法可解
• 最短向量问题（Shortest Vector Problem, SVP）：格密码学基础
• 整数分解（Integer Factorization）：Shor 算法可量子求解

Ladner 定理表明 NP 的内部结构远比”P + NP-Complete”二元划分复杂。

2.4.4 Razborov-Rudich 1997 自然证明屏障

1997 年 Alexander Razborov 与 Steven Rudich 在《Natural Proofs》（Journal of Computer and System Sciences 55(1):24-35, DOI:10.1006/jcss.1997.1494）证明：

一大类”自然”的组合证明技术无法分离 P 与 NP。

具体地，若存在满足”可构造性 + 宽广性”的证明下界技术，则可破解伪随机生成器，从而破解基于单向函数的密码学。鉴于密码学假设的可信度，自然证明技术无法解决 P vs NP。

Razborov-Rudich 与 Baker-Gill-Solovay 并列为 P vs NP 的两大屏障：

2.5 PCP 定理与不可近似性（1990s-2000s）

2.5.1 PCP 定理的发现

1992 年 Sanjeev Arora、Carsten Lund、Rajeev Motwani、Madhu Sudan、Mario Szegedy 与 Sanjeev Arora、Shmuel Safra 分别证明 PCP 定理，发表于 1998 年：

PCP 定理：$\mathrm{NP} = \mathrm{PCP}[O(\log n), O(1)]$。

即 NP 语言的证明可被概率验证器在 $O(\log n)$ 随机位、$O(1)$ 次证明查询下验证。验证器只读证明的常数位即可高概率判定真伪。

PCP 定理的革命性意义：

1. 重新定义了”证明”的概念：传统证明需线性时间读完，PCP 证明只需常数次随机查询
2. 建立了 NP 与概率可验证证明的等价
3. 直接蕴含大量不可近似性结果：MAX-3SAT 不能近似到 $7/8 + \epsilon$ 之内（除非 P=NP）

Arora-Safra 与 Arora-Lund-Motwani-Sudan-Szegedy 共获 2001 年 Gödel Prize。

2.5.2 Dinur 2007 组合证明

2007 年 Irit Dinur 在《The PCP Theorem by Gap Amplification》（JACM 54(3):Article 12, DOI:10.1145/1132516.1132534）给出 PCP 定理的纯组合证明。Dinur 的证明使用间隙放大（gap amplification）技术：

1. 将 NP 语言的判定实例表示为约束图（constraint graph）
2. 通过 expanders 与随机游走放大不可满足性间隙
3. 迭代放大直到常数间隙，每步保持图规模多项式有界

Dinur 的证明比原始代数证明简洁许多，使 PCP 定理成为更易教学的工具。Dinur 因此获 2019 年 Gödel Prize。

2.5.3 PCP 定理的不可近似性蕴含

PCP 定理直接导致现代不可近似性理论的诞生：

2.6 摊还分析与竞争分析的兴起（1980s）

2.6.1 Sleator-Tarjan 1985 摊还分析

1985 年 Daniel Sleator 与 Robert Tarjan 在《Amortized efficiency of list update and paging rules》（Communications of the ACM 28(2):202-208, DOI:10.1145/2786.2793）中系统化摊还分析（amortized analysis），引入势能方法（potential method）：

定义势能函数 $\Phi: \text{数据结构状态} \to \mathbb{R}_{\geq 0}$，满足 $\Phi(D_0) = 0$。操作的摊还代价 $\hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1})$，其中 $c_i$ 为实际代价。总摊还代价 $\sum \hat{c}_i = \sum c_i + \Phi(D_n) - \Phi(D_0) \geq \sum c_i$。

Sleator-Tarjan 用势能法分析：

• 动态数组（dynamic array）：append 摊还 $O(1)$
• Splay 树（splay tree）：所有操作摊还 $O(\log n)$
• 页面替换 LRU：k-竞争

Tarjan 1986 因数据结构与算法分析获 Turing Award。

2.6.2 在线算法与竞争分析

Sleator-Tarjan 同篇论文引入竞争分析（competitive analysis）：

在线算法 ALG 是 c-竞争的，若对所有输入序列 $I$，$|\mathrm{ALG}(I)| \leq c \cdot |\mathrm{OPT}(I)| + b$，其中 OPT 为最优离线算法。

经典结果：

竞争分析开创了在线算法这一新领域，Borodin-El-Yaniv 1998《Online Computation and Competitive Analysis》是该领域标准教材。

2.7 现代发展（2000s 至今）

2.7.1 P vs NP 千禧年大奖

2000 年 Clay Mathematics Institute 设立 7 个千禧年大奖问题（Millennium Prize Problems），每个悬赏 $1,000,000。P vs NP 是其中唯一的计算机科学问题，由 Cook 在 Clay 官方陈述中形式化：

P = NP？

Cook 2003 在《The P versus NP Problem》（Clay Mathematics Institute Monograph）中阐述了该问题的历史与重要性。截至 2026 年，该问题仍开放，多数理论计算机科学家相信 P ≠ NP。

2.7.2 量子复杂性

1994 年 Peter Shor 给出多项式时间量子算法分解整数与离散对数，威胁 RSA 密码。Shor 算法引发了量子复杂性理论研究：

• BQP（Bounded-error Quantum Polynomial time）：量子多项式时间
• 已知 BQP ⊆ PSPACE，BQP 与 NP 的关系未明
• 量子计算机是否可解 NP 完全问题？多数理论学家相信 NP ⊄ BQP

2.7.3 元复杂性

21 世纪兴起元复杂性（Meta-complexity）方向：研究”判断问题难度”本身的难度。典型问题：

• MCSP（Minimum Circuit Size Problem）：给定真值表与整数 s，是否存在大小 ≤ s 的电路计算该函数？
• MCSP 是否 NP 完全？这是复杂性理论 21 世纪核心开放问题之一

3. 形式化定义

3.1 图灵机与计算模型

3.1.1 确定性图灵机

定义 3.1（确定性图灵机，DTM） 确定性图灵机是七元组 $M = (Q, \Sigma, \Gamma, \delta, q_0, q_{acc}, q_{rej})$：

• $Q$：有限状态集
• $\Sigma$：输入字母表，不含空白符 $\sqcup$
• $\Gamma$：带字母表，$\Sigma \cup \{\sqcup\} \subseteq \Gamma$
• $\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$：转移函数
• $q_0 \in Q$：初始状态
• $q_{acc} \in Q$：接受状态
• $q_{rej} \in Q$：拒绝状态，$q_{rej} \neq q_{acc}$

配置（configuration）$(q, T, i)$ 表示当前状态 $q$、带内容 $T: \mathbb{Z} \to \Gamma$、读写头位置 $i \in \mathbb{Z}$。

计算（computation）是配置序列 $C_0 \vdash C_1 \vdash C_2 \vdash \cdots$，其中 $C_0 = (q_0, w, 0)$ 为初始配置，$C_{i+1}$ 由 $C_i$ 经 $\delta$ 转移得到。若到达 $q_{acc}$ 则接受；若到达 $q_{rej}$ 则拒绝；否则可能死循环。

3.1.2 非确定性图灵机

定义 3.2（非确定性图灵机，NTM） 非确定性图灵机的转移函数为 $\delta: Q \times \Gamma \to \mathcal{P}(Q \times \Gamma \times \{L, R\})$，即每步可能有多个合法转移。

NTM 的接受定义为：存在一个接受计算分支。这与”猜测 + 验证”的直觉一致——NTM 猜测正确分支并验证。

关键事实：DTM 可模拟 NTM，但时间开销可能指数增长。这是 P vs NP 问题的根源。

3.1.3 多带图灵机

实际复杂性理论使用多带图灵机（multi-tape TM）：含 $k$ 条带与 $k$ 个读写头。Hartmanis-Stearns 1965 证明：

单带 TM 与多带 TM 在多项式时间内等价（即 $t$ 步多带 TM 可被 $O(t^2)$ 步单带 TM 模拟）。

因此 P 类对图灵机变体（单带/多带/二维带/随机访问）鲁棒，证明 Cobham-Edmonds 论题的合理性。

3.2 复杂性类的形式化定义

3.2.1 时间复杂性类

定义 3.3（DTIME, NTIME） 设 $f: \mathbb{N} \to \mathbb{N}$：

定义 3.4（P, NP）：

NP 的等价定义（验证视角）：

其中 $y$ 称为证书（certificate/witness），$V$ 为验证器。例如 SAT 的证书是满足赋值，3-SAT 验证只需 $O(n)$ 时间。

3.2.2 空间复杂性类

定义 3.5（DSPACE, NSPACE）：

定义 3.6（PSPACE, NPSPACE, L, NL）：

Savitch 定理蕴含 $\mathrm{NPSPACE} = \mathrm{PSPACE}$。

3.2.3 指数复杂性类

定义 3.7（EXPTIME, NEXPTIME）：

层次定理（Hartmanis-Stearns 1965）保证严格包含：

3.3 多项式归约

定义 3.8（多项式时间多一归约） 语言 $L_1$ 多项式时间多一归约到 $L_2$，记 $L_1 \leq_p L_2$，若存在多项式时间可计算函数 $f: \Sigma^* \to \Sigma^*$ 使得：

性质 3.1（归约的传递性） 若 $L_1 \leq_p L_2$ 且 $L_2 \leq_p L_3$，则 $L_1 \leq_p L_3$。

性质 3.2（归约的封闭性） 若 $L_1 \leq_p L_2$ 且 $L_2 \in \mathrm{P}$，则 $L_1 \in \mathrm{P}$。

定义 3.9（NP-Hard） 语言 $L$ 是 NP-Hard 的，若对任意 $L' \in \mathrm{NP}$，$L' \leq_p L$。

定义 3.10（NP-Complete） 语言 $L$ 是 NP 完全的（NPC），若 $L \in \mathrm{NP}$ 且 $L$ 是 NP-Hard。

定理 3.1（NP 完全性的归约判据） 设 $L_{NPC}$ 为已知 NP 完全语言。若 $L_{NPC} \leq_p L$ 且 $L \in \mathrm{NP}$，则 $L$ 是 NP 完全的。

证明：对任意 $L' \in \mathrm{NP}$，由 $L_{NPC}$ 完全性 $L' \leq_p L_{NPC}$；由假设 $L_{NPC} \leq_p L$；由传递性 $L' \leq_p L$。故 $L$ 是 NP-Hard。又 $L \in \mathrm{NP}$，故 $L$ NP 完全。$\square$

3.4 NP 完全性证明的 4 步法

4 步法（Standard 4-step method）证明问题 $L$ NP 完全：

1. 证明 $L \in \mathrm{NP}$：给出多项式时间验证器，描述证书形式与验证过程
2. 选择已知 NP 完全问题 $L_{NPC}$：通常选 SAT、3-SAT、VERTEX COVER、CLIQUE、SUBSET SUM 等
3. 构造多项式归约 $f: L_{NPC} \to L$：将 $L_{NPC}$ 实例变换为 $L$ 实例
4. 证明归约正确性：
   • 完备性（completeness）：$x \in L_{NPC} \Rightarrow f(x) \in L$
   • 可靠性（soundness）：$f(x) \in L \Rightarrow x \in L_{NPC}$
   • 多项式时间性：$f$ 可在多项式时间计算

例 3.1（3-SAT NP 完全）证明 3-SAT 是 NP 完全的：

1. 3-SAT ∈ NP：证书是满足赋值，验证器在 $O(m)$ 时间检查每个子句
2. 选择 SAT 为已知 NPC（Cook-Levin 定理）
3. 构造归约 SAT → 3-SAT：使用 Tseytin 变换将任意 CNF 公式转为 3-CNF：
   • 对长度 > 3 的子句 $(l_1 \lor l_2 \lor \cdots \lor l_k)$，引入新变量 $y_1, y_2, \ldots, y_{k-3}$ 与子句 $(l_1 \lor l_2 \lor y_1) \land (\lnot y_1 \lor l_3 \lor y_2) \land \cdots \land (\lnot y_{k-3} \lor l_{k-1} \lor l_k)$
   • 对长度 1 的子句 $(l)$，引入新变量 $a, b$ 与 $(l \lor a \lor b) \land (l \lor a \lor \lnot b) \land (l \lor \lnot a \lor b) \land (l \lor \lnot a \lor \lnot b)$
   • 对长度 2 的子句类似处理
4. 正确性：Tseytin 变换保持可满足性（新变量编码子句的真值）

$\square$

4. 理论推导与复杂度分析

4.1 Cook-Levin 定理证明思路

定理 4.1（Cook-Levin 1971）SAT 是 NP 完全的。

证明思路：

1. SAT ∈ NP：证书是满足赋值，验证在 $O(n)$ 时间
2. 对任意 $L \in \mathrm{NP}$ 构造归约 $L \leq_p \mathrm{SAT}$：
   • 设 NTM $M = (Q, \Sigma, \Gamma, \delta, q_0, q_{acc}, q_{rej})$ 在 $O(n^k)$ 时间判定 $L$
   • 对输入 $w$（$|w| = n$），$M$ 在 $T = O(n^k)$ 步内停机
   • 构造布尔公式 $\phi_{M,w}$ 编码 “M 接受 w” 的计算
3. tableau 编码：
   • 计算可视为 $T \times T$ 的 tableau（每行一个配置）
   • 变量 $x_{t,i,s}$ 表示时刻 $t$、位置 $i$、符号 $s$
   • 变量 $h_{t,i}$ 表示时刻 $t$ 读写头在位置 $i$
   • 变量 $q_{t,s}$ 表示时刻 $t$ 状态为 $s$
4. 约束子句：
   • 初始格局：$q_{0,q_0} = 1$，$x_{0,i,w_i} = 1$（输入符号），其他位置空白
   • 合法性：每格恰好一个符号（互斥子句）
   • 转移一致性：相邻行配置满足 $\delta$（局部约束，相邻格子组合决定）
   • 接受：某时刻 $t$ 满足 $q_{t,q_{acc}} = 1$
5. 规模分析：变量数 $O(T^2) = O(n^{2k})$，子句数 $O(T^2) = O(n^{2k})$，构造时间多项式

$\square$

4.2 经典归约链

4.2.1 3-SAT → CLIQUE

归约：3-CNF 公式 $\phi = C_1 \land C_2 \land \cdots \land C_m$，每子句 3 文字。构造图 $G$：

• 顶点：每个文字出现对应一顶点，标签为 $(i, j)$（第 $i$ 子句第 $j$ 文字）
• 边：$(i, j)$ 与 $(i', j')$ 相邻，当且仅当 $i \neq i'$ 且两文字不矛盾（即不是 $l$ 与 $\lnot l$）

定理 4.2 $\phi$ 可满足 $\iff$ $G$ 有大小 $\geq m$ 的团。

证明：

• $(\Rightarrow)$ 若 $\phi$ 可满足，每子句有真文字，对应顶点构成大小 $m$ 的团
• $(\Leftarrow)$ 若 $G$ 有大小 $m$ 的团，团中顶点来自不同子句（无自环），矛盾文字不相邻，故可同时赋真，满足 $\phi$

$\square$

4.2.2 CLIQUE → VERTEX COVER

归约：图 $G = (V, E)$ 与整数 $k$。构造补图 $\bar{G} = (V, \bar{E})$，其中 $\bar{E} = \binom{V}{2} \setminus E$。

定理 4.3 $G$ 有大小 $k$ 的团 $\iff$ $\bar{G}$ 有大小 $|V| - k$ 的顶点覆盖。

证明：

• $S$ 是 $G$ 的团 $\iff$ $S$ 在 $G$ 中两两相邻 $\iff$ $V \setminus S$ 在 $\bar{G}$ 中两两不相邻 $\iff$ $V \setminus S$ 覆盖 $\bar{G}$ 所有边（任一边至少一端不在 $V \setminus S$ 中，即两端都在 $S$ 中，但 $S$ 在 $\bar{G}$ 中独立）

$\square$

4.2.3 VERTEX COVER → HAMILTONIAN CYCLE

此归约较复杂，使用图配件（gadget）技术：

• 顶点 $v$ 对应”选择”配件（菱形结构）
• 边 $e$ 对应”连接”配件
• 适当连接使得 Hamilton 圈恰好选择 $|VC|$ 个菱形横穿

详见 Karp 1972 原文或 Garey-Johnson 1979《Computers and Intractability》附录 A1。

4.2.4 HAMILTONIAN CYCLE → TSP

归约：图 $G = (V, E)$。构造 TSP 实例：

• 城市：$V$
• 距离矩阵：$d(u, v) = 1$ 若 $(u, v) \in E$，否则 $d(u, v) = 2$
• 阈值：$B = |V|$

定理 4.4 $G$ 有 Hamilton 圈 $\iff$ TSP 实例有长度 $\leq B$ 的环游。

证明：Hamilton 圈对应长度 $|V| = B$ 的 TSP 环游；反之长度 $\leq B$ 的 TSP 环游必全用距离 1 边，即 $G$ 中边，构成 Hamilton 圈。$\square$

4.3 Savitch 定理证明

定理 4.5（Savitch 1970）对可构造 $f(n) \geq \log n$，$\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)$。

证明思路：

1. 设 NTM $M$ 在 $f(n)$ 空间判定 $L$。$M$ 的配置数 $\leq 2^{O(f(n))}$
2. 接受计算对应配置图中从初始 $s$ 到接受 $t$ 的路径，长度 $\leq 2^{O(f(n))}$
3. 定义递归过程 $\mathrm{CANYIELD}(c_1, c_2, t)$：判断 $c_1$ 能否在 $\leq t$ 步到达 $c_2$
4. 递归式：$\mathrm{CANYIELD}(c_1, c_2, t) = \bigvee_{c'} \mathrm{CANYIELD}(c_1, c', t/2) \land \mathrm{CANYIELD}(c', c_2, t/2)$
5. 递归深度 $O(\log t) = O(f(n))$，每层存储 $O(f(n))$ 配置，总空间 $O(f(n)^2)$

推论 4.1 $\mathrm{NPSPACE} = \mathrm{PSPACE}$。

$\square$

4.4 层次定理

定理 4.6（空间层次定理）若 $f$ 空间可构造且 $g = \omega(f)$，则 $\mathrm{DSPACE}(f(n)) \subsetneq \mathrm{DSPACE}(g(n))$。

定理 4.7（时间层次定理）若 $f$ 时间可构造且 $g \log g = \omega(f)$，则 $\mathrm{DTIME}(f(n)) \subsetneq \mathrm{DTIME}(g(n))$。

推论 4.2 $\mathrm{P} \subsetneq \mathrm{EXPTIME}$，$\mathrm{NP} \subsetneq \mathrm{NEXPTIME}$。

层次定理是已知少数几个无条件分离结果，利用对角线法证明——构造语言 $L$ 使得任何 $f(n)$ 时间机器在某些输入上”被对角”。

4.5 PCP 定理与不可近似性

定理 4.8（PCP 定理，Arora-Safra 1998 + Arora-Lund-Motwani-Sudan-Szegedy 1998）$\mathrm{NP} = \mathrm{PCP}[O(\log n), O(1)]$。

直观含义：NP 语言的证明可被常数次随机查询高概率验证。

不可近似性蕴含：

定理 4.9（MAX-3SAT 不可近似性，Håstad 2001）除非 P=NP，MAX-3SAT 不能在多项式时间近似到 $7/8 + \epsilon$ 之内。

证明思路：由 PCP 定理，3-SAT 实例 $\phi$ 可归约到 MAX-3SAT 实例 $\psi$，使得：

• $\phi$ 可满足 $\Rightarrow$ $\psi$ 所有子句可满足
• $\phi$ 不可满足 $\Rightarrow$ $\psi$ 至多 $7/8 + \epsilon$ 比例子句可满足

若存在 $(7/8 + \epsilon)$-近似多项式算法 A，则：

• $\phi$ 可满足 $\Rightarrow$ A($\psi$) 给出 $\geq 1$ 比例
• $\phi$ 不可满足 $\Rightarrow$ A($\psi$) 给出 $\leq 7/8 + \epsilon$ 比例

A 可在多项式时间判定 SAT 可满足性，矛盾 P ≠ NP。$\square$

4.6 复杂性类的包含关系图

                         ┌────────────┐
                         │  EXPTIME   │
                         │  (EXP)     │
                         └────────────┘
                              │
                         ┌────┴────┐
                         │ PSPACE  │
                         └─────────┘
                              │
                    ┌─────────┴─────────┐
                    │        NP         │
                    │  ┌────────────┐   │
                    │  │ NP-Complete│   │
                    │  │  (NPC)     │   │
                    │  └────────────┘   │
                    └─────────┬─────────┘
                              │
                    ┌─────────┴─────────┐
                    │        P          │
                    └───────────────────┘
                              │
                    ┌─────────┴─────────┐
                    │   NL ⊆ P          │
                    │   ┌───┐           │
                    │   │ L │           │
                    │   └───┘           │
                    └───────────────────┘

已知：L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME
已知：L ⊊ PSPACE, P ⊊ EXPTIME（层次定理）
开放：L vs P, P vs NP, NP vs PSPACE

5. 代码示例

5.1 SAT 求解器（DPLL 算法）

DPLL（Davis-Putnam-Logemann-Loveland）算法是 SAT 求解的回溯算法基础：

from typing import List, Set, Dict, Optional

# CNF 公式表示：子句列表，每个子句为文字集合
# 文字：正整数表示正变量，负整数表示否定变量
Clause = frozenset
Formula = List[Clause]


def dpll(formula: Formula, assignment: Dict[int, bool]) -> Optional[Dict[int, bool]]:
    """DPLL 算法求解 CNF-SAT

    输入：
        formula: CNF 公式，子句列表
        assignment: 当前部分赋值

    返回：
        完整满足赋值，或 None 表示不可满足
    """
    # 单元传播（unit propagation）
    formula, assignment = unit_propagate(formula, assignment)
    if formula is None:
        return None  # 冲突
    if not formula:
        return assignment  # 所有子句满足

    # 纯文字消除（pure literal elimination）
    formula, assignment = pure_literal_eliminate(formula, assignment)
    if not formula:
        return assignment

    # 选择分支变量（启发式：最常出现的变量）
    var = choose_branching_variable(formula)

    # 尝试 var = True
    result = dpll(simplify(formula, var, True), {**assignment, var: True})
    if result is not None:
        return result

    # 尝试 var = False
    return dpll(simplify(formula, var, False), {**assignment, var: False})


def unit_propagate(formula: Formula, assignment: Dict[int, bool]) -> tuple:
    """单元传播：反复处理单文字子句"""
    while True:
        # 寻找单文字子句
        unit_clause = None
        for clause in formula:
            unassigned = [lit for lit in clause if abs(lit) not in assignment]
            if len(unassigned) == 0:
                # 子句已全部赋值
                if not any(is_satisfied(lit, assignment) for lit in clause):
                    return None, assignment  # 冲突
            elif len(unassigned) == 1:
                unit_clause = unassigned[0]
                break

        if unit_clause is None:
            return formula, assignment

        # 赋值使单元子句满足
        var = abs(unit_clause)
        value = unit_clause > 0
        assignment[var] = value
        formula = simplify(formula, var, value)


def simplify(formula: Formula, var: int, value: bool) -> Formula:
    """简化公式：删除满足子句，删除矛盾文字"""
    new_formula = []
    for clause in formula:
        # 检查子句是否已满足
        lit = var if value else -var
        if lit in clause:
            continue  # 子句已满足
        # 删除矛盾文字
        new_clause = clause - {-lit}
        if not new_clause:
            return None  # 空子句，冲突
        new_formula.append(new_clause)
    return new_formula


def is_satisfied(lit: int, assignment: Dict[int, bool]) -> bool:
    var = abs(lit)
    if var not in assignment:
        return False
    return assignment[var] == (lit > 0)


def pure_literal_eliminate(formula: Formula, assignment: Dict[int, bool]) -> tuple:
    """纯文字消除：仅以一种极性出现的文字可立即赋值"""
    polarity = {}
    for clause in formula:
        for lit in clause:
            var = abs(lit)
            sign = lit > 0
            if var in polarity:
                if polarity[var] != sign:
                    polarity[var] = None  # 双极
            else:
                polarity[var] = sign

    for var, sign in polarity.items():
        if sign is not None and var not in assignment:
            assignment[var] = sign
            formula = simplify(formula, var, sign)
            if formula is None:
                return None, assignment

    return formula, assignment


def choose_branching_variable(formula: Formula) -> int:
    """选择分支变量：使用最多出现次数启发式"""
    count = {}
    for clause in formula:
        for lit in clause:
            var = abs(lit)
            count[var] = count.get(var, 0) + 1
    return max(count, key=count.get)


# 测试：(x1 ∨ ¬x2) ∧ (¬x1 ∨ x3) ∧ (x2 ∨ x3)
formula = [frozenset([1, -2]), frozenset([-1, 3]), frozenset([2, 3])]
result = dpll(formula, {})
print(f"满足赋值: {result}")
# 输出示例：{1: True, 2: True, 3: True}

5.2 子集和问题（NP 完全性归约）

子集和问题是经典 NP 完全问题，可从 PARTITION 归约：

#include <iostream>
#include <vector>
#include <set>
using namespace std;

// 子集和问题：给定正整数集合 S 与目标 T，判断是否存在子集和为 T
// NP 完全性证明：3-SAT → SUBSET-SUM（Karp 1972 原始归约）

// 伪多项式 DP 解法：O(n * T) 时间
bool subset_sum_dp(const vector<long long>& S, long long T) {
    int n = S.size();
    // dp[i] = true 表示存在子集和为 i
    vector<char> dp(T + 1, 0);
    dp[0] = 1;
    for (long long x : S) {
        // 逆序更新避免重复使用
        for (long long i = T; i >= x; --i) {
            if (dp[i - x]) dp[i] = 1;
        }
    }
    return dp[T];
}

// 指数级精确解法（用于小规模 n ≤ 30）：Meet-in-the-Middle
// 时间 O(2^(n/2))，空间 O(2^(n/2))
bool subset_sum_mitm(const vector<long long>& S, long long T) {
    int n = S.size();
    int half = n / 2;

    // 枚举前半所有子集和
    set<long long> left_sums;
    for (int mask = 0; mask < (1 << half); ++mask) {
        long long s = 0;
        for (int i = 0; i < half; ++i) {
            if (mask & (1 << i)) s += S[i];
        }
        left_sums.insert(s);
    }

    // 枚举后半，查找补集
    int right_half = n - half;
    for (int mask = 0; mask < (1 << right_half); ++mask) {
        long long s = 0;
        for (int i = 0; i < right_half; ++i) {
            if (mask & (1 << i)) s += S[half + i];
        }
        if (left_sums.count(T - s)) return true;
    }
    return false;
}

int main() {
    vector<long long> S = {3, 34, 4, 12, 5, 2};
    long long T = 9;
    cout << "DP: " << (subset_sum_dp(S, T) ? "Yes" : "No") << endl;
    cout << "MitM: " << (subset_sum_mitm(S, T) ? "Yes" : "No") << endl;
    // 输出：DP: Yes (4 + 5 = 9)
    //       MitM: Yes
    return 0;
}

5.3 动态数组的摊还分析（Python）

import math
from typing import Any, Iterator


class DynamicArray:
    """动态数组实现，演示摊还分析

    时间复杂度（摊还）：
        - append:     O(1) 摊还
        - pop:        O(1) 摊还
        - access:     O(1) 最坏
        - insert(0):  O(n) 摊还
        - delete(0):  O(n) 摊还
    """

    def __init__(self, capacity: int = 1):
        self._capacity = max(1, capacity)
        self._size = 0
        self._data = [None] * self._capacity
        self._copy_count = 0  # 统计元素拷贝次数

    def __len__(self) -> int:
        return self._size

    def __getitem__(self, i: int) -> Any:
        if i < 0:
            i += self._size
        if not 0 <= i < self._size:
            raise IndexError("index out of range")
        return self._data[i]

    def __setitem__(self, i: int, value: Any) -> None:
        if i < 0:
            i += self._size
        if not 0 <= i < self._size:
            raise IndexError("index out of range")
        self._data[i] = value

    def append(self, value: Any) -> None:
        """追加元素，必要时扩容"""
        if self._size == self._capacity:
            self._resize(self._capacity * 2)
        self._data[self._size] = value
        self._size += 1

    def _resize(self, new_capacity: int) -> None:
        """调整容量，统计元素拷贝"""
        new_data = [None] * new_capacity
        for i in range(self._size):
            new_data[i] = self._data[i]
            self._copy_count += 1
        self._data = new_data
        self._capacity = new_capacity

    def pop(self) -> Any:
        """弹出末尾元素，必要时缩容"""
        if self._size == 0:
            raise IndexError("pop from empty array")
        value = self._data[self._size - 1]
        self._data[self._size - 1] = None
        self._size -= 1
        # 缩容：当 size < capacity / 4 时，容量减半
        if self._size < self._capacity // 4 and self._capacity > 1:
            self._resize(max(1, self._capacity // 2))
        return value

    def __iter__(self) -> Iterator:
        for i in range(self._size):
            yield self._data[i]


def verify_amortized_analysis(n: int = 10000) -> None:
    """验证 append 的摊还 O(1) 性质

    聚合分析：n 次 append 总拷贝次数 < 2n
    """
    arr = DynamicArray()
    for i in range(n):
        arr.append(i)

    # 总拷贝次数应 < 2n（理论上 n + n/2 + n/4 + ... = 2n）
    print(f"n = {n}")
    print(f"实际拷贝次数: {arr._copy_count}")
    print(f"理论上界 (2n): {2 * n}")
    print(f"摊还代价 (拷贝次数/n): {arr._copy_count / n:.4f}")
    # 输出示例：摊还代价约 1-2，符合 O(1) 摊还

    # 验证势能函数 Φ(D) = 2*size - capacity 的非负性
    # 当 size > capacity/2 时 Φ > 0；扩容后 size = capacity/2，Φ = 0
    # 操作序列中 Φ 始终非负


verify_amortized_analysis(10000)

5.4 LRU 缓存（k-竞争在线算法）

import java.util.*;

/**
 * LRU（Least Recently Used）缓存实现
 *
 * 竞争分析（Sleator-Tarjan 1985）：
 *   对容量 k 的缓存，LRU 是 k-竞争的
 *   即对任意请求序列 σ，cost(LRU, σ) ≤ k · cost(OPT, σ) + k
 *
 * 证明思路：
 *   将 σ 划分为 k-相位（k-phase），每个相位至多 k 个不同页面
 *   LRU 每相位至多 k 次未命中；OPT 每相位至少 1 次未命中
 *   故 cost(LRU) / cost(OPT) ≤ k
 */
public class LRUCache<K, V> {
    private final int capacity;
    private final Map<K, V> cache;
    private long hitCount = 0;
    private long missCount = 0;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        // LinkedHashMap 按 access-order 维护，最近访问在末尾
        this.cache = new LinkedHashMap<K, V>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > LRUCache.this.capacity;
            }
        };
    }

    public V get(K key) {
        V value = cache.get(key);
        if (value != null) {
            hitCount++;
            return value;
        }
        missCount++;
        return null;
    }

    public void put(K key, V value) {
        if (!cache.containsKey(key)) {
            missCount++;
        } else {
            hitCount++;
        }
        cache.put(key, value);
    }

    public long getHitCount() { return hitCount; }
    public long getMissCount() { return missCount; }

    public static void main(String[] args) {
        // 模拟 paging 请求序列
        int k = 3;  // 缓存容量
        int[] requests = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};

        LRUCache<Integer, Boolean> lru = new LRUCache<>(k);
        for (int page : requests) {
            if (lru.get(page) == null) {
                lru.put(page, true);
            }
        }

        System.out.println("LRU 竞争比验证 (k = " + k + ")");
        System.out.println("命中: " + lru.getHitCount());
        System.out.println("未命中: " + lru.getMissCount());
        System.out.println("理论竞争比上界: " + k);
        // 输出：LRU 应是 3-竞争的
    }
}

5.5 度量 TSP 的 2-近似算法

from typing import List, Tuple
import heapq


def tsp_2_approx(points: List[Tuple[float, float]]) -> float:
    """度量 TSP 的 2-近似算法（基于 MST）

    算法：
        1. 构造最小生成树 T
        2. 对 T 进行前序遍历，得到访问顺序
        3. 返回按前序顺序访问所有点的环游长度

    近似比证明：
        - MST 权重 w(T) ≤ OPT（删除 OPT 一条边得到生成树）
        - 前序遍历长度 ≤ 2w(T)（每边访问两次）
        - 故算法解 ≤ 2w(T) ≤ 2·OPT
    """
    n = len(points)
    if n <= 1:
        return 0.0
    if n == 2:
        return 2 * dist(points[0], points[1])

    # 步骤 1：构造 MST（Prim 算法）
    mst_edges = prim_mst(points)

    # 步骤 2：构造邻接表
    adj = [[] for _ in range(n)]
    for u, v in mst_edges:
        adj[u].append(v)
        adj[v].append(u)

    # 步骤 3：前序遍历
    visited = [False] * n
    preorder = []
    def dfs(u):
        visited[u] = True
        preorder.append(u)
        for v in adj[u]:
            if not visited[v]:
                dfs(v)
    dfs(0)

    # 步骤 4：计算环游长度（前序顺序 + 回到起点）
    total = 0.0
    for i in range(n):
        u = preorder[i]
        v = preorder[(i + 1) % n]
        total += dist(points[u], points[v])
    return total


def prim_mst(points: List[Tuple[float, float]]) -> List[Tuple[int, int]]:
    """Prim 算法构造 MST，O(n^2) 时间"""
    n = len(points)
    in_mst = [False] * n
    min_dist = [float('inf')] * n
    parent = [-1] * n
    min_dist[0] = 0

    edges = []
    for _ in range(n):
        # 选择未加入 MST 的最小距离顶点
        u = -1
        for v in range(n):
            if not in_mst[v] and (u == -1 or min_dist[v] < min_dist[u]):
                u = v

        in_mst[u] = True
        if parent[u] != -1:
            edges.append((parent[u], u))

        # 更新邻居距离
        for v in range(n):
            if not in_mst[v]:
                d = dist(points[u], points[v])
                if d < min_dist[v]:
                    min_dist[v] = d
                    parent[v] = u
    return edges


def dist(p1: Tuple[float, float], p2: Tuple[float, float]) -> float:
    """欧几里得距离（满足三角不等式，故为度量 TSP）"""
    return ((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2) ** 0.5


# 测试
points = [(0, 0), (1, 1), (2, 0), (1, -1), (3, 2)]
approx = tsp_2_approx(points)
print(f"2-近似解: {approx:.4f}")
# 输出示例：2-近似解: 11.5396

5.6 Christofides 1.5-近似算法

from typing import List, Tuple, Dict
import networkx as nx


def christofides_tsp(points: List[Tuple[float, float]]) -> float:
    """Christofides 1.5-近似算法（度量 TSP）

    算法（Christofides 1976）：
        1. 构造 MST T
        2. 找出 T 中所有奇度顶点 O
        3. 在 O 上构造最小权重完美匹配 M
        4. T ∪ M 形成 Eulerian 多重图
        5. 求 Euler 回路
        6. shortcut 重复顶点得到 Hamilton 圈

    近似比证明：
        - w(MST) ≤ OPT
        - w(perfect matching on O) ≤ OPT/2
        - 故 w(Euler) = w(MST) + w(M) ≤ 3·OPT/2
        - shortcut 不增加长度（三角不等式）
        - 故算法解 ≤ 1.5·OPT
    """
    n = len(points)
    if n <= 2:
        return 0.0 if n <= 1 else 2 * dist(points[0], points[1])

    # 构造完全图
    G = nx.Graph()
    for i in range(n):
        for j in range(i + 1, n):
            G.add_edge(i, j, weight=dist(points[i], points[j]))

    # 步骤 1：MST
    T = nx.minimum_spanning_tree(G)

    # 步骤 2：找奇度顶点
    odd_degree = [v for v in T.nodes() if T.degree(v) % 2 == 1]

    # 步骤 3：奇度顶点上的最小权重完美匹配
    # 使用 NetworkX 的 max_weight_matching（取负权转最小）
    subgraph = G.subgraph(odd_degree).copy()
    for u, v in subgraph.edges():
        subgraph[u][v]['weight'] = -subgraph[u][v]['weight']
    matching = nx.max_weight_matching(subgraph, maxcardinality=True)

    # 步骤 4：T ∪ M 形成 Eulerian 多重图
    multigraph = nx.MultiGraph(T)
    for u, v in matching:
        multigraph.add_edge(u, v, weight=dist(points[u], points[v]))

    # 步骤 5：Euler 回路
    euler_circuit = list(nx.eulerian_circuit(multigraph, source=0))

    # 步骤 6：shortcut 重复顶点
    visited = set()
    tour = []
    for u, v in euler_circuit:
        if u not in visited:
            tour.append(u)
            visited.add(u)
    tour.append(0)  # 回到起点

    # 计算总长度
    total = sum(dist(points[tour[i]], points[tour[i + 1]]) for i in range(len(tour) - 1))
    return total


def dist(p1, p2):
    return ((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2) ** 0.5


points = [(0, 0), (1, 1), (2, 0), (1, -1), (3, 2)]
approx = christofides_tsp(points)
print(f"Christofides 1.5-近似解: {approx:.4f}")

5.7 Count-Min Sketch（数据流算法）

import numpy as np
import mmh3  # MurmurHash3
from typing import List


class CountMinSketch:
    """Count-Min Sketch 频率估计算法

    空间复杂度：O(d * w) = O((1/ε) · log(1/δ))
    估计误差：|f̂ - f| ≤ ε·||f||_1，概率 ≥ 1 - δ

    应用：
        - 网络流量监控（按 IP 统计包数）
        - 搜索引擎热门查询
        - 推荐系统频率统计
    """

    def __init__(self, epsilon: float, delta: float):
        """
        epsilon: 频率估计误差上界（相对于总流量）
        delta:  估计失败概率
        """
        self.w = int(np.ceil(1 / epsilon))   # 列数
        self.d = int(np.ceil(np.log(1 / delta)))  # 行数（哈希函数数）
        self.table = np.zeros((self.d, self.w), dtype=np.int64)
        # 使用不同 seed 生成 d 个独立哈希函数
        self.seeds = [i * 31 + 17 for i in range(self.d)]

    def update(self, key: str, count: int = 1) -> None:
        """更新 key 的频率估计"""
        for i in range(self.d):
            j = mmh3.hash(key, self.seeds[i], signed=False) % self.w
            self.table[i][j] += count

    def estimate(self, key: str) -> int:
        """估计 key 的频率（上界）"""
        return min(
            self.table[i][mmh3.hash(key, self.seeds[i], signed=False) % self.w]
            for i in range(self.d)
        )


# 测试
cms = CountMinSketch(epsilon=0.01, delta=0.01)
print(f"Sketch 大小: {cms.d} 行 × {cms.w} 列 = {cms.d * cms.w} 计数器")

# 模拟数据流
stream = ["apple", "banana", "apple", "cherry", "apple", "banana"] * 1000
for item in stream:
    cms.update(item)

# 估计频率
for item in ["apple", "banana", "cherry", "grape"]:
    print(f"  {item}: 估计 = {cms.estimate(item)}, 真实 = {stream.count(item)}")
# 输出示例：估计值略大于真实值（Count-Min 总是高估）

6. 对比分析

6.1 复杂性类对比

6.2 摊还分析 vs 平均情况 vs 最坏情况

摊还分析的核心特点：

1. 不涉及概率：与平均情况不同，摊还分析对任意操作序列给硬保证
2. 针对操作序列：分析 n 次操作的总代价，平均到每次
3. 三种方法等价：聚合、核算、势能法在表达能力上等价

6.3 在线算法的确定性 vs 随机化

Yao 原理：要证明随机化算法的下界，只需构造输入分布使任何确定性算法期望代价 ≥ c·OPT。这是随机化在线算法下界证明的核心工具。

6.4 SAT 求解器对比

工业级 CDCL 求解器（如 CaDiCaL、Kissat）能解决百万变量规模的工业 SAT 实例，远超理论最坏界。这表明”NP 完全”并不等同于”实际不可解”。

6.5 近似算法 vs 精确算法 vs 启发式

7. 常见陷阱

7.1 误将 NP 当作”多项式时间不可解”

陷阱：认为 NP 完全问题就一定多项式时间不可解。

澄清：

• NP 完全性是条件性结果——除非 P=NP，否则 NPC 问题无多项式算法
• 实际中 NPC 问题在小规模（如 $n \leq 100$）可用 CDCL、CP-SAT、Concorde 等工业求解器高效解决
• 许多 NPC 问题有好的近似算法或参数化算法

正确认识：NPC 是”难度警告”，不是”不可解判决”。

7.2 归约方向错误

陷阱：证明 L 是 NP 完全时，错误地将 L 归约到已知 NPC 问题，即 $L \leq_p L_{NPC}$。

澄清：

• 证明 L NP 完全需要 $L_{NPC} \leq_p L$（即 $L_{NPC}$ 归约到 $L$）
• 这表明 $L$ 至少和 $L_{NPC}$ 一样难
• 反方向 $L \leq_p L_{NPC}$ 只能说明 $L \in \mathrm{NP}$（若 $L_{NPC} \in \mathrm{NP}$）