Theory of Computation note IV: 全源最短路的高速（迫真）算法：电路复杂性

· · 算法·理论

Theory of Computation note I\ Theory of Computation note III

计算稠密图上任意两点之间的最短路是一个经典问题。2014 年，Ryan Williams 给出了一个 \mathcal O(\frac {n^3} {\exp(\Theta(\sqrt {\log n}))}) 的算法，它优于任何 \mathcal O(n^3/\text{polylog}(n)) 的算法。

这个算法基于电路复杂性中的技术。实际上，下面电路复杂性本身的内容反而阉割了很多，相信大家包括我也不感兴趣

\mathsf{AC}^0 电路

请证明二进制加法在 $\mathsf{AC}^0$ 中。 :::success[电路] 对于每一位，它受到进位当且仅当存在前面的某一位两边都是 $1$ 且到这一位之间两边至少有一个 $1$。按照此定义构造即可。 ::: 注意二进制乘法不在 $\mathsf{AC}^0$ 中。接下来我们会证明这一点。 ## 多项式方法 我们已经知道一个电路可以用多项式次的多元多项式表示。不过实际上，对于一个大小为 $s$、深度为 $d$ 的无界扇入电路，**可以用 $\log^{\mathcal O(d)} s$ 次的 $\mathbb{Z}_3$ 上的多元多项式以 $99\%$ 的精度近似。** 关键在于同时存在多个输入，我们仅考虑或门，设其为 $v_{1\dots k}$，我们随机选取 $a_{1\dots k} \in \mathbb{Z}_3$。考虑（模 $3$ 意义下）$x=\sum_{i=1}^n v_ia_i$，如果 $v$ 是全 $0$ 则 $x$ 一定是 $0$，否则有 $2/3$ 概率不是 $0$。那么我们造 $\Theta(\log s)$ 组 $a$，然后用 $1-\prod_i(1-x_i^2)$ 拼起来，就只有 $\frac {1} {100s}$ 的错误率了。union bound 一下总错误率只有 $1\%$。 ## $\text{Parity} \notin \mathsf{AC}^0

上述结论可以用来证明奇偶校验问题 Parity 不在 \mathsf{AC}^0 中。即，给你一些布尔变量，求它们的异或和。

我们先把输入和输出都映射到 \mathbb Z_3 上的 \{-1,1\}，并且只关心这类输入 \{-1,1\} 时输出也是 \{-1,1\} 的多项式。之前的多项式的输入和输出是 \{0,1\}，需要转换一下。这样可以简单地给出一个 Parity 的多项式：\prod_{i=1}^n x_i。

现在对于常数 c，我们假设 Parity 可以被 c\sqrt n 次多项式以 99\% 精度近似，即在至少 0.99\cdot 2^n 个输入上与 \prod_{i=1}^n x_i 的结果相同。

对于每种输入，我们都有两种不同的输出，因此在上述条件下总的函数个数至少是 2^{0.99\cdot 2^n}，并且对于每个函数，用之前“MIP=NEXP”中的插值方法都可以构造出一个对应的（多线性）多项式。

现在，把多项式展开，然后考虑其中次数 >n/2 的项，它可以被替换为 \prod_{i=1}^n x_i 乘上其中没有出现的项，也就是说，它的次数可以被控制到 n/2+c\sqrt n。

然而，算一下此类多项式的个数：每一项次数不超过 n/2+c\sqrt n，系数有三种可能，所以个数是 3^{\sum_{i\le n/2+c\sqrt n} \binom n i}=3^{(0.5+\epsilon)2^n}，选取足够小的 c 就有 3^{(0.5+\epsilon)}<2^{0.99}，矛盾！

然后把 $\text{Parity}$ 归约到乘法：用一个 $\mathsf{AC}^0$ 电路把 $x_i$ 放到二进制数 $a$ 的 $a_{in}$ 位置，再构造一个 $\forall 1\le i\le n,b_{in}=1$ 的二进制数 $b$，显然 $(ab)_{n(n+1)}$ 就是 $x$ 的异或和了。 ## APSP 的快速算法 我们用做 $\mathcal O(\log n)$ 次 $(\min,+)$ 矩阵乘法的方法求 APSP。对行/列按照 $k$ 分块，我们希望能快速处理 $n\times k$ 和 $k\times n$ 的 $(\min,+)$ 矩阵乘法，调用 $n/k$ 次这个算法对结果取 $\min$ 就行了。 考虑将 $\min(a_i+b_i)$ 写成 $\mathsf{AC}^0$ 电路。课上有值域是 $\mathcal O(\text{poly}(n))$ 的假设，于是有很简单的构造方法：首先做二进制加法。然后可以造一个比较器，某个数是最小值当且仅当它小于等于其他所有数。 但如果没有值域限制，如实数的情形，我们仍然能做。请思考一下。 :::success[电路] 有 $a_i+b_i\le a_j+b_j \iff a_i-a_j\le b_j-b_i$，于是对所有 $a_i-a_j,b_j-b_i$ 离散化，把值域降低到 $\mathcal O(\text{poly}(n))$ 之后就很简单了。当然最终电路输出的是下标而非具体值。 ::: 这里序列长度为 $k$，于是它可以被次数为 $\log^{\mathcal O(1)} (k\log n)$ 的多项式以 $99\%$ 精度近似。 取一个合理的 $k=\exp({\Theta(\log^{c} n)})$，将上述多项式展开，令展开项数有 $\text{poly}(k)^{\log^{c} n}=\mathcal O(n^{0.1})$ 项。实际上，可以随意取 $c=0.4999$；对于 $c=0.5$，结果是 $n^{\Theta(1)}$，还需要进一步分析具体常数~~没错，我懒得写了~~。然后调用一个大锤子： * **$n\times n^{0.172}$ 和 $n^{0.172}\times n$ 的 $(+,\times)$ 矩阵乘法可以做到 $\tilde {\mathcal O}(n^2)$。**[Coppersmith 1982] 于是把单项式中的项分离到两边，然后把全部的项拼到一个矩阵中做一次矩阵乘法即可。最后还要做 $\mathcal O(\log n)$ 轮提升正确率。 嗯，真的是太快啦！ *注：本文是从 Spring 2026, Theory of Computation, IIIS, Tsinghua 的课程学习的，外加一些个人的理解。文中有任何错误请指正。*