课程概述

北京大学软件研究所 屈婉玲 教授《算法设计与分析》（0A002）课程第 10 讲。本讲是课程的计算复杂性理论总结篇，从 Turing 机模型出发，系统建立计算复杂性的形式化理论框架，涵盖 NP 完全性理论、NP 难度、复杂性类谱系以及并行计算复杂性。

一、Turing 机模型

1.1 基本定义

双向无限带 Turing 机：M = ⟨Q, Σ, Γ, δ, q₀, B, F⟩

符号	含义
Q	有穷状态集
Γ	有穷带字符集
Σ	输入字符集，Σ ⊂ Γ
B	空白字符，B ∈ Γ － Σ
q₀	初始状态，q₀ ∈ Q
F	终结状态集，F ⊆ Q，含 qᵧ（接受）/ qɴ（拒斥）
δ	状态转移函数：(Q－F) × Γ → Q × Γ × {L, R}

1.2 瞬时描述（ID）

α₁qα₂：FSC 处于状态 q，读写头指向 α₂ 的第一个字符。

例：δ(q, xᵢ) = (p, Y, L)，则

x₁x₂…xᵢ₋₁ q xᵢ…xₙ ⊦ x₁x₂…xᵢ₋₂ p xᵢ₋₁Yxᵢ₊₁…xₙ

⊦：一步达到
⊦*：经有限步达到

1.3 经典实例：0ⁿ1ⁿ 语言

设计 Turing 机接受 L = { 0ⁿ1ⁿ | n ≥ 1 }

策略：每个巡回将一对 0 和 1 改为 X 和 Y，直到全部配对成功
状态：q₀（找 0）→ q₁（向右找 1）→ q₂（向左回 X）→ q₃（扫尾）→ qᵧ（接受）
带字符：{0, 1, X, Y, B}

例如输入 0011 的执行轨迹：

q₀0011 ⊦ Xq₁011 ⊦ X0q₁11 ⊦ Xq₂0Y1 ⊦ q₂X0Y1 ⊦ Xq₀0Y1 ⊦ XXq₁Y1 ⊦ XXYq₁1 ⊦ XXq₂YY ⊦ Xq₂XYY ⊦ XXq₀YY ⊦ XXYq₃Y ⊦ XXYYq₃ ⊦ XXYYqᵧ

1.4 Turing 机接受语言

被 M 接受的语言：

L(M) = { ω | ω ∈ Σ*, ∃α₁,α₂ ∈ Γ* (q₀ω ⊦* α₁qᵧα₂) }

如果 ω ∉ L(M)，M 可以不停机或停机在拒斥状态 qɴ。

1.5 Turing 机变种

变种	说明
单向无限带	带方格从 1 开始向右无限
多带 Turing 机	k 条双向带 + k 个读写头，初始输入写在第 1 条带
确定型 DTM	标准模型
非确定型 NDTM	每步有多个可选转移

1.6 多带 Turing 机实例：wcwᴿ 识别

L = { wcwᴿ | w 为 0-1 字符串 }，设计两种 Turing 机：

机器	时间复杂度	空间复杂度	方法
M₁（2 条带）	O(n)	O(n)	把 c 左边的 w 复制到第 2 条带，从 c 开始两边比较
M₂（2 条带）	O(n²)	O(log n)	第 2 条带当二进制计数器，逐个比较对称位置字符

二、计算复杂性理论

2.1 空间复杂度（离线 Turing 机）

离线 Turing 机 M：1 条只读输入带（带端记号）+ k 条半无限存储带。

若对每个长为 n 的输入串，M 在任一条存储带上至多扫视 S(n) 个单元，则 M 的空间复杂度为 S(n)。

2.2 时间复杂度（多带 Turing 机）

k 条双向带的 Turing 机 M，一条带包含输入。

若对每个长为 n 的输入串，M 停机前至多做 T(n) 个动作，则 M 的时间复杂度为 T(n)。

基本假设：

S(n) ≥ 1（空间复杂性至少需要 1）
T(n) ≥ n+1（时间至少需要读入输入）
log n 是 max{1, ⌈log n⌉} 的缩写

2.3 复杂性重要结果汇总

结果类型	M₁	M₂	空间	时间	条件
带压缩	k 带	k 带	cS(n), ∀0<c<1	—	—
线性加速	k 带	k 带	—	cT(n), ∀0<c<1	lim T(n)/n = ∞
带数目减少	k 带	1 带	S(n)	O(T(n)logT(n))	—
带数目减少	k 带	2 带	S(n)	(1+ε)n 等	特定场景

带数目减少定理：k 带 Turing 机可被 1 带 Turing 机模拟，时间从 T(n) 增加到 O(T(n)logT(n))，空间不变。

三、NP 完全性理论

3.1 判定问题与语言

判定问题 π = (Dπ, Yπ)：

Dπ：实例集
Yπ ⊆ Dπ：肯定实例的集合
问题：任给实例 I ∈ Dπ，问 I ∈ Yπ？

语言与判定问题的对应：在合理编码系统 e 下，Yπ 中实例的编码构成语言 L[π,e]。

算法解判定问题 π ⟺ Turing 机识别语言 L[π,e]

3.2 P 类与 NP 类

类	非形式定义	形式定义
P	确定型算法多项式时间可解的判定问题类	P = { L：存在多项式时间 DTM M 使得 L = L(M) }
NP	非确定型算法多项式时间可解的判定问题类	NP = { L：存在多项式时间 NDTM M 使得 L = L(M) }

基本关系：P ⊆ NP

核心开放问题：P = NP ?

已知 DTM 模拟 NDTM 的时间为指数时间
若能证明某个 NP 完全问题有多项式时间解，则 P = NP

3.3 难解的问题

定义：不存在确定型多项式时间算法的问题。

难解原因两类：

问题太难，多项式时间不可能找到解（主要研究对象）
解本身太庞大，表示解的符号串长度不是输入长度的多项式函数

难解问题分类：

不可判定问题：不存在算法（如停机问题）
可判定的难解问题：有算法，但不存在多项式时间算法（如半扩展正则表达式全串判定）

停机定理：不存在根据任意 Turing 机 T 的定义，能够确定 T 在输入 dT 上是否停机的算法。

3.4 多项式变换与 NP 完全性

多项式变换：设 π₁, π₂ 是判定问题，若存在函数 f: Dπ₁ → Dπ₂ 满足：

f 可用确定型算法在多项式时间计算
∀I ∈ Dπ₁, I ∈ Yπ₁ ⟺ f(I) ∈ Yπ₂

则称 π₁ 可多项式变换到 π₂，记作 π₁ ∝ π₂。

NP 完全性：若 L ∈ NP，且对任意 L’ ∈ NP 都有 L’ ∝ L，则称 L 是 NP 完全的，记作 L ∈ NPC。

三大推论：

若 L₁, L₂ ∈ NP，L₁ ∈ NPC，且 L₁ ∝ L₂，则 L₂ ∈ NPC
若 L ∈ NPC，则 L ∈ P ⇒ P = NP
若 P ≠ NP，则 NPC ∩ P = ∅

3.5 Cook 定理与 SAT

可满足性问题（SAT）：

实例：布尔变量集合 U 以及 U 上的子句集 C
问：是否存在满足 C 的真值赋值？

Cook 定理：SAT ∈ NPC

这是第一个被证明的 NP 完全问题，所有其他 NP 完全问题都通过多项式变换从 SAT 推导出来。

基本概念：

布尔变量：U = {u₁, u₂, …, uₘ}
文字：u 或 ū（u 的否定）
子句：若干文字的集合（析取），如 {u₁, u₃, ū₅}
子句集：子句的集合（合取），如 C = {{u₁,u₂,ū₅}, {u₁,u₃,ū₅}, {u₅}}
真值赋值：t: U → {T, F}
满足子句：子句中至少一个文字为真
满足子句集：每个子句都满足

四、六个基本 NP 完全问题

4.1 问题清单

问题	缩写	实例	问题
三元可满足性	3SAT	变量集 U，每个子句恰含 3 个文字	是否存在满足赋值？
三维匹配	3DM	M ⊆ W×X×Y，\|W\|=\|X\|=\|Y\|=q	是否含大小为 q 的匹配？
顶点覆盖	VC	图 G=(V,E)，正整数 K	是否存在 ≤ K 的顶点覆盖？
团	Clique	图 G=(V,E)，正整数 J	是否存在 ≥ J 的团？
哈密顿回路	HC	图 G=(V,E)，\|V\|=n	是否包含哈密顿回路？
均分	Partition	有穷集 A，每个 a∈A 有大小 S(a)∈Z⁺	是否可分成两个和相等的子集？

4.2 顶点覆盖 / 团 / 独立集的关系

设 G = (V, E)，V’ ⊆ V，则：

V’ 是 G 的顶点覆盖 ⟺ V − V’ 是 G 的独立集 ⟺ V − V’ 是补图 Ḡ 的团

推论：

G 有大小 ≤ K 的顶点覆盖 ⟺ G 有大小 ≥ |V|−K 的独立集
G 有大小 ≥ J 的团 ⟺ 补图 Ḡ 有大小 ≥ J 的独立集

三者可相互多项式变换，同属 NPC。

4.3 NP 完全性证明链

SAT → 3SAT → 3DM → 均分 → VC → 团 → HC

证明顺序（树状结构）：

SAT 是第一个 NPC 问题（Cook 定理）
所有其他 NPC 问题通过从已知 NPC 问题多项式变换得到

五、NP 完全性理论的应用

5.1 子问题分析

子问题定义：设 π = (Dπ, Yπ)，若 Dπ’ ⊆ Dπ，Yπ’ ⊆ Yπ ∩ Dπ’，则 π’ = (Dπ’, Yπ’) 是 π 的子问题。

子问题与原问题相同，只是定义域缩小（限制参数）。

子问题实例：

限制子句文字数：SAT → 3SAT → 2SAT（2SAT 属于 P）
限制图的类型：平面图、二部图、无圈图、顶点度数限制
限制常数 K 的大小：如 K=2、K=3

研究策略：努力扩大已知（P 或 NPC）区域，缩小未知区域。当 P≠NP 时，存在既不属于 NPC 也不属于 P 的中间问题。

5.2 多处理机调度问题案例

优化问题：给定任务集 T、m 台机器、任务长度 l(t)、偏序 ≺，求最短完工时间 D。

三个约束条件：

每个任务在截止时间前完成：σ(t) + l(t) ≤ D
同时工作的机器数 ≤ m
先行约束：t ≺ t’ ⇒ σ(t) + l(t) ≤ σ(t’)

判定问题：是否存在 ≤ D 的可行调度？

子问题三维结构：

偏序：任意 ≺ / 树形 ≺ / 无偏序 ≺=∅
机器数：m=1 / m≤2 / m≤3 / m≤M / m 任意
工作时间：l 任意 / l=1（等长）

通过限制参数可以得到大量子问题，部分为 P、部分为 NPC。

六、NP 难度（NP-hard）

6.1 搜索问题

搜索问题 π：有实例集 Dπ，对每个实例 I ∈ Dπ，有穷解集合 Sπ[I]。

算法 A 解搜索问题：对任何 I ∈ Dπ，A 停机，Sπ[I]=∅ 时回答无解，否则给出一个解。

搜索问题实例：

巡回售货员优化问题 TSO（找最短巡回路线）
Hamilton 回路构造问题（找一条回路）

判定问题是搜索问题的特例（解只有 Yes/No）。

6.2 Turing 归约

设 π₁, π₂ 是搜索问题，A 是利用解 π₂ 的假想子程序 s 解 π₁ 的算法。若 s 是多项式时间的则 A 也是多项式时间的，称 A 是从 π₁ 到 π₂ 的多项式时间 Turing 归约，记作 π₁ ∝T π₂。

6.3 NP-hard 与 NP-easy

NP-hard：若存在 NPC 问题 π’ 使得 π’ ∝T π，则 π 是 NP-hard（至少和 NPC 一样难）
NP-easy：若存在 NP 问题 π’ 使得 π ∝T π’，则 π 是 NP-easy（不比 NP 问题更难）
NP 等价：既是 NP-hard 又是 NP-easy

许多 NP 完全问题对应的优化问题都是 NP-hard（也是 NP-easy，即 NP 等价）。

6.4 实例：TSO 是 NP 等价的

证明思路：TSP（判定版）是 NPC，因此 TSO（优化版）是 NP-hard。只需证 TSO 是 NP-easy。

引入中间问题 TSE（巡回售货员延伸问题）：给定部分旅行路线 ϑ，问是否可延伸成长度 ≤ B 的全程旅行？

TSE ∈ NP（验证一条完整路线只需多项式时间）
TSP 判定问题是 TSE 的子问题（ϑ = <c₁> 的情况）

两步 Turing 归约（TSO → TSE）：

第一步：二分法求最短长度 B*（MinLength 算法）

Bmin ← m, Bmax ← m × max{d(ci,cj)}
while Bmax - Bmin > 1:
    B ← ⌊(Bmin + Bmax) / 2⌋
    if s(C, d, <c1>, B) == "Yes":
        Bmax ← B
    else:
        Bmin ← B
B* ← Bmax

调用 s 的次数：O(log(md))，是多项式量级。

第二步：构造解（FindSolution 算法）

从 c₁ 出发，依次尝试每个可能的下一个城市：

从 M（未访问城市）中取最小 j
检查 <c₁, cj> 能否延伸成长度 B* 的旅行
能则固定 cj，继续确定下一个
不能则换 k（M 中下一个更大的）

调用 s 的总次数：(m-2)+(m-3)+…+1 = (m-1)(m-2)/2，是 m 的多项式。

结论：TSO Turing 归约到 TSE（NP 问题），故 TSO 是 NP-easy，即 NP 等价。

类似地，六个基本 NPC 问题对应的优化问题都是 NP-hard（也是 NP 等价）。

七、复杂性类谱系

7.1 复杂性类层级

PSPACE（多项式空间）
    ↑
   NP  —  Co-NP
    ↑
   P  —  P-complete
    ↑
   NC（高度并行可解）

7.2 Co-NP

Co-NP = { L | L̄ ∈ NP } = { πᶜ | π ∈ NP }，其中 πᶜ 是 π 的补问题。

实例：HC 的补问题——图 G 中是否不存在哈密顿回路？

开放问题：HCᶜ ∈ NP ?（即 NP = Co-NP ?）

若 NP ≠ Co-NP ⇒ P ≠ NP

7.3 PSPACE

多项式空间有界的判定问题类。

NP ⊆ PSPACE（非确定型多项式时间一定在多项式空间内）
P ⊆ NP ⊆ PSPACE（真包含关系均未证明）

八、并行计算复杂性

8.1 PRAM 模型

PRAM（Parallel Random Access Machine）：

无限大共享存储器（处理器间交换数据）
有限或无限个（n 的多项式个）功能相同的处理器
相同指令集：逻辑、算术、内存访问、I/O、转移
每条指令执行时间相同，与处理器个数无关

8.2 并行复杂性分类

类别	定义
并行可解	多项式时间 + 多项式个处理器
高度并行可解	log n 的多项式时间 + 多项式个处理器
固有顺序的	并行可解但不是高度并行可解的

8.3 NC 类

NCᵏ：PRAM 模型，O(logᵏn) 时间 + n^O(1) 个处理器可解的判定问题类
NC：∪ₖ NCₖ（所有 NCᵏ 的并集）

NC 由 Nick Pippenger 于 1978 年提出，Cook 后来命名。

基本关系：NC ⊆ P

8.4 P 完全性

NC-多一归约：多一归约函数 f 的计算时间是 O(log^O(1)n)（PRAM 模型），记作 π₁ ∝m^NC π₂。

P 完全问题：设 π ∈ P，若对任意 π’ ∈ P 都存在 NC 多一归约使得 π’ ∝m^NC π，则称 π 是 P 完全的。

定理：如果任何 P 完全问题属于 NC，则 NC = P。

P 完全问题是 P 类中”最难的”问题，最不可能高度并行化。

8.5 生成问题（Generability）——经典 P 完全问题

实例：集合 X，X 上的二元运算 •，X 的子集 T，X 中的元素 x 问：x 是否属于 T 关于 • 运算的闭包？

闭包算法：

T' ← T
while T' ≠ T' ∪ T'•T':
    T' = T' ∪ T'•T'
closure(T) ← T'

其中 T’•T’ = {a•b | a, b ∈ T’}。

复杂度：While 循环不超过 |X−T| 次（每次至少增加 1 个元素），因此生成问题属于 P。

生成问题是经典的 P 完全问题（证明省略）。

九、算法与复杂性研究方向

9.1 算法方向

概率算法：利用随机性提高效率
近似算法：NP-hard 问题的近似最优解
在线算法：输入逐步到达时的决策
分布式算法：多节点协同计算

9.2 复杂性理论方向

概率复杂性：概率图灵机模型下的复杂性类
可近似性：哪些问题可以高效近似，哪些不能（APX-hard）
参数化复杂性：固定参数时的可处理性（FPT 理论）

核心要点总结

Turing 机是计算复杂性的理论基础，多带与单带可相互模拟但时间有损失（T(n) → O(T(n)logT(n))）
P vs NP是计算机科学最核心的开放问题，NP 完全性理论提供了”问题难度等价”的证明框架
Cook 定理（SAT ∈ NPC）是整个 NP 完全性理论的基石
六个基本 NPC 问题（3SAT/3DM/VC/团/HC/均分）构成证明其他问题 NPC 的”工具箱”
NP-hard 概念将难解性从判定问题扩展到搜索/优化问题；NP 等价问题的优化版和判定版难度相当
Turing 归约比多项式变换更通用，用于比较搜索问题的难度
P 完全性刻画了”固有顺序”的问题——即使有再多处理器也无法大幅加速
复杂性类谱系：NC ⊆ P ⊆ NP ⊆ PSPACE，各层之间的真包含关系大多仍为开放问题

知识库

探索

算法分析与设计-第10讲-计算复杂性理论