引入
$\gdef\b#1{\boldsymbol{#1}}$下文中 $d$、$m$ 代表常数。
考虑运行时间为 $t(n)$ 的 $d$ 带图灵机，我们考虑的问题是可以用多少空间的多带图灵机模拟它。这一问题的重要性在于：
如果 $\forall\varepsilon>0$，$\mathsf{TIME}[t(n)]\subseteq\mathsf{SPACE}[t(n)^\varepsilon]$，则 $\mathsf{P}\ne\mathsf{PSPACE}$。
最新的这篇文章做到了 $\mathsf{TIME}[t(n)]\subseteq\mathsf{SPACE}[\sqrt{t(n)\log t(n)}]$，大致的思路是缝合了空间模拟时间的基本思想，以及一个 $\mathsf{L}\text{ vs }\mathsf{P}$ 方面的最新进展。
单带情况
在限制空间的情况下，其实显而易见的思路只有一条，就是做一个 time-space tradeoff，以重复计算的代价换取不存储完整纸带的能力。
考虑每时每刻，只在 $M^\prime$ 中存储 $M$ 的纸带上的一小段，在上面进行模拟。如果读写头离开了当前段进入其他部分，就 recover 另一小段的当前情况，继续模拟。
具体到单带图灵机上，考虑小段长为 $b(n)$，那么在跨段时，需要重新模拟新进入段的所有历史操作，但模拟过程不能递归依赖其他段的信息。为此，只需存储历史上每次跨段时的信息即可，这所需记录条目数是平均 $\frac{t(n)}{b(n)}$ 的，每个条目需要记录段号与状态，是 $\log\frac{t(n)}{b(n)}+\Omicron(1)$ 的，如果改成记录 $\pm 1$ 就是 $\Omicron(1)$（这个和四毛子优化 RMQ 是一样的）。为了避免 $M$ 在段边界反复横跳导致卡到最劣，可以枚举分段起始点的偏移，根据鸽巢原理一定存在一个偏移量满足跨段次数 $\le\frac{t(n)}{b(n)}$。
显然这里取 $b(n)=\sqrt{t(n)}$，平衡到 $\Omicron(\sqrt{t(n)})$ 的空间复杂度。
但是这个思路在多带完全不行：各带读写头的跨段没法同步，就算同步了，考虑 $(x,y)$ 表示当前第一条纸带的读写头在第 $x$ 段，第二条在 $y$，那么比如当前在 $(2,3)$ 恢复所需要的历史操作可能是 $(2,1)$、$(2,2)$、$(1,3)$、$(3,3)$ 这些情形，它就爆炸了。简而言之，依赖关系从单带的链，变成多带的 DAG。
多带历史思路
首先展开说一下多带跨段的同步以及标准化。我们希望将位置和时间同时分块：
- 对于多带图灵机，存在等效的多带“分块图灵机” with 块大小 $b(n)$，时间 $\Theta(t(n))$（实际上要求 $\log t(n)\le b(n)\le t(n)$，以及 $t(n)$、$b(n)$ time-constructible，不过这些不太重要）。分块图灵机指的是，各纸带划分为 $b(n)$ 长的小段，读写头跨段只能出现在 $b(n)$ 倍数的时刻。
构造思路
加的一条带作为“时钟”，读写头持续在 $b(n)$ 的范围内来回移动，如果其他头需要跨段但“时钟”未到“整点”（下文我称时间的分段为时间块），就等着到整点再动。但这仍然会遇到段边界反复横跳的问题。处理方法是，扩展字母表/带数使得每带的每段都记录相邻两段的信息，这样就无需等待，只需在当前时间块完成后，额外花若干（常数个）时间块把更新的信息复制到相邻段即可。
设纸带数为 $d$。
刻画多带的历史依赖关系的结构被称为 computation graph：每个时间块 $i$ 对应一个节点，其存储 $\text{content}_i$，内容为该时间块结尾时：
- 图灵机的状态 $q_i$；
- 各读写头位置 $h_{i,1}\sim h_{i,d}$；
- 各读写头所在纸带段的最终内容 $c_{i,1}\sim c_{i,d}$。
空间为 $\Omicron(b(n)+\log t(n))$。
为了得到 $\text{content}_i$，我们需要 $\text{content}_{i-1}$，以及另外某些 $\text{content}_{k_1,\cdots,k_d}$。如果对于某纸带 $j$， $$ \left\lfloor\frac{h_{i,j}}{b(n)}\right\rfloor=\left\lfloor\frac{h_{k,j}}{b(n)}\right\rfloor\land\forall k^\prime\in(k,i),\left\lfloor\frac{h_{i,j}}{b(n)}\right\rfloor\ne\left\lfloor\frac{h_{k^\prime,j}}{b(n)}\right\rfloor $$ 也就是说，$\text{content}_k$ 中有时间块 $i$ 所需的纸带 $j$ 的最新信息，那么连边 $k\to i$。因此，每个点入度 $\le d+1$。
两个注：
- 发现不强制标准化分块也是可以的，就是要每带记录两个块，入度 $\le 2d+1$。
- 处理输入有两种思路，一种是加个只存输入的 $\text{content}_0$，一种是在每个点额外存历史首次访问到的段的内容。
假定已知 computation graph 的结构，待求 $\text{content}_{t(n)/b(n)}$。当前的模型形如：给定一张 DAG，指定源和汇。每次如果一个点是源，或它的所有入点上都有石子，可以在这个点上也放石子；也可以任意拿掉石子。问使得汇上有石子，最少需要备多少石子。这被称为 (standard/black) pebble game。
例如这张图应该至少需要四个石子：
+0, +1, +2, -1, +3, -0, +4, -3, +0, +1, +2, -0, -1, +5
记 $P_k(n)$ 为最大入度为 $k$ 的 $n$ 点图中，最多的所需石子数（可以任意指定一个汇）。[HPV75] 中证明了对于常数 $k$，$P_k(n)=\Omicron(n/\log n)$。
证明
记 $R_k(n)$ 为最大入度为 $k$，所需 $n$ 个石子的图中，最少的边数。只需证明 $R_k(n)=\Omega(n\log n)$ 即可，考虑用割 + 归纳的证法。取这样一张图 $G=(V,E)$ 中，用 $\le n/2$ 个石子就能达到的所有点 $V_1$，剩余为 $V_2$。如果将 $V_2$ 的导出子图拿出，入度为 $0$ 的点可以随意放石子，那么这部分需要至少 $n/2-k$ 个石子。这是因为，在整张图中，如果要将 $V_2$ 中的一个入度为 $0$ 的点上放上石子，就需要在 $V_1$ 中至多 $k$ 个点上放石子，就需要备至多 $n/2+k-1$ 个石子。如果 $V_2$ 部分只需 ${{}<{}}n/2-k$，两者相加就与需要 $n$ 个石子矛盾了（似乎常数项可以更紧一点？）。另外 $V_1$ 中一定有需 $\ge n/2-k$ 个石子的点，因此 $$ R_k(n)\ge 2R_k\left(\frac n2-k\right)+\text{cut}(V_1,V_2) $$ 只需 $\text{cut}(V\_1,V\_2)$ 不太小（$=\Theta(n)$）就行。如果 $\text{cut}(V_1,V_2){{}<{}}n/4$，那么可以在 $V_1$ 中与 $V_2$ 有边的节点上全留石子，因此 $V_2$ 部分单独拿出来做，需要至少 $3n/4$ 的石子。于是 $$ R_k(n)\ge\min\Set{2R_k\left(\frac n2-k\right)+\frac n4,R_k\left(\frac n2-k\right)+R_k\left(\frac{3n}4\right)} $$ 归纳可证 $R_k(n)\ge cn\log n$。另外存在卡到 $\Theta(n/\log n)$ 的构造，详见 Space bounds for a game on graphs，似乎是形如 FFT 电路。
这就意味着无论怎么取 $b(n)$，空间被限制在 $\Omega(n/\log n)$。为完成整个证明，还需解决两个问题：
- 如何求出 computation graph？直接枚举每个头每个时间块的位置，是 $\Omicron\big(\frac{t(n)}{b(n)}\log\frac{t(n)}{b(n)}\big)$ bits，当然也可以枚举差分。如果模拟过程中发现读写头走的方向与枚举的不符，就返回
FAIL。 - 如何求出一组达到 $\Omicron\big(\frac{t(n)}{b(n)}/\log\frac{t(n)}{b(n)}\big)$ 的放石子顺序？直接枚举的话递归栈大小会爆，但无论如何每次猜一步，总还是 $\mathsf{NSPACE}\big[\frac{t(n)}{b(n)}\big]$ 的。$b(n)$ 稍微取大点，用下 Savitch 即可。
小结
- 整体的思想是，局部纸带段—历史跨段记录的平衡。
- computation graph 是对整个结构的很本质的刻画，但是直接在这上面跑组合算法是没前途的。
- 两个细节处理的 trick：分块化，以及猜 computation graph。
容易感受到，之前研究者们都偏向于相信，$n/\log n$ 没法再优化了。
tree evaluation problem
如果把 computation graph 展开，我们可以得到一棵高度为 $\Omicron\big(\frac{t(n)}{b(n)}\big)$，$\Omicron(d)$ 叉的树。尽管看似变得冗余了，但是树上的这一问题有代数做法，这就给了突破口。tree evaluation problem (TEP) 指的是，给定一颗高度为 $h$ 的满 $d$ 叉树，每个节点 $u$ 上有 $b$ 位 $01$ 串 $\text{content}_u$。初始给定叶子的串，以及每个节点由其各儿子串决定其本身串的函数，即 $(\set{0,1}^b)^d\to\set{0,1}^b$ 的函数，求根的串。
输入的长度是 $\Theta(b2^{bd}d^h)=2^{\Theta(b+h)}$ 的，而这一问题是否 $\in\mathsf{NL}$ 还是 open 的（大家偏向于否）。但是 [CM24] 提出了一个空间 $\Omicron(db+h\log(db))$ 的做法，对于大小为 $n$ 的输入而言，这是 $\Omicron(\log n\log\log n)$ 的（据说还能多除个 $\log\log\log n$？）。
一般的 dfs 做法需要 $\Omicron(dhb)$ 的空间：
而 [CM24] 的想法是，把上面各层的信息给叠起来，但利用单位根的性质（说白了就是单位根反演）把叠起来的垃圾抵消了。
具体而言，每个节点的函数可以看作 $b$ 个 $\mathbb{F}_2^{bd}\to\mathbb{F}_2$ 的函数，具体来说，如果原函数是 $f(\b x_1,\cdots,\b x_d)$（每个 $\b x_i$ 是一个儿子的 $b$ 位），那么对应的函数是： $$ \tilde{f}(\b x_1,\cdots,\b x_d)_i=\sum_{\b a_1,\cdots,\b a_d\in\mathbb{F}_2^b}f(\b a_1,\cdots,\b a_d)_i\prod_{j=1}^d\prod_{k=1}^b(\b x_{j,k}-\b a_{j,k}+1) $$ 这个东西的想法和拉格朗日插值/CRT 是一样的，在特征为 $2$ 的域中，$x-y+1$ 等价于 $[x=y]$。我们将定义域和值域扩到 $\mathbb{F}_{2^q}$，公式不变。
现在只需存储 $(d+1)b$ 个 $\mathbb{F}_{2^q}$ 内的元素便可以计算。记这些寄存器为 $\b x_1,\cdots,\b x_{d+1}\in\mathbb{F}_{2^q}^b$。
$\text{calc}(u,\b y):$
——将 $\text{content}_u$ 加给 $\b y$，其他寄存器的内容不变。方便起见记其他寄存器为 $\b x_1\sim\b x_d$。$\text{for }i=0\to m-1:$$(1)$ 对于每个儿子调用 $\text{calc}$，使 $\b x_j$ 变为 $\omega_m^i\b x_j+\text{content}\_{\text{son}_{u,j}}$$\b y\xleftarrow{+}\tilde f(\b x_1,\cdots,\b x_d)$
原样撤回 $(1)$
这里 $\omega_m$ 是 $m$ 次单位根，有性质：
- 对于 $<m$ 次多项式 $P$，$\displaystyle\sum_{i=0}^{m-1}P(\omega_m^iu_1+v_1,\cdots,\omega_m^iu_k+v_k)=P(v_1,\cdots,v_k)$。
证明很简单：考虑 $P(x_1,\cdots,x_k)=x_1^{p_1}\cdots x_k^{p_k}$，那么 $$ \displaystyle\sum_{i=0}^{m-1}P(\omega_m^iu_1+v_1,\cdots,\omega_m^iu_k+v_k)=\sum_{q_1,\cdots,q_k}\left(\sum_{i=0}^{m-1}\omega^{i\cdot\sum_{j=1}^kq_j}\right)\prod_{j=1}^k\binom{p_j}{q_j}u_j^{q_j}v_j^{p_j-q_j}=v_1^{p_1}\cdots v_k^{p_k} $$ 只有 $m\mid\sum q_j$ 时打括号的和式才非零，而且特征为 $2$，$m$ 是奇数，所以后一个就直接取等过去了。
空间是（再次注意，这里不计输入）：
- $u$，全局记着就是 $h\log d$
- 所有寄存器，$(d+1)bq$
- 局部循环变量，$h\log(d^2b)$
- 求 $\tilde f$ 时所需的临时空间，$db+q$
现在只要求 $db<m<2^q$，因此总共 $\Omicron((h+db)\log(db))$。一个显而易见的优化空间是，可以把若干 $01$ 位压到 $\tilde f$ 的一个参数里：考虑 $\set{0,1}^p\to\mathbb{F}_{2^q}$ 的单射，设值域为 $S$。这时对于 $x,y\in S$， $$ [x=y]=\frac{\prod_{z\in S\setminus\set{y}}(x-z)}{\prod_{z\in S\setminus\set{y}}(y-z)} $$ 因此 $\deg\tilde f=db2^p/p$，寄存器的空间是 $(d+1)bq/p$，只需要 $db/p<2^{q-p}$ 即可，那索性取 $p=\log(db)=q/2$。这样空间就优化到 $\Omicron(h\log(db)+db)$。
假定 computation graph 已知，直接套用，代入 $h=t(n)/b(n)$，$b=b(n)$，就直接平衡到了惊人的 $\Omicron(\sqrt{t(n)\log t(n)})$。
细节处理
- 仍然将原图灵机先分块化。
- 为了处理输入 $\text{content}_0$ 在 $t(n)=\omicron(n^2)$ 时过长，需要将它再分块。所以索性将所有节点存储的信息都缩减成单带的一段。现在节点有两种：$(h,i)$ 表示第 $h$ 带的第 $i$ 时间块，$(h,0,i)$ 表示第 $h$ 带初始时第 $i$ 段。连边还是类似的。
- 枚举 computation graph。只需枚举每个时间块结束时每个读写头怎么移动，总共是 $(\log_23)d\frac{t(n)}{b(n)}$ bits。没必要把图显式建出，求儿子可以枚举后暴力区间求和检验。
- 在调用上述 TEP 算法过程中，求 $\tilde f$ 时需要对于 $f$ 的每组输入模拟。如果输入中有
FAIL直接返回FAIL，否则可以原地模拟，再检查最后一步的走向是否与枚举的相符，不符也返回FAIL。 - TEP 算法中的 $u$ 是不是可以直接用节点号描述啊……反正瓶颈不在这。另外 computation graph 对应的树不是满的，补补齐就行。
- 另外有个小细节，我们不要求 $t(n)$ 是 time/space-constructible 的，因为我们可以在整个模拟外套上枚举 $t(n)$ 的循环。
多维推广
设维数为 $m$。将每个纸带划分为边长为 $b(n)$ 的超立方体。论文里说多维不存在分块图灵机，我不太理解，应该也可以用类似上面叠相邻块内容的方法啊？
不分块也没什么问题。同一时间块内，每一维可能跨两段，因此访问到的总段数不超过 $2^m$，从而 computation graph 中每个节点的入度不超过 $(2^m+1)d$，每个节点的 content 仍包括：状态、时间块结束时读写头位置（$d\log t(n)$）、访问到的段的相对位置及内容（$2^db(n)^d$ 或 $3^db(n)^d$），因此位数是 $\Theta(b(n)^d+d\log t(n))$ 的，方便起见认为 $\log t(n)=\omicron(b(n))$。代入 TEP 的复杂度： $$ \Omicron\left(\frac{t(n)}{b(n)}\log b(n)+b(n)^d\right) $$ 取 $b(n)=\sqrt[d+1]{t(n)\log t(n)}$ 得 $\Omicron((t(n)\log t(n))^{1-\frac{1}{d+1}})$。
推论
对于 space-constructible 的 $t(n)$， $$ \mathsf{TIME}[t(n)]\subseteq\mathsf{SPACE}[\sqrt{t(n)\log t(n)}]\subsetneq\mathsf{SPACE}[t(n)^{\frac12+\varepsilon}] $$ 特别地，$\mathsf{SPACE}[n]$ 中有语言 $\notin\mathsf{TIME}[n^{2-\varepsilon}]$ 及 $\notin\mathsf{TIME}[n^2/\log^{>1}n]$。可以考虑一个“$\mathsf{SPACE}[n]$-complete”的例子： $$ \set{\langle M,x,1^k\rangle\mid \lvert M\rvert\le k\text{ 且 }M\text{ 在 }k\text{ 空间内停机}} $$ 另外，如果 $\mathsf{TIME}[t(n)]\subseteq\mathsf{SPACE}[t(n)^{\frac12-\varepsilon}]$，那么交替图灵机和随机存取图灵机都可以在时间 $t(n)^{1-2\varepsilon}$ 内模拟 $t(n)$ 的图灵机。