Fingerprinting

从确定性到随机性

在经典算法设计中，我们习惯于追求确定性的正确答案。然而，许多看似简单的问题在确定性框架下却有着不可逾越的复杂度下界。随机化为我们提供了突破这些下界的可能——只要允许极小的错误概率，就能获得确定性算法无法企及的效率。

本讲的核心概念是 fingerprinting（指纹技术），一种贯穿随机算法设计的基本范式。

什么是 Fingerprinting

Fingerprinting 的核心思想是：不直接比较两个庞大的对象，而是将它们映射为短小的「指纹」，通过比较指纹来间接判断相等性。

Fingerprinting 的形式化定义

一个 fingerprinting 方案是一个（随机化的）函数 $\text{FING}\colon \mathcal{U} \to \mathcal{V}$，其中 $|\mathcal{V}| \ll |\mathcal{U}|$，满足：

1. 无假阴性：$a = b \implies \text{FING}(a) = \text{FING}(b)$（确定性保证）
2. 假阳性概率小：$a \neq b \implies \Pr[\text{FING}(a) = \text{FING}(b)]$ 很小
3. 指纹短小：$\text{FING}(a)$ 的表示长度远小于 $a$ 本身

性质 1 保证了单边错误（one-sided error）：当算法判定「不等」时一定正确，只在判定「相等」时可能犯错（假阳性）。

这一思想贯穿本讲所有内容——从多项式恒等检验、通信复杂性中的相等性问题，到矩阵乘法验证和字符串匹配，fingerprinting 都扮演着关键角色。

多项式恒等检验

问题定义

多项式恒等检验（Polynomial Identity Testing, PIT）是代数计算中的一个基本问题：给定两个多项式 $P$ 和 $Q$（以算术电路的形式表示），判断它们是否计算同一个多项式，即 $P \equiv Q$。等价地，令 $Q = P_1 - P_2$，问题转化为判断 $Q$ 是否为零多项式。

算术电路

在 PIT 中，多项式不是以展开形式（如 $3x^2 + 2x + 1$）给出的——因为展开后可能有指数多个项，无法显式列出。多项式的输入形式是算术电路（Arithmetic Circuit），它描述的不是多项式「长什么样」，而是如何从变量和常数出发，通过一系列加、减、乘操作一步步算出它。

算术电路

算术电路是一个有向无环图（DAG），其中：

• 输入节点（叶节点）标记为变量 $x_1, x_2, \ldots$ 或常数
• 内部节点标记为 $+$、$-$ 或 $\times$ 运算
• 有一个指定的输出节点，其计算结果即为电路所表示的多项式

flowchart BT
    x1["x₁"] --> plus1["＋"]
    y1["y₁"] --> plus1
    x2["x₂"] --> plus2["＋"]
    y2["y₂"] --> plus2
    xn["xₙ"] --> plusn["＋"]
    yn["yₙ"] --> plusn
    plus1 --> mul["× · · · ×"]
    plus2 --> mul
    plusn --> mul
    mul --> out(("输出"))

    classDef var fill:#e3f2fd,stroke:#1565c0,stroke-width:2px
    classDef op fill:#fff3e0,stroke:#ef6c00,stroke-width:2px
    classDef output fill:#e8f5e8,stroke:#2e7d32,stroke-width:2px

    class x1,y1,x2,y2,xn,yn var
    class plus1,plus2,plusn,mul op
    class out output

算术电路的关键特性在于它可以指数级压缩多项式的表示。例如：

$$\prod_{i=1}^{n} (x_i + y_i)$$

这个电路的描述长度仅为 $O(n)$，但展开后有 $2^n$ 个单项式。因此，将多项式显式展开再逐项比较系数在计算上是不可行的——我们需要一种能直接在电路表示上工作的算法。

PIT 问题至今没有已知的高效确定性算法，这是计算复杂性理论中的一个重大未解问题。如果存在多项式时间的确定性 PIT 算法，则意味着 $\textsf{NEXP} \neq \textsf{P/poly}$ 或 $\#\textsf{P} \neq \textsf{FP}$——这两个都是尚未被证明的重大复杂性分离猜想。

Schwartz-Zippel 引理

PIT 有一个优雅的随机化解法，其核心是以下引理：

Schwartz-Zippel 引理

设 $Q(x_1, x_2, \ldots, x_n)$ 是域 $\mathbb{F}$ 上的一个非零多项式，总次数（total degree）为 $d$。设 $S$ 是 $\mathbb{F}$ 的一个有限子集。若 $r_1, r_2, \ldots, r_n$ 独立均匀地从 $S$ 中随机选取，则

$$\Pr[Q(r_1, r_2, \ldots, r_n) = 0] \le \frac{d}{|S|}$$

这个结论非常惊人：无论多项式有多少个变量、结构多复杂，只要在一个足够大的集合中随机取值，非零多项式求值为零的概率就很小。而且这个界只依赖于多项式的总次数和取值集合的大小，与变量个数 $n$ 完全无关。

这里需要注意总次数和个体次数（individual degree）的区别。总次数是所有单项式中变量幂次之和的最大值。例如 $x_1^2 x_2^3 + x_1 x_3^4$ 的总次数为 $\max(2+3, 1+4) = 5$。

证明

对变量个数 $n$ 进行归纳。

基础情形（$n = 1$）：单变量多项式 $Q(x_1)$ 的次数为 $d$，由代数基本定理（或更一般地，域上多项式的性质），它至多有 $d$ 个根。因此：

$$\Pr[Q(r_1) = 0] \le \frac{d}{|S|}$$

归纳步骤：假设引理对 $n-1$ 个变量成立。将 $Q$ 按 $x_1$ 的幂次展开：

$$Q(x_1, x_2, \ldots, x_n) = \sum_{i=0}^{k} x_1^i \cdot Q_i(x_2, \ldots, x_n)$$

其中 $k \le d$ 是 $x_1$ 在 $Q$ 中出现的最高次数，$Q_k(x_2, \ldots, x_n)$ 是非零多项式（作为 $x_1^k$ 的系数）。注意 $Q_k$ 的总次数至多为 $d - k$，因为 $Q$ 中包含 $x_1^k$ 的任何单项式，其余变量的次数之和至多为 $d - k$。

利用全概率公式。令事件 $A$ 为「$Q_k(r_2, \ldots, r_n) = 0$」，事件 $B$ 为「$Q(r_1, r_2, \ldots, r_n) = 0$」：

$$\Pr[B] = \Pr[B \mid A] \cdot \Pr[A] + \Pr[B \mid \bar{A}] \cdot \Pr[\bar{A}]$$

• 由归纳假设，$Q_k$ 是 $n-1$ 个变量的非零多项式，总次数 $\le d - k$，故 $\Pr[A] \le \dfrac{d - k}{|S|}$
• 当 $\bar{A}$ 发生时，即 $Q_k(r_2, \ldots, r_n) \neq 0$。此时将 $r_2, \ldots, r_n$ 的值代入，$Q(x_1, r_2, \ldots, r_n)$ 成为关于 $x_1$ 的单变量多项式，且因为 $x_1^k$ 的系数 $Q_k(r_2, \ldots, r_n) \neq 0$，它确实是一个次数为 $k$ 的非零多项式。由基础情形，$\Pr[B \mid \bar{A}] \le \dfrac{k}{|S|}$

由此：

$$\Pr[B] \le 1 \cdot \frac{d - k}{|S|} + \frac{k}{|S|} \cdot 1 = \frac{d}{|S|}$$

应用于 PIT

要检验 $Q \equiv 0$，只需从足够大的集合 $S$ 中随机选取一个点 $(r_1, \ldots, r_n)$，利用算术电路计算 $Q(r_1, \ldots, r_n)$：

• 若结果 $\neq 0$：$Q$ 一定不是零多项式（确定性结论）
• 若结果 $= 0$：$Q$ 大概率是零多项式，但有至多 $d/|S|$ 的假阳性概率

这正是 fingerprinting 的范式：$\text{FING}(Q) = Q(r_1, \ldots, r_n)$，将一个可能有指数多项的多项式压缩为一个域元素。

降低错误概率

通过独立重复 $t$ 次检验（每次独立随机选取新的取值点），错误概率降低到 $(d/|S|)^t$。选取 $|S| \ge 2d$ 即可使单次错误概率 $\le 1/2$，重复 $t$ 次后错误概率 $\le 2^{-t}$，指数级衰减。

Schwartz-Zippel 引理的应用远不止 PIT。它还可以用于判断图是否有完美匹配、验证矩阵乘法、检验有根树同构、分析 Reed-Muller 码的距离性质、构造概率可检验证明（PCP）等。本讲后续的几个应用都是它的直接推论。

通信复杂性与相等性问题

问题模型

通信复杂性（Communication Complexity）研究以下场景：Alice 持有输入 $a$，Bob 持有输入 $b$，他们需要通过通信来协作计算某个函数 $f(a, b)$。通信复杂度衡量的是完成计算所需的最小通信比特数（在最坏情况下）。

考虑最基本的相等性问题（Equality）：Alice 有一个 $n$ 比特字符串 $a \in \{0,1\}^n$，Bob 有一个 $n$ 比特字符串 $b \in \{0,1\}^n$，他们需要判断 $a = b$ 是否成立。

flowchart LR
    A["Alice<br/>持有 a ∈ {0,1}ⁿ"] -- "交换消息" --> B["Bob<br/>持有 b ∈ {0,1}ⁿ"]
    B -- "a = b?" --> C["输出"]

    classDef person fill:#e3f2fd,stroke:#1565c0,stroke-width:2px
    classDef output fill:#e8f5e8,stroke:#2e7d32,stroke-width:2px

    class A,B person
    class C output

确定性下界

在确定性协议中，相等性问题的确定性通信复杂度为 $\Theta(n)$——Alice 和 Bob 必须交换线性于 $n$ 的比特数。

直观理解：如果 Alice 发送的消息总共不到 $n$ 比特（比如只有 $k < n$ 比特），那么她的 $2^n$ 种可能输入中必有两个不同输入产生了相同的消息。对于这两个输入，Bob 收到相同的消息，无法区分它们，因此至少对其中一个给出错误答案。

这个直觉可以用组合矩形（Combinatorial Rectangle）的语言严格化。

组合矩形

想象一个 $2^n \times 2^n$ 的表格，行对应 Alice 的所有可能输入 $a$，列对应 Bob 的所有可能输入 $b$，格子 $(a, b)$ 标记为 $f(a,b)$ 的值。

确定性协议中，每个叶节点（输出节点）对应的输入集合构成一个组合矩形 $R \times C$，其中 $R \subseteq \{0,1\}^n$ 是使 Alice 到达该叶节点的输入集合，$C \subseteq \{0,1\}^n$ 是使 Bob 到达该叶节点的输入集合。

为什么是笛卡尔积的形状？因为 Alice 发送的消息只取决于她自己的输入 $a$，Bob 发送的消息也只取决于他自己的输入 $b$。如果两个不同的输入 $a_1, a_2$ 让 Alice 产生完全相同的消息序列，那么无论 Bob 的输入 $b$ 是什么，$(a_1, b)$ 和 $(a_2, b)$ 都会走到同一个叶节点——因为 Bob 看到的交互完全一样。因此到达同一叶节点的输入集合必然是 $R \times C$ 的形式。

一个正确的协议要求每个矩形内的所有输入都有相同的正确输出。

现在将这一工具应用于相等函数。所有使 $f(a,b) = 1$（即 $a = b$）的输入恰好是对角线 $\{(a,a) : a \in \{0,1\}^n\}$——共 $2^n$ 个点。关键观察：对角线上的每个组合矩形最多只包含 1 个点。

为什么？假设某个标记为「相等」的矩形 $R \times C$ 包含两个不同的对角线点 $(a_1, a_1)$ 和 $(a_2, a_2)$（$a_1 \ne a_2$）。那么 $a_1, a_2 \in R$ 且 $a_1, a_2 \in C$，由笛卡尔积的性质，$(a_1, a_2)$ 也在这个矩形中。但 $a_1 \ne a_2$，所以 $(a_1, a_2)$ 应该输出「不等」——与该矩形标记为「相等」矛盾。

因此，协议至少需要 $2^n$ 个标记为「相等」的叶节点来覆盖所有 $2^n$ 个对角线点，决策树至少有 $2^n$ 个叶节点，通信量 $\ge \log_2 2^n = n$。

随机化协议

随机化可以将通信复杂度从 $\Theta(n)$ 大幅降低到 $O(\log n)$。根据随机性是共享的还是私有的，有两种不同的协议。

公共随机协议

在公共随机（public coin）模型中，Alice 和 Bob 共享一个随机源（如一个公开的随机比特串），但各自的输入是私有的。

模运算与域

后续频繁使用 $\mathbb{Z}_p$：这是模素数 $p$ 的整数集合 $\{0, 1, \ldots, p-1\}$，加法和乘法都在模 $p$ 下进行。例如在 $\mathbb{Z}_7$ 中，$3 + 5 = 1,\, 3 \times 4 = 5$。当 $p$ 为素数时，每个非零元素都有乘法逆元，因此 $\mathbb{Z}_p$ 构成一个域（Field）——支持加减乘除。$\mathbb{Z}_p[x]$ 表示系数在 $\mathbb{Z}_p$ 中的多项式。

将 $a \in \{0,1\}^n$ 编码为多项式 $f_a(x) = \sum_{i=1}^{n} a_i \cdot x^i \in \mathbb{Z}_p[x]$，其中 $p$ 是一个公开的素数（$p = \Theta(n^2)$）。类似地，Bob 将 $b$ 编码为 $f_b(x)$。

协议：

1. Alice 和 Bob 共享随机元素 $r \in \mathbb{Z}_p$
2. Alice 计算 $f_a(r) = \sum_{i=1}^{n} a_i \cdot r^i \bmod p$，发送给 Bob
3. Bob 计算 $f_b(r) = \sum_{i=1}^{n} b_i \cdot r^i \bmod p$，检查 $f_a(r) = f_b(r)$

通信量仅为 $O(\log p) = O(\log n)$ 比特（Alice 发送一个 $\mathbb{Z}_p$ 中的元素）。

错误分析：若 $a \neq b$，则 $f_a - f_b$ 是 $\mathbb{Z}_p[x]$ 上次数 $\le n$ 的非零多项式。由 Schwartz-Zippel 引理：

$$\Pr[f_a(r) = f_b(r)] \le \frac{n}{p}$$

取 $p = \Theta(n^2)$，错误概率 $\le 1/n$。

另一种更极端的公共随机协议只需 1 比特通信：Alice 和 Bob 共享随机向量 $\bm{r} \in \{0,1\}^n$，Alice 发送 $\langle a, \bm{r} \rangle \bmod 2$（内积模 2），Bob 检查是否等于 $\langle b, \bm{r} \rangle \bmod 2$。若 $a \neq b$，则 $\langle a - b, \bm{r} \rangle \bmod 2$ 是一个关于 $\bm{r}$ 的非零线性多项式（因为 $a - b$ 有某个分量非零），由 Schwartz-Zippel 引理（$d = 1,\, |S| = 2$），碰撞概率 $\le 1/2$。单次错误概率较高，但重复几十次即可将错误概率降到任意小。

这里的 fingerprint 是 $\text{FING}(a) = f_a(r) = \sum a_i \cdot r^i \bmod p$——将 $n$ 比特的字符串压缩为一个 $O(\log n)$ 比特的域元素。

私有随机协议

在私有随机（private coin）模型中，Alice 和 Bob 各自拥有独立的随机源，不共享随机性。

将 $a, b \in \{0,1\}^n$ 视为 $[0, 2^n)$ 中的整数。

协议：

1. Alice 从不超过 $k$ 的素数中均匀随机选取一个素数 $p$（$k$ 待定）
2. Alice 将 $(p, \, a \bmod p)$ 发送给 Bob
3. Bob 检查 $a \bmod p \equiv b \bmod p$，输出结果

通信量为 $O(\log k) = O(\log n)$ 比特。这里的 fingerprint 是 $\text{FING}_p(a) = a \bmod p$。

私有随机协议的错误分析

• 若 $a = b$，则 $a \bmod p = b \bmod p$ 一定成立，不会产生假阴性。
• 若 $a \neq b$，令 $z = |a - b|$，则 $0 < z < 2^n$。假阳性发生当且仅当 $p \mid z$。我们需要估计随机素数 $p$ 整除 $z$ 的概率。

关键观察：$z$ 的不同素因子个数是有限的。由于 $z < 2^n$，而最小的 $n$ 个素数的乘积满足 $2 \times 3 \times 5 \times \cdots \times p_n \ge 2^n$（素数阶乘 primorial 的增长速度），若 $z$ 有 $n$ 个或更多不同素因子，则 $z$ 至少等于前 $n$ 个素数之积，即 $z \ge 2^n$，与 $z < 2^n$ 矛盾。因此 $z$ 至多有 $n - 1$ 个不同的素因子。

素数计数函数与素数定理

由素数定理（Prime Number Theorem），不超过 $N$ 的素数个数满足

$$\pi(N) \sim \frac{N}{\ln N} \quad (N \to \infty)$$

这意味着 $[1, k]$ 范围内约有 $\dfrac{k}{\ln k}$ 个素数。

对于我们的分析，更有用的一个推论是：对于足够大的 $N$，$\pi(N) \ge \dfrac{N}{2\ln N}$。

错误概率为：

$$\Pr[\text{error}] = \frac{\#\{p \le k : p \text{ 是素数且 } p \mid z\}}{\pi(k)} \le \frac{n - 1}{\pi(k)} \approx \frac{n \ln k}{k}$$

选取 $k = n^3$：

$$\Pr[\text{error}] \le \frac{n \cdot 3\ln n}{n^3} = \frac{3\ln n}{n^2} = O\left(\frac{1}{n}\right)$$

注意 fingerprint 函数 $\text{FING}_p(a) = a \bmod p$ 是一个随机化的映射——随机性来自素数 $p$ 的选择。两种协议使用了不同的 fingerprinting 方案：公共随机协议基于多项式求值和 Schwartz-Zippel 引理，私有随机协议基于模运算和素数定理，但它们的共同点是将 $n$ 比特的信息压缩为 $O(\log n)$ 比特的指纹。

Newman 定理

Newman 定理

公共随机和私有随机两种模型的通信复杂度之间有什么关系？显然私有随机不弱于公共随机（后者可以模拟前者），因为若有一个 private-coin 协议 $\Pi$，其中 Alice 和 Bob 分别使用独立随机串 $R_{A}, R_{B}$，那么构造 public-coin 协议 $\Pi'$：

• 取公共随机串 $R=\left(R_{A}, R_{B}\right)$
• Alice 在 $\Pi'$ 中把 $R_{A}$ 当作自己原来的私有随机性
• Bob 在 $\Pi'$ 中把 $R_{B}$ 当作自己原来的私有随机性

则 $\Pi'$ 对任意输入 $(x, y)$ 的行为分布与 $\Pi$ 相同。因此

$$R^{\mathrm{pub}}(f) \le R^{\mathrm{priv}}(f)$$

即 public-coin 的随机通信复杂度不大于 private-coin。

但反过来呢？

Newman 定理

对于任意函数 $f$，令 $R^{\text{pub}}_\epsilon(f)$ 和 $R^{\text{priv}}_\epsilon(f)$ 分别表示错误概率至多为 $\epsilon$ 的公共随机和私有随机通信复杂度。则：

$$R^{\text{priv}}_\epsilon(f) \le R^{\text{pub}}_\epsilon(f) + O(\log n)$$

Newman 定理告诉我们，私有随机最多比公共随机多 $O(\log n)$ 的通信量。

其证明思想如下：假设已有一个公共随机协议 $\Pi$，使用公共随机串 $s$，错误概率 $\le \epsilon$。虽然可能的随机串有指数多个，但我们并不需要所有的——只需从中挑选出 $t = \text{poly}(n)$ 个「有代表性的」随机串 $s_1, \ldots, s_t$ 即可。通过概率论中的抽样论证，可以证明随机选取 $t$ 个串后，对所有输入对 $(a,b)$ 的平均错误率与使用全部随机串时接近。

有了这组串，Alice 和 Bob 事先约定好 $s_1, \ldots, s_t$（这不需要通信，因为是协议的一部分）。协议开始时，Alice 用私有随机性选取 $i \in [t]$，将 $i$ 发送给 Bob（需要 $\lceil \log_2 t \rceil = O(\log n)$ 比特），双方随后使用 $s_i$ 执行原协议。额外通信开销仅为 $O(\log n)$。

对于相等性问题，两种模型的通信复杂度都是 $\Theta(\log n)$，差距在常数因子内。

应用：二部图完美匹配

问题与经典方法

给定一个二部图（Bipartite Graph）$G = (U, V, E)$，其中 $|U| = |V| = n$，判断 $G$ 是否存在完美匹配（Perfect Matching），即一个边集 $M \subseteq E$，使得 $U$ 和 $V$ 中的每个顶点都恰好被 $M$ 中的一条边覆盖。

二部图与完美匹配

二部图是指顶点可以分成两组 $U$ 和 $V$，且所有边都跨组连接（组内没有边）的图。完美匹配是一种配对方案：将 $U$ 中每个顶点恰好与 $V$ 中一个顶点配对，且每个顶点恰好被配对一次（要求 $|U| = |V|$）。

一个直观例子：$n$ 个学生和 $n$ 门课程，每个学生只对部分课程感兴趣（用边表示）。完美匹配就是给每个学生恰好分配一门他感兴趣的课，且每门课恰好分配给一个学生。不是所有二部图都有完美匹配——可能有些学生竞争同一门课，导致无法全部满足。

经典的确定性算法基于增广路径（从一个未匹配的顶点出发，沿交替使用匹配边和非匹配边的路径扩展当前匹配）：如 Hopcroft-Karp 算法，时间复杂度为 $O(m\sqrt{n})$，其中 $m = |E|$。利用 fingerprinting 和代数方法，可以得到一个截然不同的随机判定算法。

Edmonds 定理与 Edmonds 矩阵

Edmonds 定理（Edmonds' Theorem）建立了图的匹配与矩阵行列式之间的深刻联系，将组合问题转化为代数问题。

定义二部图 $G$ 的 Edmonds 矩阵 $\bm{M}$ 为 $n \times n$ 矩阵，其中每条边对应一个独立的形式变量：

$$M_{ij} = \begin{cases} x_{ij} & \text{if } (u_i, v_j) \in E \\ 0 & \text{otherwise} \end{cases}$$

其中 $\{x_{ij}\}$ 是相互独立的形式变量（indeterminates）——它们不是具体的数值，而是纯粹的符号占位符。可以把每个 $x_{ij}$ 理解为边 $(u_i, v_j)$ 的「标签」：行列式 $\det(\bm{M})$ 就成为一个关于这些标签的多项式。使用形式变量而非具体数值，是为了让不同的边保持可区分——这样不同匹配对应的乘积项涉及不同的变量组合，彼此不会相消。后面的随机算法就是给这些变量随机赋值，然后利用 Schwartz-Zippel 引理检验行列式是否恒为零。

具体例子

考虑一个 $3 \times 3$ 的二部图，$U = \{u_1, u_2, u_3\},\, V = \{v_1, v_2, v_3\}$，边集 $E = \{(u_1,v_1), (u_1,v_2), (u_2,v_1), (u_2,v_3), (u_3,v_2), (u_3,v_3)\}$。Edmonds 矩阵为：

$$\bm{M} = \begin{pmatrix} x_{11} & x_{12} & 0 \\ x_{21} & 0 & x_{23} \\ 0 & x_{32} & x_{33} \end{pmatrix}$$

行列式展开后，6 个排列中只有对应完美匹配的排列贡献非零项。例如排列 $\sigma = (1,2,3)$（恒等排列）对应匹配 $\{(u_1,v_1),(u_2,v_2),(u_3,v_3)\}$，但 $M_{2,2} = 0$，所以这个排列贡献为零。排列 $\sigma = (1,3,2)$ 对应 $\{(u_1,v_1),(u_2,v_3),(u_3,v_2)\}$，所有边都存在，贡献 $-x_{11}x_{23}x_{32}$。排列 $\sigma = (2,1,3)$ 对应 $\{(u_1,v_2),(u_2,v_1),(u_3,v_3)\}$，贡献 $-x_{12}x_{21}x_{33}$。因此 $\det(\bm{M}) = -x_{11}x_{23}x_{32} - x_{12}x_{21}x_{33} \not\equiv 0$，说明该图有完美匹配。

对于一般图（非二部图），对应的概念是 Tutte 矩阵，定义为反对称矩阵：

$$T_{ij} = \begin{cases} x_{ij} & \text{if } (i,j) \in E \text{ and } i < j \\ -x_{ij} & \text{if } (i,j) \in E \text{ and } i > j \\ 0 & \text{if } (i,j) \notin E \text{ or } i = j \end{cases}$$

Edmonds 矩阵可以看作 Tutte 矩阵在二部图上的简化版本。Edmonds 定理同样适用于一般图：$G$ 有完美匹配当且仅当其 Tutte 矩阵的行列式（作为形式变量的多项式）不恒为零。

Edmonds 定理

二部图 $G$ 存在完美匹配，当且仅当 $\det(\bm{M})$ 作为 $\{x_{ij}\}$ 的多项式不恒为零。

为什么 Edmonds 定理成立

行列式的定义为：

$$\det(\bm{M}) = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) \prod_{i=1}^{n} M_{i,\sigma(i)}$$

其中求和遍历所有 $n!$ 个排列 $\sigma \in S_n$，$\operatorname{sgn}(\sigma) \in \{+1, -1\}$ 是排列的符号（偶排列取 $+1$，奇排列取 $-1$）。每个排列 $\sigma$ 对应 $U$ 到 $V$ 的一个一一映射：将 $u_i$ 映射到 $v_{\sigma(i)}$。

乘积 $\prod_{i=1}^{n} M_{i,\sigma(i)}$ 非零当且仅当对所有 $i$ 都有 $(u_i, v_{\sigma(i)}) \in E$，即 $\{(u_i, v_{\sigma(i)}) : i = 1, \ldots, n\}$ 构成 $G$ 的一个完美匹配。

• 若 $G$ 没有完美匹配，则行列式中每一项的乘积都包含至少一个零因子，故 $\det(\bm{M}) \equiv 0$
• 若 $G$ 有完美匹配 $\sigma^*$，则对应项 $\operatorname{sgn}(\sigma^*) \prod_{i} x_{i,\sigma^*(i)}$ 是一个非零的单项式。关键在于，由于各 $x_{ij}$ 是独立的形式变量，不同匹配对应的单项式一定不同（因为它们涉及不同的变量子集），所以非零项之间不会相消，$\det(\bm{M})$ 作为多项式不恒为零

随机算法

Edmonds 定理将完美匹配的存在性归结为多项式是否恒为零，而这正是 PIT 问题。结合 Schwartz-Zippel 引理，得到如下算法：

1. 将每个形式变量 $x_{ij}$ 独立均匀地替换为 $S = \{1, 2, \ldots, 2n\}$ 中的随机值
2. 计算数值矩阵的行列式（高斯消元 $O(n^3)$，或利用矩阵乘法算法 $O(n^\omega)$）
3. 若行列式为 $0$，输出「无完美匹配」；否则输出「有完美匹配」

$\det(\bm{M})$ 的总次数为 $n$（每个乘积项恰好是 $n$ 个变量之积），取 $|S| = 2n$。由 Schwartz-Zippel 引理，当存在完美匹配时，随机赋值后行列式恰好为零的概率 $\le n/(2n) = 1/2$。

这个算法虽然在判定问题上并不比 Hopcroft-Karp 更快，但它揭示了匹配问题与线性代数之间的深刻联系。更重要的是，这一代数方法可以推广到并行算法：计算行列式可以高效并行化（属于复杂性类 $\textsf{NC}$，即可以用多项式个处理器在 $O(\operatorname{polylog} n)$ 即 $O\left((\log n)^k\right)$ 时间内完成），因此二部图完美匹配判定也可以随机并行化（属于 $\textsf{RNC}$）——这是经典增广路径方法难以达到的。

一个至今未解的问题是：完美匹配判定是否可以确定性并行化（即属于 $\textsf{NC}$）？目前只知道它在 $\textsf{RNC}$ 中，去随机化仍然是一个重大挑战。

应用：矩阵乘法验证

问题背景

给定三个 $n \times n$ 矩阵 $\bm{A}, \bm{B}, \bm{C}$，判断是否 $\bm{A}\bm{B} = \bm{C}$。

直接计算 $\bm{A}\bm{B}$ 再逐项比较需要矩阵乘法的时间。令 $\omega$ 为矩阵乘法指数，即 $n \times n$ 矩阵乘法的最优时间复杂度为 $O(n^\omega)$。长期以来，降低 $\omega$ 的上界是算法理论的核心课题之一：

年份	作者	$\omega$ 上界
-	朴素算法	$3$
1969	Strassen	$2.807$
…	…	…
2024	Williams, Xu, Xu, Zhou	$2.3716$

目前 $\omega > 2$ 仍然成立。长期以来广泛猜想 $\omega = 2$，但近年来也有研究者开始质疑这一猜想。无论如何，验证 $\bm{AB} = \bm{C}$ 似乎理应比计算 $\bm{AB}$ 更容易——事实上，Freivalds 给出了一个 $O(n^2)$ 的随机验证算法。

Freivalds 算法

Freivalds 算法的核心思想是对矩阵做 fingerprinting：$\text{FING}(\bm{M}) = \bm{M}\bm{r}$，将一个 $n \times n$ 的矩阵压缩为一个 $n$ 维向量。

1. 随机选取向量 $\bm{r} \in \{0,1\}^n$，每个分量独立均匀地取 $0$ 或 $1$
2. 计算 $\bm{A}(\bm{B}\bm{r})$ 和 $\bm{C}\bm{r}$
3. 若 $\bm{A}(\bm{B}\bm{r}) \neq \bm{C}\bm{r}$，输出「$\bm{AB} \neq \bm{C}$」；否则输出「$\bm{AB} = \bm{C}$」

计算顺序

步骤 2 中必须先计算 $\bm{B}\bm{r}$（矩阵乘向量，$O(n^2)$），再计算 $\bm{A}$ 乘以结果（又一次矩阵乘向量，$O(n^2)$）。若直接计算 $(\bm{A}\bm{B})\bm{r}$，则 $\bm{A}\bm{B}$ 本身就是矩阵乘法，退化为 $O(n^\omega)$。总计算量为 $O(n^2)$。

正确性分析

令 $\bm{D} = \bm{AB} - \bm{C}$。算法检验的等价条件是 $\bm{D}\bm{r} = \bm{0}$。

若 $\bm{D} = \bm{0}$（即 $\bm{AB} = \bm{C}$），则 $\bm{D}\bm{r} = \bm{0}$ 恒成立，算法不会出错。

若 $\bm{D} \neq \bm{0}$，我们需要证明 $\Pr[\bm{D}\bm{r} = \bm{0}] \le 1/2$。

由于 $\bm{D} \neq \bm{0}$，存在某个非零行，不妨设第 $i$ 行 $\bm{d}_i \neq \bm{0}$，且 $d_{ij} \neq 0$。考虑 $(\bm{D}\bm{r})_i$：

$$(\bm{D}\bm{r})_i = \sum_{k=1}^{n} d_{ik} r_k = d_{ij} r_j + \underbrace{\sum_{k \neq j} d_{ik} r_k}_{\coloneqq\, W}$$

这里使用了延迟决策原则（Principle of Deferred Decisions）：我们可以假设先确定所有 $r_k$（$k \neq j$）的值，再考虑 $r_j$ 的选择。一旦 $r_k$（$k \neq j$）固定，$W$ 就成为一个确定的常数，于是：

$$(\bm{D}\bm{r})_i = 0 \iff r_j = -\frac{W}{d_{ij}}$$

无论 $W$ 的值是什么，$(\bm{D}\bm{r})_i = 0$ 等价于 $d_{ij} r_j + W = 0$，即 $r_j$ 必须取某个特定值。而 $r_j$ 在 $\{0,1\}$ 上均匀分布且独立于其他 $r_k$，$\{0,1\}$ 只有两个元素，所以 $r_j$ 恰好命中那个特定值的概率至多为 $1/2$（如果那个值不在 $\{0,1\}$ 中，概率为 $0$）。

也可以从计数的角度看：满足 $\bm{D}\bm{r} = \bm{0}$ 的 $\bm{r} \in \{0,1\}^n$ 至多有 $2^{n-1}$ 个（因为每组固定的 $r_{-j}$，即除了 $r_j$ 后其余分量的集合，至多对应一个 $r_j$ 的取值，至多有一个满足条件），而 $\bm{r}$ 的总选取数为 $2^n$，所以：

$$\Pr[\bm{D}\bm{r} = \bm{0}] \le \frac{2^{n-1}}{2^n} = \frac{1}{2}$$

独立重复 $t$ 次（每次独立随机选取 $\bm{r}$），错误概率降为 $2^{-t}$，总时间 $O(tn^2)$。取 $t = O(\log n)$，即可在 $O(n^2 \log n)$ 时间内以高概率得到正确结果。

Schwartz-Zippel 视角

Freivalds 算法也可以从 Schwartz-Zippel 引理的角度统一理解。将 $(\bm{D}\bm{r})_i = \sum_k d_{ik} r_k$ 看作变量 $r_1, \ldots, r_n$ 的多元多项式，它是一个总次数为 $1$ 的多项式。若它不恒为零，由 Schwartz-Zippel 引理（$d = 1,\, |S| = 2$），在 $S = \{0,1\}$ 上随机取值为零的概率 $\le 1/|S| = 1/2$。

Karp-Rabin 字符串匹配

问题定义

模式匹配（Pattern Matching）是字符串算法中的经典问题：给定文本串 $T[1 \ldots n]$ 和模式串 $P[1 \ldots m]$（$m \le n$），找到 $P$ 在 $T$ 中所有出现的位置，即所有满足 $T[j \ldots j+m-1] = P$ 的位置 $j$。

朴素算法逐位置对齐并逐字符比较，最坏时间 $O(nm)$。确定性线性算法（如 KMP、Boyer-Moore）可以达到 $O(n + m)$，但需要预处理模式串，空间 $O(m)$。

通用框架：Fingerprinting 方法

在介绍具体算法之前，先看 fingerprinting 方法解决模式匹配的一般框架：

1. 计算模式的指纹 $\text{FING}(P)$
2. 对每个位置 $j$，计算子串的指纹 $\text{FING}(T_j)$（其中 $T_j = T[j \ldots j+m-1]$）
3. 比较 $\text{FING}(T_j)$ 与 $\text{FING}(P)$

这个框架要求指纹函数满足一个额外条件：增量可计算性——能够从 $\text{FING}(T_j)$ 在 $O(1)$ 时间内递推出 $\text{FING}(T_{j+1})$。这是因为如果每个位置都从头计算指纹，总时间仍为 $O(nm)$，没有改进。

Karp-Rabin 算法

Karp-Rabin 算法给出了一个满足增量可计算性的 fingerprinting 方案。

将二进制字符串 $s = s_1 s_2 \ldots s_m$ 视为整数 $\bar{s} = \sum_{i=1}^{m} s_i \cdot 2^{m-i}$。定义指纹：

$$\text{FING}_p(s) = \bar{s} \bmod p$$

其中 $p$ 是从不超过 $mn^3$ 的素数中均匀随机选取的素数。

滑动窗口与增量更新

关键观察：相邻位置的子串 $T_j$ 和 $T_{j+1}$ 高度重叠，仅相差首尾各一个字符。在整数表示下：

$$\bar{T}_{j+1} = 2\big(\bar{T}_j - T[j] \cdot 2^{m-1}\big) + T[j+m]$$

直觉很简单：从 $T_j$ 到 $T_{j+1}$，去掉最高位 $T[j]$，其余位左移一位（乘以 $2$），再加上新的最低位 $T[j+m]$。

由于模运算与加法、乘法兼容（即 $(a + b) \bmod p = ((a \bmod p) + (b \bmod p)) \bmod p$，乘法同理），同一递推关系在模 $p$ 下也成立：

$$\text{FING}_p(T_{j+1}) = \big(2 \cdot (\text{FING}_p(T_j) - T[j] \cdot 2^{m-1}) + T[j+m]\big) \bmod p$$

只需预计算 $2^{m-1} \bmod p$，之后每次更新只涉及 $O(1)$ 次模运算。

算法流程

flowchart LR
    A["随机选取素数 p ≤ mn³"] --> B["预计算 FING(P) 和 FING(T₁)<br/>以及 2^(m-1) mod p"]
    B --> C{"FING(T_j) = FING(P)?"}
    C -- 是 --> D["报告位置 j 匹配"]
    C -- 否 --> E["跳过"]
    D --> F{"j < n - m + 1?"}
    E --> F
    F -- 是 --> G["O(1) 递推 FING(T_{j+1})"]
    G --> C
    F -- 否 --> H["结束"]

    classDef init fill:#e3f2fd,stroke:#1565c0,stroke-width:2px
    classDef decision fill:#fff3e0,stroke:#ef6c00,stroke-width:2px
    classDef match fill:#e8f5e8,stroke:#2e7d32,stroke-width:2px
    classDef skip fill:#f8f9fa,stroke:#495057,stroke-width:2px
    classDef endclass fill:#ffebee,stroke:#c62828,stroke-width:2px

    class A,B init
    class C,F decision
    class D match
    class E,G skip
    class H endclass

复杂度：

• 时间：预处理 $O(m)$，匹配阶段每步 $O(1)$，共 $n - m + 1$ 步，总计 $O(n)$
• 空间：$O(\log(mn))$——只需存储当前指纹、素数 $p$、预计算的 $2^{m-1} \bmod p$

错误分析

对于某个固定位置 $j$，若 $T_j \neq P$，假阳性发生当且仅当 $p \mid (\bar{T}_j - \bar{P})$。令 $z_j = |\bar{T}_j - \bar{P}|$，则 $0 < z_j < 2^m$，所以 $z_j$ 至多有 $m$ 个不同的素因子（理由同前）。

$$\Pr[\text{位置 } j \text{ 假阳性}] = \frac{\#\{p \le mn^3 : p \text{ 是素数且 } p \mid z_j\}}{\pi(mn^3)} \le \frac{m}{\pi(mn^3)} \approx \frac{m \cdot \ln(mn^3)}{mn^3}$$

这里有 $n - m + 1 \le n$ 个位置需要检查。由联合界（union bound：多个事件中至少一个发生的概率不超过各自概率之和，即 $\Pr[\bigcup_i A_i] \le \sum_i \Pr[A_i]$）：

$$\Pr[\text{存在假阳性}] \le n \cdot \frac{m \cdot \ln(mn^3)}{mn^3} = \frac{\ln(mn^3)}{n^2} = O\left(\frac{\log n}{n^2}\right) = O\left(\frac{1}{n}\right)$$

Karp-Rabin 的优势

与 KMP 等确定性算法相比，Karp-Rabin 的主要优势在于：

• 实现极简：核心仅涉及模运算，无需复杂的预处理数据结构
• 空间极小：仅需 $O(\log n)$ 空间，远小于 KMP 的 $O(m)$
• 泛化能力强：天然适用于多模式匹配（同时搜索多个模式串）、二维模式匹配、以及大字母表上的匹配问题
• 数据流友好：文本可以逐字符流式输入，无需预先存储

一般字母表

上述描述假设二进制字母表 $\{0,1\}$。对于大小为 $|\Sigma|$ 的一般字母表，只需将 $2$ 替换为 $|\Sigma|$：将字符串视为 $|\Sigma|$ 进制数，递推公式变为 $\text{FING}_p(T_{j+1}) = (|\Sigma| \cdot (\text{FING}_p(T_j) - T[j] \cdot |\Sigma|^{m-1}) + T[j+m]) \bmod p$。分析完全类似。

多重集相等性检验与元素唯一性

问题定义

给定一个序列 $A = (a_1, a_2, \ldots, a_n)$，其中 $a_i \in [n] = \{1, 2, \ldots, n\}$，判断 $A$ 中的元素是否两两不同（元素唯一性问题，Checking Distinctness）。

等价地，如果元素两两不同，则 $A$ 恰好是 $\{1, 2, \ldots, n\}$ 的一个排列。因此问题可以表述为：判断多重集（Multiset）$A$ 是否等于集合 $I = \{1, 2, \ldots, n\}$（作为多重集相等）。

排序后逐个比较需要 $O(n \log n)$ 时间。哈希表方法需要 $O(n)$ 时间但空间也是 $O(n)$。利用 fingerprinting，可以在 $O(n)$ 时间、$O(\log n)$ 空间内完成——这在数据流模型下尤为重要。

多项式编码

将多重集编码为多项式是 Lipton 的核心思想。定义：

$$f_A(x) = \prod_{i=1}^{n} (x - a_i) \qquad f_I(x) = \prod_{i=1}^{n} (x - i)$$

$f_A$ 和 $f_I$ 都是 $\R$ 上的首一（最高次系数为 1）$n$ 次多项式。$A$ 中元素两两不同（且均在 $[n]$ 中），当且仅当 $f_A \equiv f_I$。这是因为首一多项式可以唯一分解为 $\prod (x - r_i)$，其根集合（含重数）完全确定了这个多项式。

定义指纹：

$$\text{FING}(A) = f_A(r) \bmod p = \prod_{i=1}^{n} (r - a_i) \bmod p$$

其中参数 $r$ 和 $p$ 的选取需要仔细设计。

两类错误源

当 $A$ 中有重复元素时（即 $f_A \not\equiv f_I$ 在 $\R$ 上），假阳性 $\text{FING}(A) = \text{FING}(I)$ 可以由两个不同的原因引起：

两层随机性

仅用随机素数 $p$（固定 $r$）或仅用随机取值点 $r$（固定 $p$）都不足以保证低错误概率。需要同时随机化 $r$ 和 $p$。

错误源 1：$f_A \equiv f_I$ 在 $\mathbb{Z}_p$ 上

虽然 $f_A \neq f_I$ 在 $\R$ 上，但有可能在取模 $p$ 之后两个多项式变得相同。这发生在 $p$ 整除 $f_A - f_I$ 的某个非零系数的时候。

设 $f_A(x) - f_I(x) = \sum_{k=0}^{n} c_k x^k$，其中 $c_k \in \mathbb{Z}$ 且不全为零。每个系数 $|c_k|$ 至多为 $\binom{n}{k} \cdot n^k \le n^n$（$a_i \in [n]$，选择 $k$ 个元素的组合数乘以每个元素的最大值 $n$ 的 $k$ 次方）。素因子至少为 2，因此 $c_k$ 的不同素因子个数至多为：

$$\log_2 |c_k| = \frac{\ln |c_k|}{\ln 2} \le \frac{n \ln n}{\ln 2} = O(n \log n)$$

错误源 2：$f_A \not\equiv f_I$ 在 $\mathbb{Z}_p$ 上，但 $f_A(r) \equiv f_I(r) \pmod{p}$

此时 $g(x) = f_A(x) - f_I(x)$ 作为 $\mathbb{Z}_p$ 上的多项式不恒为零，次数至多为 $n$。由 Schwartz-Zippel 引理（或直接由域上多项式的根的个数），随机 $r \in \mathbb{Z}_p$ 满足 $g(r) \equiv 0 \pmod{p}$ 的概率至多为 $n/p$。

Lipton 算法与参数选择

Lipton 算法（Lipton's Algorithm）的具体参数如下：

• 随机选取素数 $p$，满足 $\dfrac{(n\log n)^2}{2} \le p \le (n\log n)^2$
• 随机选取 $r \in \mathbb{Z}_p$
• 计算 $\text{FING}(A) = \prod_{i=1}^{n} (r - a_i) \bmod p$
• 计算 $\text{FING}(I) = \prod_{i=1}^{n} (r - i) \bmod p$
• 检查 $\text{FING}(A) = \text{FING}(I)$

参数范围的选取

选取素数范围为 $[L, U]$（其中 $L = (n\log n)^2/2,\, U = (n\log n)^2$），而非从 $[1, U]$ 中选取，是为了保证所有素数都足够大，从而控制错误源 2。

由素数定理，区间 $[L, U]$ 中的素数个数约为：

$$\pi(U) - \pi(L) \approx \frac{U}{\ln U} - \frac{L}{\ln L} \approx \frac{L}{\ln L} = \Theta\left(\frac{(n\log n)^2}{\log(n\log n)}\right) = \Theta\left(\frac{n^2 (\log n)^2}{\log n}\right) = \Theta(n^2 \log n)$$

错误源 1 的概率：对于某个非零系数 $c_k$，它至多有 $O(n\log n)$ 个素因子。在 $[L, U]$ 内约有 $\Theta(n^2 \log n)$ 个素数中，$p$ 恰好整除 $c_k$ 的概率：

$$\Pr[\text{错误源 1}] \le \frac{O(n \log n)}{\Theta(n^2 \log n)} = O\left(\frac{1}{n}\right)$$

错误源 2 的概率：由 Schwartz-Zippel 引理，随机 $r \in \mathbb{Z}_p$ 使得非零多项式 $g(x) \bmod p$ 取值为零的概率至多为 $n/p \le n/L$：

$$\Pr[\text{错误源 2}] \le \frac{n}{(n\log n)^2 / 2} = \frac{2}{n(\log n)^2} = O\left(\frac{1}{n}\right)$$

由联合界，总错误概率为 $O(1/n)$。

复杂度与数据流适用性

指标	复杂度
时间	$O(n)$——遍历所有元素，逐步累乘 $(r - a_i) \bmod p$
空间	$O(\log n)$——只需存储当前部分积、$r$ 和 $p$
错误	$O(1/n)$（单边错误，仅假阳性）

Lipton 算法的一个重要优势是天然适合数据流模型（Data Stream Model）：元素 $a_1, a_2, \ldots, a_n$ 逐个到达，算法只需维护当前部分积 $\prod_{i=1}^{k}(r - a_i) \bmod p$，每到达一个新元素只需一次乘法和一次取模。这在处理大规模数据时尤为有用——数据可能太大而无法全部存储在内存中。

推广：一般多重集相等性

Lipton 算法不局限于元素唯一性，可以推广到一般的多重集相等性检验：给定两个多重集 $A = (a_1, \ldots, a_n)$ 和 $B = (b_1, \ldots, b_n)$，判断 $A = B$。只需分别计算 $\text{FING}(A) = \prod(r - a_i) \bmod p$ 和 $\text{FING}(B) = \prod(r - b_i) \bmod p$，然后比较即可。分析完全类似。

Fingerprinting 的统一视角

回顾本讲的所有算法，它们共享一个统一的范式：

问题	对象	指纹 $\text{FING}$	随机源	时间
PIT	多项式 $Q$	$Q(r_1, \ldots, r_n)$	随机取值点	取决于电路
字符串相等（公共随机）	$a \in \{0,1\}^n$	$\sum a_i r^i \bmod p$	随机 $r \in \mathbb{Z}_p$	$O(n)$
字符串相等（私有随机）	$a \in \{0,1\}^n$	$a \bmod p$	随机素数 $p$	$O(n)$
二部图匹配	Edmonds 矩阵 $\bm{M}$	$\det(\bm{M})\big\|_{x_{ij}=r_{ij}}$	随机赋值	$O(n^\omega)$
矩阵乘法验证	矩阵 $\bm{D}$	$\bm{D}\bm{r}$	随机向量 $\bm{r}$	$O(n^2)$
字符串匹配	子串 $T_j$	$\bar{T}_j \bmod p$	随机素数 $p$	$O(n)$
多重集相等	多项式 $f_A$	$f_A(r) \bmod p$	随机 $r$ 和 $p$	$O(n)$

Fingerprinting 的本质是一种「降维」策略：将高维或大规模的对象映射到低维空间中，利用随机性保证「保距性」——不同对象大概率映射为不同指纹。错误分析的核心工具是两个：

• Schwartz-Zippel 引理：非零多项式在随机点处为零的概率有上界
• 素数定理：控制随机素数整除特定整数的概率

这一思想不仅是随机算法的基石，也是后续课程中哈希技术、数据流算法、降维方法（如 Johnson-Lindenstrauss 引理）的核心起点。