Theory of Computation note I: 空间复杂性
critnos
·
·
算法·理论
复杂性类，非确定图灵机
首先必须得速通一下基础知识。
语言是字符串的集合。
一个复杂性类包含了所有这样的语言 L：存在这种复杂性类对应的图灵机，输入 x 后 accept/reject 的结果和 x\in L 一致（当然，这个图灵机必须停机）。
给复杂性类加上 \text{co-} 前缀，表示对其中每个语言取补。
非确定图灵机是在确定性图灵机的基础上，每一步可以同时进入常数个分支（更准确地说，是猜测进入某个分支）。如果有任意分支 accept 就 accept，所有分支都 reject 就 reject，也可能不停机。
你发现这玩意能判定 L 不代表能判定 \bar L。实际上这等价于：可以向一个计算能力为同等限制下的确定性图灵机的验证者证明 x\in L 这个事实。即，取其中 accept 的计算路径。但是并不能证明 x\notin L，因为计算路径数可能远大于路径长度。
$\text{NP}$ 复杂性类：限制非确定性图灵机的运行次数不超过某个关于输入长度的多项式。
我们来直观理解一下一个复杂性类和它的补的区别：素数判定，语言是 $\{x|x\in \text{prime}\}$。
$\text{Prime}\in \text{co-NP}$ 是显然的，我们可以简单地给出一个合数的某个非平凡因子来证明这个数不是素数。然而，$\text{Prime}\in \text{NP}$ 是一个比较有趣的事情。如何用 $\mathcal O(\text{poly}(\log n))$ 长度的证书证明一个数是素数？
:::success[答案]
考虑原根存在性定理：$n$ 存在原根当且仅当 $n=2,4,p^k,2p^k$。
可以简单检查上述情况中 $n$ 是素数之外的任何情况。然后考虑给出 $n$ 的一个原根。众所周知，检查 $g$ 是原根的方式是，判断任意 $g^{(n-1)/p} \not \equiv 1 \pmod n$，其中 $p$ 是 $n-1$ 的素因子。
所以除了 $g$ 之外我们还给出 $n-1$ 的素因子集合，再递归地证明这些素因子是素数即可。
显然，递归树上叶子的数量和深度都是 $\mathcal O(\log n)$，因此检查的时间复杂度是可以接受的。
:::
## PSPACE=NPSPACE？
定义复杂性类 $\text{SPACE}(k),\text{NSPACE}(k)$ 分别为限制一个图灵机、非确定图灵机使用 $\mathcal O(k)$ 的空间（非确定图灵机使用的空间对于不同分支不会叠加）。
$\text{PSPACE},\text{NPSPACE}$ 指多项式空间。严格地说，$\text{PSPACE}(n)=\bigcup_{k\ge 1} \text{SPACEA}(n^k)$。
如何证明 $\text{PSPACE}$ 和 $\text{NPSPACE}$ 的等价性？或者说 $\text{NPSPSCE}\subset \text{PSPACE}$。
## NL in L^2
我们考虑一类空间更小的复杂性类 $\text{NL}=\text{NSPACE}(\log n)$ 和 $\text{L}^2=\text{SPACE}(\log^2 n)$。如果可以证明 $\text{NL}\subset \text{L}^2$，那么只要给输入后面加上一堆无意义字符，使得 $n\gets m,m\ge n$ 然后调用上述证明，就可以说明 $\forall m\ge \log n,\text{NSPACE}(m) \subset \text{SPACE}(m^2)$，于是自然有 $\text{NPSPSCE}\subset \text{PSPACE}$。
考虑 $\text{NL}$ 类的实质。空间只有 $\mathcal O(\log n)$，所以图灵机的状态数是 $\mathcal O(\text{poly}(n))$ 的。非确定图灵机在状态构成的图上搜索，如果能搜索到目标状态就 accept，否则 reject。
因此所有 $\text{NL}$ 问题可以被规约到有向图可达性。显然，这个问题同时在 $\text{NL}$ 中。我们只需要给出一条路径，然后逐步验证相邻两点之间是否有边。这个问题验证需要 $\log n$ 空间的原因是存储一个数需要 $\log n$ 的空间。
因此这被称为 $\text{NL}$ 完全问题。我们只需要用确定性图灵机在 $\mathcal O(\log^2 n)$ 的空间解决这个问题，就能证明 $\text{NL}\subset \text{L}^2$。
**给你一张 $n$ 个点的有向图，用 $\mathcal O(\log^2 n)$ 的额外空间判断两点的可达性。**
这个不算很难，可以思考一下。
:::success[算法]
考虑分治。设 $f(x,y,k)$ 为 $x$ 能否在 $k$ 步内到达 $y$，如果 $x,y$ 之间有边直接 accept，否则枚举所有点 $w$ 调用 $f(x,w,\lfloor k/2 \rfloor)\land f(w,y,\lceil k/2 \rceil)$。
递归栈 $\mathcal O(\log n)$ 层，每层需要 $\mathcal O(\log n)$ 空间。
:::
## NL=co-NL
同样地，证明有向图上一点无法到达另一点更难一些。现在轮到你来解决这个问题了！
只要证明了这个 $\text{co-NL}$ 完全问题在 $\text{NL}$ 中，就有 $\forall L\in \text{NL},\bar L\in \text{co-NL}\in \text{NL}\Longrightarrow \bar {\bar L}=L\in \text{co-NL}$，进而 $\text{NL}=\text{co-NL}$，进而 $\forall m\ge \log n,\text{NSPACE}(m) = \text{co-NSPACE}(m)$。
**给你一张 $n$ 个点的有向图，可以向只有 $\mathcal O(\log n)$ 额外空间的验证者证明图上一点无法到达另一点。**
:::info
这被称为 Immerman–Szelepcsényi 定理，获得了 1995 年哥德尔奖。然而，这个算法相当简单而 ad-hoc，这个题的难度可能相当于一道 qoj 难度 8 的问题。
:::
:::success[算法]
考虑求出起点 $x$ 能到达的点数。删去 $y$ 后再求一遍，比较一下即可。
考虑逐步求出 $c_0=1,c_1,\dots ,c_{n-1}$ 表示 $x$ 走不超过 $i$ 步能到达的点数 $c_i$，$c_{n-1}$ 即为答案。
求 $c_i$ 的时候，枚举每一个点 $u$。对于可以不超过 $i$ 步到达的，直接证明即可。对于无法用 $i$ 步到达的，需要证明指向它的点都无法用 $i-1$ 步到达。这只需要再枚举一次每个点，证明其中可以用 $i-1$ 步到达的，最后说明这样的点数恰好是 $c_{i-1}$ 即可。
:::
*注：这部分的内容比较简短而且对于 OI 选手很容易理解，所以先于其他内容展示了。本文是从 Spring 2026, Theory of Computation, IIIS, Tsinghua 的课程学习的，外加一些个人的理解。文中有任何错误请指正。*