计算理论全景：从渐近记号到 NP 完全性

发表于 2026-01-02 更新于 2026-03-03 分类于 CS-Fundamentals

计算理论研究的是”什么是可计算的”以及”计算的代价是多少”。这两个问题看似简单，却奠定了现代密码学、算法设计和人工智能可信性的数学基础。本文整理了从渐近记号出发，贯穿形式语言、图灵机模型、不可判定性，直到 P vs NP 的完整知识框架。

一、渐近记号：精确刻画增长率

在分析算法时，我们关心的不是具体运行时间，而是输入规模 $n$ 趋于无穷时函数的增长行为。渐近记号体系为此提供了精确的语言。

1.1 核心定义

大 O 记号（上界）： $f = O(g)$ 当且仅当

$$(\exists c > 0)(\exists N)(\forall x \ge N);|f(x)| \le c \cdot |g(x)|$$

即对充分大的 $x$，$f$ 至多以 $g$ 的常数倍增长。

小 o 记号（严格上界）： $f(x) = o(g(x))$ 当且仅当

$$
\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0
$$

例如 $2n = o(n^2)$，但 $2n \ne o(n)$。

$\Omega$ 记号（下界）： $f = \Omega(g)$ 当且仅当 $g = O(f)$，即 $f$ 至少以 $g$ 的常数倍增长。

$\Theta$ 记号（精确界）： $f = \Theta(g)$ 当且仅当 $f = O(g)$ 且 $f = \Omega(g)$，记作 $f \sim g$。

$\tilde{O}$ 记号（忽略对数因子）： $f(x) = \tilde{O}(g(x))$ 当且仅当存在常数 $c$ 使得 $|f(x)| \le (\log n)^c |g(x)|$。”拟线性时间”即 $\tilde{O}(n)$，例如 $O(n \log n)$。

1.2 复杂度类速查

记号	含义
$O(1)$	常数时间
$O(\log n)$	对数时间
$O(n)$	线性时间
$O(n \log n)$	拟线性（即 $\tilde{O}(n)$）
$O(n^2)$	二次时间
$O(n^c)$	多项式时间，记作 $\text{poly}(n)$
$2^{O(\log n)}$	拟多项式时间
$O(c^n)$	指数时间

1.3 重要示例

调和级数满足 $1 + \frac{1}{2} + \dots + \frac{1}{n} = \ln n + O(1)$，可通过比较积分 $\int_1^n \frac{1}{x} dx$ 几何理解。

乘法的封闭性：若 $f_1 = O(g_1)$ 且 $f_2 = O(g_2)$，则 $f_1 f_2 = O(g_1 g_2)$。加法封闭：$f_1 + f_2 = O(\max(g_1, g_2))$。

二、形式语言与自动机理论

2.1 基础概念

字母表 $\Sigma$ 是符号的有限集合，其上的字符串是有限符号序列，空字符串记 $\epsilon$。

$$
\Sigma^* = {\epsilon} \cup \Sigma \cup \Sigma^2 \cup \dots
$$

语言 $L \subseteq \Sigma^$ 是字符串的集合。语言支持布尔运算（并、交、补）、连接运算 $L_1 L_2 = {xy \mid x \in L_1, y \in L_2}$ 以及*克林闭包 $L^* = {w_1 \dots w_k \mid k \ge 0, w_i \in L}$。

2.2 确定性有限自动机（DFA）

DFA 是五元组 $(Q, \Sigma, \delta, q_0, F)$，其中 $Q$ 是有限状态集，$\delta: Q \times \Sigma \to Q$ 是确定性转移函数，$q_0$ 是起始状态，$F \subseteq Q$ 是接受状态集。

机器接受字符串 $w = w_1 \dots w_n$ 当且仅当存在状态序列 $r_0, r_1, \dots, r_n$ 满足：$r_0 = q_0$，$\delta(r_i, w_{i+1}) = r_{i+1}$，且 $r_n \in F$。

经典例子：识别二进制表示中被 3 整除的整数。三个状态 $q_0, q_1, q_2$ 分别表示当前数模 3 余 0、1、2，转移规则为读入比特 $a$ 后余数变为 $2r + a \pmod{3}$。

正则语言：某个 DFA 识别的语言。正则语言族在补运算、并运算、交运算下均封闭（后者通过乘积构造证明）。

2.3 非确定性有限自动机（NFA）与子集构造

NFA 的转移函数为 $\delta: Q \times \Sigma_\epsilon \to P(Q)$，允许 $\epsilon$-转移（无需消耗输入）。机器接受字符串当且仅当计算树中存在至少一条路径到达接受状态。

定理（等价性）：每个 NFA 都有等价的 DFA。构造方法——幂集构造法：令 DFA 的状态为 NFA 状态集的子集，$Q’ = P(Q)$，转移时取 $\epsilon$-闭包。由此推论：语言是正则的当且仅当某个 NFA 识别它。

正则语言对连接运算与克林闭包同样封闭，可通过 NFA 构造（$\epsilon$-转移串联）证明。

2.4 正则表达式

正则表达式由原子（$a \in \Sigma$、$\epsilon$、$\emptyset$）及并、连接、$*$ 三种运算归纳定义。

定理：语言是正则语言当且仅当某个正则表达式描述它。从正则表达式到 NFA 的转换是构造性的；反向（DFA 转正则表达式）通过广义非确定性有限自动机（GNFA）逐步消去中间节点，每次消去状态 $q_{rip}$ 时更新转移标记：

$$R_{\text{new}} = R_{i,j} \cup (R_{i,\text{rip}}) (R_{\text{rip},\text{rip}})^* (R_{\text{rip},j})$$

2.5 非正则语言与泵引理

正则语言的存在基于有限状态机，这天生限制了它能处理的语言范畴。

泵引理：若 $L$ 是正则语言，则存在泵长度 $p$ 使得任意 $|s| \ge p$ 的 $s \in L$ 均可分解为 $xyz$，满足：(1) 对所有 $i \ge 0$，$xy^iz \in L$；(2) $|y| > 0$；(3) $|xy| \le p$。

经典反例：${0^n 1^n \mid n \ge 0}$ 不是正则语言。取 $s = 0^p 1^p$，$xy$ 部分必全为 0，泵送 $y$ 后 0 的数量多于 1，矛盾。

三、图灵机：计算能力的极限模型

3.1 形式定义

图灵机是七元组 $(Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$，其转移函数 $\delta: Q \times \Gamma \to Q \times \Gamma \times {L, R}$ 描述”读-写-移”三件事。若机器对所有输入停机并正确分类，则称它判定该语言；若它接受所有属于该语言的字符串（但不保证对不属于该语言的输入停机），则称它识别该语言。

图灵可识别的语言包含所有可判定语言，但反之不成立（停机问题 $L_{\text{HALT}}$ 是可识别而不可判定的典型例子）。

3.2 等价变体

图灵机的多种变体在计算能力上等价，但时间开销存在差异：

多带图灵机：$k$ 带机可被单带机以 $O(T(n)^2)$ 代价模拟（分隔符 # 串联带子内容）。
RAM 图灵机：支持随机访问存储，可模拟 x86-64 汇编的 MOV/ADD/JMP 等指令，能被多带机以 $O(T(n)^3)$ 代价模拟，构成”强丘奇-图灵论题”的形式支撑。

丘奇-图灵论题（弱形式）：任何物理上可计算的函数均可被图灵机计算。强形式进一步声明代价至多相差多项式——量子计算被认为是最重要的潜在例外（Shor 算法）。

3.3 通用图灵机（UTM）

存在一台三带 UTM $U$，使得 $U(\alpha, x) = M_\alpha(x)$，其中 $\alpha$ 是图灵机 $M$ 的编码。若 $M_\alpha$ 在 $T$ 步内停机，则 $U$ 在 $O(T \log T)$ 步内停机（Hennie-Stearns 模拟，利用分区/倍增技巧降低带子移动代价）。UTM 的存在说明程序本质上也是数据，这是现代可编程计算机架构的理论基础。

四、不可判定性：计算的边界

4.1 停机问题

$$L_{\text{HALT}} = {(\alpha, x) : M_\alpha \text{ 在输入 } x \text{ 上停机}}$$

$L_{\text{HALT}}$ 不可判定——证明采用对角化（自引用矛盾）：假设存在判定器 $M_{\text{HALT}}$，构造机器 $M_{\text{flip}}$，在输入 $\alpha$ 上若 $M_{\text{HALT}}(\alpha, \alpha)$ 回答”停机”则死循环，否则停机。考虑 $M_{\text{flip}}$ 以自身编码 $\beta$ 为输入，两种情况均产生矛盾。

这一证明结构揭示：语言的数量（${0,1}^*$ 的幂集）是不可数的，而图灵机的数量是可数的，因此几乎所有语言都不可判定。

4.2 莱斯定理（Rice’s Theorem）

图灵机识别语言的任何非平凡性质都是不可判定的。

形式化：设 $P$ 是图灵可识别语言的一个非平凡性质（$P \ne \emptyset$ 且 $P \ne \Sigma^*$），则 ${\alpha : L(M_\alpha) \in P}$ 不可判定。

证明通过将 $L_{\text{accept}}$ 归约到判定 $P$ 来完成：给定 $(\alpha, x)$，构造机器 $M_\gamma$（先模拟 $M_\alpha$ 接受 $x$，再模拟具有性质 $P$ 的参考机器 $M_\beta$）。若 $M_\alpha$ 接受 $x$ 则 $L(M_\gamma) = L(M_\beta) \in P$，否则 $L(M_\gamma) = \emptyset \notin P$。莱斯定理说明我们永远无法写出一个通用的程序分析工具来判定代码的任意非平凡语义性质，这是静态分析领域的根本局限。

4.3 波斯特对应问题（PCP）

PCP 问题：给定多米诺骨牌集合 ${[t_i / b_i]}$，是否存在序列 $i_1, \dots, i_m$ 使得 $t_{i_1} \dots t_{i_m} = b_{i_1} \dots b_{i_m}$？

PCP 不可判定（Post 1946）——构造从 $L_{\text{accept}}$ 到 PCP 的归约，用骨牌编码图灵机的运行历史（初始格局、转移规则、接受格局），使得存在匹配当且仅当机器接受输入。

4.4 哥德尔不完备性定理

任何包含皮亚诺算术的一致形式系统都存在不可判定命题。证明的核心是将 PCP 的不可判定性（更深层是 $L_{\text{accept}}$）算术化：利用哥德尔 $\beta$-函数（基于中国剩余定理）将有限序列编码为自然数，在算术语言中表达”存在匹配序列”。若系统完备，则可判定 PCP，矛盾。

五、计算复杂性：时间与空间的代价

5.1 P 类

$$P = \bigcup_{k \ge 1} \text{DTIME}(n^k)$$

P 类是”高效可解”问题的数学抽象。多项式在加法、乘法、复合下封闭，因此 P 类对算法组合是稳健的。代表性高效算法：BFS/DFS（$O(|V|+|E|)$）、Dijkstra（$\tilde{O}(n)$）、最大流的近线性算法（Chen et al. 2022：$O(E^{1+o(1)})$）。

线性规划（LP）的历史清晰反映了复杂度的进展：单纯形法最坏情况指数、椭球法 $O(m^4 L)$（首个多项式时间）、内点法 $O(m^{3.5} L)$，直至随机化内点法 $\tilde{O}(m^\omega)$（$\omega < 2.37$）。

5.2 NP 类与两种等价视角

$$NP = \bigcup_{c \ge 1} \text{NTIME}(n^c)$$

视角一（求解）：NP 是非确定性图灵机（NTM）在多项式时间内可求解的问题集合。NTM 的每步可有多个分支选择，只要存在一条接受路径即接受。

视角二（验证）：NP 等价于”有多项式长度证书可在多项式时间内验证”的问题集合。

形式化（定理 5.16）：$L \in NP$ 当且仅当存在多项式时间验证器 $M$ 满足：

完备性：若 $x \in L$，则存在证书 $w$ 使 $M(x, w) = 1$；
可靠性：若 $x \notin L$，则对所有 $w$ 均有 $M(x, w) = 0$。

5.3 NP 完全性与 Cook-Levin 定理

NP-Hard：问题 $L$ 是 NP-Hard 当且仅当每个 NP 问题都可多项式时间归约到 $L$。

NP-Complete (NPC)：$L \in NP$ 且 $L$ 是 NP-Hard。

定理（Cook-Levin）：SAT 是 NP-Complete。

SAT 是 NP 的经典”完全证明方法使用计算快照（Tableau）”：将 NTM 的 $T(n) \times T(n)$ 计算历史用布尔变量编码，添加唯一性约束、初始化约束、转移规则约束和接受约束，总公式大小 $O(T(n)^2)$（多项式）。

从 SAT 出发，通过归约树可证明大量问题的 NP 完全性：

SAT → 3SAT → INDSET → CLIQUE
                    → VERTEX-COVER
          → HAM-PATH → TSP
          → SUBSET SUM → PARTITION
          → INTEGER PROGRAMMING

3SAT $\le_p$ INDSET 的 Gadget 构造：对每个子句创建一个三角形（内部节点两两相连），子句间互斥的文字对连冲突边。大小为 $m$（子句数量）的独立集存在当且仅当 3CNF 可满足。

INDSET $\le_p$ CLIQUE：利用补图，独立集与补图中的团一一对应。

dHAMPATH $\le_p$ HAMPATH：节点分裂技巧将有向约束嵌入无向图。

对于整数分解（给定 $N$，是否存在因子 $d \in [L, R]$），目前认为属于 $NP \cap coNP$ 但不是 NPC，量子计算机上可用 Shor 算法多项式时间求解——这是 RSA 加密体系的安全性假设。

5.4 时间层级定理与 Ladner 定理

时间层级定理：若 $f(n) \log f(n) = o(g(n))$，则 $\text{DTIME}(f(n)) \subsetneq \text{DTIME}(g(n))$——更多时间确实能解更多问题。直接推论：$P \subsetneq EXP$。

Ladner 定理：若 $P \ne NP$，则存在 NP 中既不属于 P 也不属于 NPC 的语言（NP-Intermediate）。图同构和整数分解是主流候选者。

5.5 空间复杂性

$$L = \text{SPACE}(\log n), \quad NL = \text{NSPACE}(\log n), \quad PSPACE = \bigcup_k \text{SPACE}(n^k)$$

Savitch 定理：$\text{NSPACE}(S(n)) \subseteq \text{SPACE}(S(n)^2)$，即 $PSPACE = NPSPACE$。证明通过递归地解决”是否存在路径从格局 $C$ 到 $C’$ 长度 $\le 2^i$”，每层仅存储中间节点，总空间 $O(S(n)) \times O(S(n)) = O(S(n)^2)$。

TQBF（真量化布尔公式）是 PSPACE-Complete，可视为两方博弈：存在玩家选择 $\exists$ 变量，全称玩家选择 $\forall$ 变量，代表广义棋盘游戏的难度下界。

5.6 层级关系全景

$$L \subseteq NL \subseteq P \subseteq NP \subseteq PSPACE \subseteq EXP \subseteq EXPSPACE$$

其中 $P \ne EXP$ 已证（时间层级定理），$P \ne PSPACE$ 已证（空间层级定理间接）。最核心的开放问题：

$P \stackrel{?}{=} NP$（千禧年问题之一）
$P \stackrel{?}{=} BPP$（确定性 vs 随机化多项式时间）
$NL \stackrel{?}{=} P$（对数空间非确定性 vs 多项式时间确定性）

若 $P = NP$，则密码学中的单向函数不存在，现代公钥体系（RSA、椭圆曲线）将全面崩溃。