第五章：时间、空间与层次

可判定性允许任意有限资源。复杂度理论将机器限制在随输入长度增长的预算内，并研究资源增加是否严格扩展计算能力。

复杂度函数

对确定性图灵机 $M$，定义最坏情况时间

$$T_M(n)=\max_{|x|=n}\{\text{$M(x)$ 的转移次数}\}.$$

空间 $S_M(n)$ 计算工作带上被访问单元的最大数量；只读输入通常不计入工作空间。非确定性时间取所有计算分支的运行长度上界，不只计接受分支；所有分支都必须在预算内停机。

典型复杂度类为

$$\begin{aligned} \mathsf{DTIME}(t(n))&=\{L:\text{某确定性机在 }O(t(n))\text{ 时间判定 }L\},\\ \mathsf{SPACE}(s(n))&=\{L:\text{某确定性机在 }O(s(n))\text{ 空间判定 }L\}. \end{aligned}$$

常用并集类包括

$$\mathsf P=\bigcup_{k\ge1}\mathsf{DTIME}(n^k),\qquad \mathsf{PSPACE}=\bigcup_{k\ge1}\mathsf{SPACE}(n^k).$$

时间可构造性

对角化需要机器在给定资源预算结束时停止模拟。若函数 $t(n)$ 可由机器在 $O(t(n))$ 时间内计算或计时，则称其 time-constructible。$n^k$、$2^n$ 等常见函数满足该条件。

constructibility 排除具有异常不可计算波动的预算函数。层次定理中的正则性条件属于证明机制的一部分，不能从结论中省略。

时间层次定理

确定性时间层次定理的典型形式为：若 $t_1(n)\log t_1(n)=o(t_2(n))$，且函数满足适当 constructibility，则

$$\mathsf{DTIME}(t_1(n)) \subsetneq \mathsf{DTIME}(t_2(n)).$$

证明构造一台带时钟的对角机，在输入编码对应某机器时模拟并取反。额外 $\log t$ 因子来自通用模拟开销。

推论包括

$$\mathsf P\subsetneq\mathsf{EXP}.$$

层次定理证明“更多时间最终严格更强”，但不能直接区分相邻且重要的类，如 $\mathsf P$ 与 $\mathsf{NP}$。

空间层次定理

空间可以复用，通用模拟的额外成本较低。在标准工作带空间模型中，取满足 $s_1(n)\ge\log n$ 的空间可构造函数，且 $s_1=o(s_2)$，则

$$\mathsf{SPACE}(s_1(n)) \subsetneq \mathsf{SPACE}(s_2(n)).$$

常见类为

$$\mathsf L=\mathsf{SPACE}(\log n),\qquad \mathsf{PSPACE}=\bigcup_k\mathsf{SPACE}(n^k).$$

对数空间足以保存常数个输入位置、顶点编号和计数器，但不能显式保存长度为 $n$ 的 visited 数组。

时间与空间的基本关系

运行 $t(n)$ 步最多访问 $O(t(n))$ 个单元，因此

$$\mathsf{TIME}(t(n))\subseteq\mathsf{SPACE}(t(n)).$$

反向关系更弱。对 $s(n)\ge \log n$ 的标准可构造空间界，使用 $s(n)$ 空间的确定性机只有

$$2^{O(s(n))}$$

个配置；若判定机重复配置，之后会循环。因此可在指数时间内完成：

$$\mathsf{SPACE}(s(n)) \subseteq \mathsf{TIME}(2^{O(s(n))}).$$

配置图是连接时间与空间的主要工具：节点为机器配置，边表示一步转移，接受问题转化为图可达性。

Savitch 定理

Savitch theorem 给出

$$\mathsf{NSPACE}(s(n)) \subseteq \mathsf{SPACE}(s(n)^2) \quad (s(n)\ge\log n).$$

核心算法递归判断配置 $u$ 是否能在至多 $2^k$ 步内到达 $v$。枚举中间配置 $m$，递归检查两段长度 $2^{k-1}$ 的路径。递归深度为 $O(s)$，每层保存 $O(s)$ bit，因此总空间 $O(s^2)$；时间可以很大。

由此得到

$$\mathsf{NPSPACE}=\mathsf{PSPACE}.$$

该结论说明非确定性对多项式空间不增加计算能力，但模拟可能产生指数时间，不能推出 $\mathsf{NP}=\mathsf P$。

完备性与自然问题

下列 NL 与 P 完备性使用对数空间多对一归约，PSPACE 与 EXP 完备性使用多项式时间多对一归约。归约本身必须比目标资源限制足够弱：

• directed reachability 是 $\mathsf{NL}$-complete；
• circuit value problem 是 $\mathsf P$-complete；
• quantified Boolean formula 是 $\mathsf{PSPACE}$-complete；
• 有界确定性机器接受问题：输入 $\langle M,x,t\rangle$，其中 $t$ 用二进制编码，问 $M$ 是否在 $t$ 步内接受 $x$；它是 $\mathsf{EXP}$-complete。

$\mathsf P$-complete 问题被认为难以高效并行化：若它属于一致的 $\mathsf{NC}$，则在上述对数空间归约下可推出 $\mathsf P=\mathsf{NC}$。

时间与空间的权衡

算法可以用额外空间换取时间，也可以重复计算以节省空间。需要明确 tradeoff 的量化形式，例如

$$T(n)\cdot S(n)=\Omega(n^2)$$

只在指定模型和问题上成立。

pebbling game 将中间结果视为图上的 pebble，用于分析计算 DAG 的 time-space tradeoff。streaming 算法则限制可用内存和输入扫描次数，说明普通 RAM 上易解的问题在小空间单遍模型中可能需要近似或随机化。

本章自测

1. 非确定性时间为什么要求所有分支满足时间界？
2. 层次定理为什么需要 constructibility 条件？
3. 使用 $s(n)$ 空间的判定机为何可在指数时间内模拟？
4. Savitch theorem 为什么不会推出 $\mathsf P=\mathsf{NP}$？
5. $\mathsf P$-complete 与 NP-complete 分别对应什么限制？