【算法分析与设计】第43篇：空间复杂度类与Savitch定理
在前面的篇章中，我们的注意力几乎全部集中在时间效率上：算法运行需要多少步？问题的固有难度是否可以用多项式时间刻画？然而，算法消耗的另一种资源——内存空间——同样有其独立的复杂度理论体系。更关键的是，空间复杂度类之间的关系远比时间复杂度类之间的关系清晰：我们不知道P是否等于NP，但我们确切地知道PSPACE等于NPSPACE。这一结果由Walter Savitch于1970年证明，是计算复杂性理论早期最优雅的成果之一。
一、空间复杂度的度量模型
空间复杂度度量的是图灵机在计算过程中使用的纸带格子数量。对于确定性图灵机 MM，其在输入 xx 上的空间消耗sM(x)sM(x) 定义为读写头在计算过程中访问过的不同纸带格子的总数。与时间复杂度不同，空间复杂度的度量约定将输入所占的空间排除在外——输入是“只读”的，算法只需为额外的工作空间付费。这一约定使得讨论亚线性空间（如 O(logn)O(logn)）的算法成为可能——若连输入空间一并计入，则任何读取完整个输入的算法至少消耗线性空间，亚线性空间类便无意义。
基于此约定，定义空间复杂度类。设 s(n)s(n) 为空间上界函数。
SPACE(s(n))={L∣∃ 确定性图灵机 M 判定 L,且 sM(x)≤s(∣x∣)}SPACE(s(n))={L∣∃ 确定性图灵机 M 判定 L,且 sM(x)≤s(∣x∣)}
NSPACE(s(n))={L∣∃ 非确定性图灵机 M 判定 L,且 sM(x)≤s(∣x∣)}NSPACE(s(n))={L∣∃ 非确定性图灵机 M 判定 L,且 sM(x)≤s(∣x∣)}
最重要的空间复杂度类按空间上界的阶数划分。L（对数空间）：L=SPACE(logn)L=SPACE(logn)，即仅使用 O(logn)O(logn) 个额外工作纸带格子的确定性算法所能判定的语言类。NL：NL=NSPACE(logn)NL=NSPACE(logn)，L的非确定性对应物。PSPACE：PSPACE=⋃kSPACE(nk)PSPACE=⋃kSPACE(nk)，多项式空间可判定的语言类。NPSPACE：NPSPACE=⋃kNSPACE(nk)NPSPACE=⋃kNSPACE(nk)。
二、L与NL：亚线性空间的威力与局限
对数空间是亚线性空间的典型代表。O(logn)O(logn) 个格子足以存储有限个指针（指向输入位置的索引）和固定数量的计数值。但这也意味着算法无法将整个输入复制到工作区中——它必须在对输入流的“局部访问”中完成计算。
属于L的问题举例：判断一个无向图是否连通。算法只需在图上执行DFS，将当前顶点编号和探索状态记录在工作带上。顶点编号占用 ⌈logn⌉⌈logn⌉ 位，至多维护常数个这样的指针，总空间 O(logn)O(logn)。
属于NL的问题举例：判断一个有向图中是否存在从 ss 到 tt 的路径。非确定性算法可以从 ss 出发，每一步非确定性地猜测下一顶点，同时用一个计数器限制步数不超过 nn（避免环导致无限循环）。仅需存储当前顶点编号和计数值，空间 O(logn)O(logn)。这一问题的确定性对数空间算法是否存在的问题，称为L vs. NL问题，至今未解。
L与NL的已知关系为：L⊆NL⊆PL⊆NL⊆P。第一个包含关系是平凡的，第二个包含关系的成立是因为对数空间非确定性图灵机的格局数最多为多项式（状态数 ×× 工作带内容可能数 ×× 输入头位置可能数 =O(1)×nO(1)×O(logn)=nO(1)=O(1)×nO(1)×O(logn)=nO(1)），可以构造格局图并在多项式时间内搜索接受路径。
三、Savitch定理：确定性与非确定性空间的坍缩
Savitch定理是空间复杂度理论中最令人振奋的结果之一。其陈述极为简洁：
定理（Savitch, 1970）：对于任意满足 s(n)≥logns(n)≥logn 的空间可构造函数 ss，有
NSPACE(s(n))⊆SPACE(s(n)2)NSPACE(s(n))⊆SPACE(s(n)2)
其直接推论是：
PSPACE=NPSPACEPSPACE=NPSPACE
即多项式空间下，非确定性不增加任何额外的判定能力。这与时间维度的P vs. NP悬案形成了鲜明对比——空间的平方代价就足以消除非确定性，而时间维度上我们甚至不知道是否能用多项式代价消除非确定性。
证明：设 MM 为一台在 s(n)s(n) 空间内运行的非确定性图灵机。目标是构造一台确定性图灵机判定同样的语言，且空间消耗为 O(s(n)2)O(s(n)2)。
核心思路是基于可到达性测试的分治递归。考虑 MM 的格局图：顶点为 MM 的所有可能格局，边为合法的一步转移。MM 接受输入 xx 当且仅当在格局图中存在一条从初始格局 cstartcstart 到某个接受格局 cacceptcaccept 的路径，且路径长度至多为 2O(s(n))2O(s(n))（因为格局总数为此量级，路径长于此则必有环路）。
定义递归过程 Reach(c1,c2,t)Reach(c1,c2,t)：判断是否存在一条从格局 c1c1 到格局 c2c2 的路径，长度不超过 tt 步。
若 t=1t=1，直接检查 c1=c2c1=c2 或 c1c1 在一步内可达 c2c2。此检查仅需 O(s(n))O(s(n)) 空间——比较两个格局的每个分量。
若 t>1t>1，枚举所有可能的中间格局 cmidcmid（所有可能格局的总数为 2O(s(n))2O(s(n))）。对每个 cmidcmid，递归调用 Reach(c1,cmid,⌈t/2⌉)Reach(c1,cmid,⌈t/2⌉) 和 Reach(cmid,c2,⌊t/2⌋)Reach(cmid,c2,⌊t/2⌋)。若两者皆返回“真”，则返回“真”。
这一递归过程的深度为 logt=O(s(n))logt=O(s(n))。每层递归需要在调用栈上保存当前的 c1,c2,tc1,c2,t 和枚举中的 cmidcmid，每次存储格局消耗 O(s(n))O(s(n)) 空间。递归深度 O(s(n))O(s(n)) 乘以每层开销 O(s(n))O(s(n))，总空间为 O(s(n)2)O(s(n)2)。
初始调用为 Reach(cstart,caccept,2c⋅s(n))Reach(cstart,caccept,2c⋅s(n))（cc 为某个常数）。此过程确定性地判定是否存在接受计算路径，且总空间 O(s(n)2)O(s(n)2)。证毕。
Savitch定理在亚线性空间的推论同样重要：NL⊆SPACE(log2n)NL⊆SPACE(log2n)。这表明NL与L之间的差距至多为对数平方因子——远小于P与NP之间可能存在的指数鸿沟。
四、对数空间归约与NL完全性
与时间复杂度的归约类似，空间复杂度也有相应的归约概念。但因所涉及的空间预算极小，归约的要求更为严格。
函数 f:Σ∗→Σ∗f:Σ∗→Σ∗ 是对数空间可计算的，若存在一台确定性图灵机，对于任意输入 xx，能在仅使用 O(log∣x∣)O(log∣x∣) 个额外工作格子的条件下，在输出带上写出 f(x)f(x)（输出带为只写，不计入空间消耗）。对数空间归约记为 ≤L≤L。若 A≤LBA≤LB，则 B∈L⇒A∈LB∈L⇒A∈L，且 B∈NL⇒A∈NLB∈NL⇒A∈NL。
一个问题 LL 是NL完全的，若 L∈NLL∈NL 且任意 L′∈NLL′∈NL 满足 L′≤LLL′≤LL。
有向图的可到达性问题是NL完全的原型问题。给定有向图 GG 和顶点 s,ts,t，判断是否存在从 ss 到 tt 的有向路径。该问题属于NL（如前所述），其NL完全性的证明类似于Cook-Levin定理的空间版本：将任意NL机器的格局图编码为有向图，将接受判定归约为可到达性。可到达性问题的NL完全性意味着：若可到达性问题属于L，则L = NL。
五、已知的复杂度类关系
综合目前已知的结果，各空间与时间复杂度类之间的关系如下：
L⊆NL⊆P⊆NP⊆PSPACE=NPSPACE⊆EXPTIMEL⊆NL⊆P⊆NP⊆PSPACE=NPSPACE⊆EXPTIME
其中，已知至少有以下不等式是严格的：L⊊PSPACEL⊊PSPACE（由空间层次定理保证），P⊊EXPTIMEP⊊EXPTIME（由时间层次定理保证）。但以下包含关系是否严格仍然是开放问题：L vs. NL、NL vs. P、P vs. NP、NP vs. PSPACE。我们不知道其中任何一个等式是否成立，但已知若 P = NP，则 NPSPACE = PSPACE 早已成立——这揭示了空间与时间维度复杂度类结构之间的深层差异。
六、总结与展望
空间复杂度理论中，Savitch定理以其简洁优美的证明，成为确定性模拟非确定性的典范。它告诉我们：在空间资源的消耗上，非确定性带来的额外能力最多仅平方于确定性——我们确切地知道PSPACE等于NPSPACE。这与时间维度上P vs. NP的悬而未决形成强烈的理论反差。
对数空间类L和NL则展示了亚线性空间算法的可能性与局限。有向图可到达性作为NL完全问题的发现，为理解亚线性空间计算的能力边界提供了核心锚点。
将时间与空间统一考虑，引出了更深层的问题：随机化在空间受限计算中的力量如何？我们在第23篇中讨论了时间维度上的随机化算法——拉斯维加斯与蒙特卡洛。下一篇，我们将把随机化引入空间维度，讨论RP、BPP等随机化时间类，以及BPL（随机化对数空间）类的定义和已知的去随机化结果，进一步丰富我们对计算能力边界的理解。