如果你和我一样是先啃时间复杂性再翻到空间复杂性这一章很大概率会有点不适应前面还在不停比大小、分多项式还是指数级到了第八章突然要换个视角把“工作带上的格子数”当成主角。但空间复杂性恰恰是复杂性理论里最容易和实际系统产生对应关系的一块——你在写递归程序时担心栈溢出本质上就是在担心空间复杂度你在设计缓存、内存映射、数据库索引时考虑“到底要存放多少中间状态”也是空间复杂度问题。这一章学完你会发现之前那些看似抽象的语言类、归约、完全性突然有了很具体的工程味道。这篇笔记按我自己的授课和复习经验整理从基本定义讲到对数空间、NL、空间层级定理再到 PSPACE 完全性最后留下一些我在教与学中反复踩过的坑希望能帮你把这一章读薄也把概念间的逻辑链条接上。1. 为什么空间复杂性能自成一大章1.1 从时间资源到空间资源的视角切换计算复杂性理论关心资源最常见的是时间和空间。时间复杂性是我们熟悉的一台确定性图灵机跑完整个输入消耗的步数是多少。空间复杂性则换成了“工作带上有多少个格子被写过”。初次接触这个定义的人往往有一个误解以为空间就是输入占用的存储比如一个长度为 n 的字符串空间就是 n。实际并非如此。图灵机的空间计算里输入带是只读的不计入空间成本真正计入的是机器为了计算而临时开辟的工作带。这就好比你做一道数学题时题目写在稿纸上不算你用掉的稿纸真正算数的是你为了演算打的草稿用了多少格子。这个定义上的差异带来一个很直接的后果时间是一次性消费而空间可以重复使用。时间花掉了就没了工作带上的格子却可以被擦掉、重新写入、再一次使用。因此空间复杂度的直觉判断不能照搬时间的直觉。一个算法就算跑了很多步只要它反复使用同一小段工作带它的空间需求仍然可能很小。这个“格子复用”的思想在后面理解那些看似违反直觉的结论时特别关键。1.2 基本定义与约定书面上我们用 SPACE(f(n)) 表示那些存在一台确定性图灵机能在 O(f(n)) 个工作带格数内判定的语言集合类似地NSPACE(f(n)) 是使用非确定性图灵机在 O(f(n)) 空间内判定的语言集合。这里的 f(n) 通常要求满足一定的正则性条件比如至少是线性可计算的并且本身要能简单计算出来否则连“分配这么多空间”都无法保证。实际讨论时大家不会抠到每一个常数因为空间复杂度也是在大 O 意义下比较的两个常数之差在干系上常常可以忽略。一个很容易忽略的细节是空间界通常被要求“可构造”。就是说图灵机需要能在运行中计算出当前输入的 n并且在不超界的情况下“画出”自己的空间上限。为什么这样要求因为空间层级定理、对角化构造都要靠“我自己要限制自己在这么多格子里运行”这种自我指涉。如果 f(n) 本身都算不出来机器的控制逻辑就无从谈起。教材里默认这些函数满足空间可构造但做题时偶尔会遇到“为什么这里要强调可构造”的疑问答案就在这里。另外我建议你把“输出不算空间”这个约定也记住。有些资料里图灵机会有一个只写输出带写输出带的长度不计入空间成本。这种简化其实很合理如果一个算法只是要把答案写出来那么回答的长度本身不代表算法难度重要的是生成答案所需要的中间存储。考试里常见的问题是“这个算法空间复杂度到底是 O(n) 还是 O(1)”多数时候答案的分歧就出现在有没有把输出带算进去。2. 对数空间类别 L 与 NL小空间里的大世界2.1 对数空间到底在算什么当我们把空间限制压到极低低到 O(log n)会得到两个重要的类L 和 NL。L 是确定性图灵机用对数空间就能判定的语言类NL 是使用非确定性图灵机在对数空间内判定的语言类。对数空间听起来微不足道因为 n 个物品本身就要占 n 个格子你怎么能只靠 log n 的空间来处理它们关键在于“位置”和“指针”。对数空间足够记录几个计数器、几个指针、一个当前状态编号或者一个图节点的编号。也就是说你没法把整个输入复制进工作带却可以记录“我现在看到输入的第几个字符”“当前访问到第几个节点”“已经走了多少步”。这很像你在超级大的图书馆里只带一张便签纸便签纸上没法抄写整本书却可以写“第 3 排第 7 本第 214 页”这样的索引。通过索引和指针你可以在只读的输入带上任意来回扫描而不是把它背下来。这个“只带指针”的思路正是对数空间算法的核心。我们在实际工程里也能找到类似的影子处理超大规模数据时内存里装的不是数据本身而是指向磁盘块的偏移量遍历一个巨型文件时你不需要在内存里展开整个文件只需要一个文件指针。这样思考对数空间就不是一种数学上的奇技淫巧而是现实中“流式”“指针式”处理的抽象化。2.2 s-t 连通性NL 的代表问题想要理解一个复杂性类最直接的方法是看它的代表问题。对于 NL最重要的是有向图 s-t 连通性也就是给定一个有向图和两个顶点 s、t问是否存在一条从 s 到 t 的路径。这个问题属于 NL每次猜一个顶点 v把当前顶点更新为 v同时用计数器限制步数不超过顶点数 n这样只需要记录当前顶点、计数器和一个临时缓冲空间 O(log n)。如果路径存在非确定性机器总有一条分支能正确猜出整条路如果不存在所有分支都会失败。也许有人会问路径长度可能达到 n只记录“当前顶点”怎么保证不绕圈答案是对数空间里我们用计数器控制最多走 n 步。如果存在一条简单路径它的长度顶多 n-1所以走 n 步以内如果没有到达 t就可以安全地拒绝。这个细节是我建议初学者记下来的因为很多人在模拟非确定性时总觉得需要把整个路径存下来结果做不出 NL 的证明。真实非确定性机器并不需要一次给出整个路径它只是并行地“尝试”各种选择因此空间账单上只需要写当前选择的顶点和计数器的长度也就是 O(log n)。顺带提一个扩展无向图的 s-t 连通性是否也属于 L这个问题比看起来复杂。后来被证明与一种称为“适定对数空间”的类有关不过标准教材里不会展开太多。你只需要记住有向版本代表 NL无向版本与 L 的关系是另一个值得留意的结果因为它体现了“非确定性”和“对称性”之间的差异。2.3 对数空间归约为什么特殊在时间复杂性那一章我们习惯了多项式时间归约如果能用多项式时间把 A 转成 B那么 A 的难度不超过 B。到了空间复杂性归约的成本标准也要跟着改。通常采用对数空间归约存在一个对数空间可计算的函数 f使得 x 属于 A 当且仅当 f(x) 属于 B。这个函数虽然是逐位输出的但输出 f(x) 的长度可能达到多项式级因为它用的是“对数空间工作带”而输出带不计空间。为什么归约本身要用对数空间因为如果你允许归约用多项式时间或多项式空间那么归约的计算能力太强会把很多类压扁失去“标尺”的作用。对数空间则小到不会破坏被归约语言本身的复杂度小到能保证“L 中的问题不借助大空间归约跑到 NL 头上去”。你可以类比看用翻译器把英文材料译成中文再判断难度如果这个翻译器本身是一台超级计算机那什么题目都能被它变成容易题只有翻译器本身也受限时翻译的结果才有比较意义。3. 空间换时间的模拟构造3.1 非确定性引入的额外“猜测权”空间复杂性里最让人惊讶的一个事实是非确定性和确定性之间的差距不像时间复杂性里表现得那么“大”。在时间世界里我们有 P 与 NP 这个大问题悬而未决没人知道非确定性是否让计算快出好几个量级。但在空间世界里一个经典构造却告诉我们对于足够大的空间界非确定性并没有带来指数级的差异至少在同阶量级上NSPACE(f(n)) 被包含在 SPACE(f(n)²) 里。先别急着背结论来看思路。一台非确定性机器 M 在 O(f(n)) 空间内运行它的瞬时描述状态、工作带内容、带头位置数量是多少工作带长度 O(f(n))带上每个符号有固定常数种选择再加上状态数和带头位置总组态数大致是 2^{O(f(n))}。这就把 M 的行为压缩进一张有向图每个组态是一个顶点边表示一步转移。问题“M 是否接受输入 x”就变成了“初始组态能否到达某个接受组态”。这个转化并不复杂复杂的是如何在空间限制内回答“能否到达”。这里就轮到空间换时间的核心思想登场了。3.2 构造要点用一个递归函数在中间分组态上搭桥要判断两个组态 c、d 是否能在 2^i 步内互相到达可以拆成是否存在一个中介组态 m使得 c 能在 2^{i-1} 步内到达 m同时 m 能在 2^{i-1} 步内到达 d。这个递归过程每一步都要临时存放一个 m递归深度是 i而 i 大约等于 log(2^{O(f(n))})也就是 O(f(n))。每层递归存一个组态需要 O(f(n)) 空间所以整体空间是 O(f(n) × f(n)) O(f(n)²)。注意这里的时间代价是完全被忽略的因为递归会展开成一棵巨大的搜索树时间可能暴涨到 2^{O(f(n))}但空间账单却只是多项式级别。这正好体现了“空间可以重复使用”的反直觉之处同一个中间变量 m在每一层递归里都被反复覆盖、反复使用并没有像时间那样累计叠加。我见过不少同学第一次看到这个证明时会疑惑“递归不是要保存现场吗”关键就在工作带上的组态被覆盖后旧内容已经不需要保留而递归返回时只需要继续使用上一层的那份数据。这里有一个必须注意的边界这个构造里被模拟的机器必须保证在 f(n) 空间内运行因此所有组态的长度都被限制在 O(f(n))。中介组态 m 的存储不会超出这个上界。这看起来像循环论证但正说明“空间可构造”和“机器自限空间”是构造的前提。教材里通常把 f(n) 限定为至少 log n 且可构造就是为了让这些论证顺滑。3.3 推论PSPACE NPSPACE把 f(n) 取为多项式立即得到 PSPACE NPSPACE。这是整个空间复杂性章节里最耀眼的结果之一。它不依赖于任何未解决问题不像 P 与 NP 那样悬而未决。原因在于组态图的大小是 2^{多项式}递归深度是多项式中间变量存整个组态也是多项式所以非确定性带来的“并行猜测”可以被确定性的“深度搜索”模拟掉空间只翻平方。我给学生的直觉说法是非确定性相当于同时往所有方向走时间上它能创造出指数级分支可空间上每个分支共享同一个工作带不严格来说每个分支有自己的组态。但当我们用“到达性”去看问题时所有路径只是图上的边搜索这些路径只需要存“当前在哪个顶点”和“还要探索多少步”。顶点数量虽然巨大但存储一个组态的代价只是多项式。换句话说空间资源衡量的更接近“你最多需要同时记住多少东西”非确定性给你的是“选择权”而不是“记忆权”所以空间上赢不了太多。4. 空间层级定理空间给得越多能判定的东西越多4.1 从对角化到空间层级时间复杂性那里有一个时间层级定理空间这边也有对应的空间层级定理如果 f 和 g 都是空间可构造函数并且 f(n) 是 o(g(n))那么 SPACE(f(n)) 是 SPACE(g(n)) 的真子集。换句话说多给一点可构造的空间就一定能多判定一些新的语言。证明思路仍然是经典的对角化构造一台机器 D它在输入 x 上模拟“第 x 台机器在相同输入上的运行”但是故意把结果取反。为了让这种自我指涉成立D 需要在自己的空间界内完成模拟为此它必须把工作带划分出若干区域。因为 g 比 f 大得多D 可以用 g(n) 的空间去模拟一台只用 f(n) 空间的机器并在模拟结束后输出相反答案。这样任意一个需要 f(n) 空间的机器都不可能等于 D否则就会在输入 D 的编码时产生矛盾。这里有一个重要的前提被模拟机器如果试图超出 f(n) 空间D 要能检测到并直接判定它“不接受”或“中止”否则模拟会失控。由于我们讨论可构造函数D 知道 f(n) 的边界可以在每次写带时检查计数器。工程上这就是“沙箱”的概念我限制你只能在这块内存里跑一旦越界就把你杀掉。对角化程序里充满了这种自我监控逻辑。4.2 层级定理给我们的直觉空间层级定理最直接的含义是空间资源“严格分层”O(n) 空间能判定的东西严格多于 O(log n) 空间能判定的O(n²) 空间又严格多于 O(n) 空间。这和我们平时写代码的直觉一致——更大的缓存、更多内存原则上总能让你完成更复杂的计算。不过层级定理并没有告诉我们具体哪个问题真正需要这么多空间它是一种“存在性”的判断存在某些语言需要那么多空间。这和工程里“这个功能必须用多少内存”完全是两码事。实际算法分析还受到具体数据结构、编程接口、常数因子的影响空间层级定理只是理论上的天花板。另外值得留意的点是空间层级用的对角化并不能直接移植到 P 与 NP 的分离上因为多项式时间类之间互相包含很难用对角化分离它们而且我们不知道多项式时间机器是否足以等价模拟多项式时间的非确定性机器。层级定理“有效”恰恰是因为确定性机器可以直接模拟任意给定空间的机器并把空间限制写进程序里。空间的自限性在这里比时间更“听话”。5. 补封闭与计数构造NL coNL5.1 coNL 的疑问在代数里一个类的补类就是把语言集合改成其补集。比如 coNL 就是所有那些“补语言属于 NL”的语言集合。对于确定性类补运算很好处理把接受状态换一下即可。但对于非确定性类直接交换接受与拒绝状态并不正统因为非确定性机器可能在接受与拒绝之间都有分支交换状态会把“存在一条接受路径”变成“所有路径都拒绝吗”这种全称判断非确定性机器无法直接表达。于是问题来了NL 补集里有什么看起来 NL 与 coNL 可能完全不同。这个问题一直悬着直到一个有开创性的构造证明它们相等。这个结果在标准教材里经常被单独列出核心思想可以概括为“在非确定空间内用计数来消除全称判断”。5.2 组态计数与可达性要证明 NL coNL等价于证明有向图 s-t 不可达问题属于 NL。也就是说要让一台非确定性机器在 O(log n) 空间内判定“不存在从 s 到 t 的路径”。直接猜一条“不存在路径”是不可能的于是构造选择换一种方式先算出从 s 出发、在 k 步内能到达的顶点数再检查 t 是否在这些顶点里。算出“从 s 出发 k 步内能到达多少个顶点”听起来像是确定性计数问题怎么用非确定性做关键技巧是“猜测加验证”对每个顶点 v猜测它是否在 k 步内可达并通过递归地检查 v 在 k 步内是否真的可达来核实。为了核实又需要知道它在 k-1 步内可达的顶点数所以递归层层下推。整个递归深度最多 n 层但每层只保存当前顶点编号和计数器空间仍然是 O(log n)。这个构造的妙处在于它把“全称判断”每个顶点都不能通往 t转化为“存在性验证链”可以先猜测总数 C再逐个检查“不属于可达集”的顶点都不等于 t同时验证计数 C 与事实一致。如果猜测和验证一致机器就确信 t 不在可达集里。整个思考方式非常像概率检查里“证明者给出摘要、验证者抽查验证”的思路——你不需要自己列出所有证据只需要保证错误路径能被识别。5.3 为什么这让 NL 与 coNL 合流得到 NL coNL 后很多推论会立刻出现在你面前例如 NL 中的问题都存在对数空间的补算法再结合我们前面提的包含关系可以得到 L ⊆ NL coNL 以及 NL 的补封闭性。这个结果也给后来更多“猜测验证型”空间算法提供了模板在描述复杂性、逻辑刻画中都能看到它的影子。我个人的体会是这个定理比 PSPACE NPSPACE 更难直觉化。PSPACE NPSPACE 用的是组态图加模拟脑中有图就能想通NL coNL 则需要你在脑子里把“不可达性”转成“可验证的计数”没有经过几道习题的打磨很容易背完就忘。所以如果你学这一章时间紧张至少要在纸上亲手推一遍这个递归计数过程才算真正掌握。6. PSPACE 与 PSPACE 完全多项式空间的顶点6.1 PSPACE 为什么重要把目光拉回多项式空间得到一个巨大的复杂类 PSPACE。时间复杂性里的 P 与 NP 都包含在 PSPACE 中普遍认为 PSPACE 比它们大得多但严格包含关系并没有完全证明。由于 PSPACE NPSPACE所以它对于非确定性的容忍度比 P/NP 高很多这让它成为一个非常“结实”的类几乎各种资源难题都能放到 PSPACE 里。拿工程语言来说PSPACE 里的问题通常意味着“如果给你足够的内存你可以彻底搜索整个解空间”。这包括许多博弈问题棋盘上的最优策略判定、有限步数内的胜败结果都是 PSPACE 完全。它们和现实中的游戏 AI 有直接联系所以这一小节从来不缺谈资。6.2 一个典型的 PSPACE 完全问题量词布尔公式在时间复杂性那一章典型的完全问题是 SAT给定一个布尔公式问是否存在一组赋值让它为真。PSPACE 完全的代表则是“带量词的布尔公式”TQBF公式里不仅有 ∃还有 ∀更一般的写法是 ∃x1 ∀x2 ∃x3 ... φ(x1, ..., xn)问这个公式是否成立。为什么量词会让难度从 NP 跳到 PSPACE因为量词默认带来“博弈结构”。你可以想象成两个玩家轮流指定变量∃ 玩家想让公式最终为真∀ 玩家想让公式最终为假。每指定一个变量剩余的解空间就缩小一半而 PSPACE 能让你沿着这棵“赋值树”一路搜索到底。NP 只能处理“有一组赋值让公式为真”却无法表达“不管对手怎么选我都赢”这种全称与存在交替的命题。一旦出现 ∀我们就需要一个能处理整棵搜索树的空间而这正好落在多项式空间内。6.3 证明 PSPACE 完全性的一般套路要证明某个问题是 PSPACE 完全的照例分两步第一步是把它放进 PSPACE也就是给出一个多项式空间的算法第二步是找一个已知 PSPACE 完全问题通常是 TQBF对数空间归约到它。在实际习题里第二步往往最难因为归约需要把“机器运行过程”编码成目标问题的实例。归约的核心经常是用组态图把输入长度为 n 的 PSPACE 图灵机运行过程转成“两个玩家博弈”或“量词交替”的结构把“初始组态能否达到接受组态”编码成量词表达式。这里会再次出现“组态”这个概念。我发现学生反复卡住的地方是为什么量词的数量要等于空间的多项式次方而不是直接等于运行步数。原因是运行步数可能指数级但组态大小是多项式的所以量词只需要覆盖多项式个“阶段”每一层表示“某个时刻某个组态是否存在”。只要你接受了“组态可以压缩整个历史”PSPACE 完全性证明的思路就顺了。6.4 PSPACE、P、NP 与 L 的边界从包含关系看大家熟悉的链是 L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE。另外还知道 PSPACE ⊆ 指数时间并且空间层级定理告诉我们 PSPACE 严格包含在某种指数空间类中。但中间哪些包含是真包含哪些只是未知一定要分清。特别是 P 与 PSPACE 是否相等仍然和 P 与 NP 一样悬而未决。虽然直觉上大家相信 P ≠ PSPACE但这个结论至今没有证明。这部分内容背诵时很容易搞混我建议你画一张包含关系图然后把那些“已知严格”和“未知”分别标记复习时就更清楚。7. 常见问题与排查实录7.1 工作带上的格子到底怎么数很多练习题会让你计算某个算法的空间复杂度这时候最容易出错的地方是对“输入”和“输出”的处理。约定俗成的是输入带只读不计空间输出带只写也不计空间工作带上的格子计入。如果一个算法需要在输入上来回扫描那么扫描指针的数量要计入但指针所占的对数空间通常会被大 O 吸收。真正需要警惕的是那些看似常数实际会增长的对象比如保存了一个数组下标数组或者递归深度本身也要空间每个栈帧里还保存着局部变量。我自己的检查方法是把算法里所有“活着的变量”列出来每个变量的长度是多少然后问自己“在所有可能执行路径上同时存活的最大总长度是多少”。不需要计算那些已经不再引用的变量因为空间允许释放。你要是能把“同时存活”四个字刻进脑子里空间复杂度的估算就不会出现翻倍错误。7.2 递归与空间复用的糊涂账前面提过对数空间算法里的递归深度看起来是 log n但如果每一层都要拷贝一份大小为 n 的数组总空间立刻变成 n log n。这是初学者最常见的陷阱误以为递归深度只有 log n 就很安全忽略了每一层栈帧里的数据大小。分母是要看“栈帧大小 × 深度”而不是只看深度。反过来有时候递归从表面上看起来要记录很多中间状态但如果你只用一个可重新赋值的变量比如那类“覆盖式递归”栈帧里的数据就可以共享。我们在讨论空间换时间模拟定理时用的就是这种覆盖式技巧。写伪代码时我建议你在每个递归调用点旁边标出“这里需要多少新空间旧空间是否可以覆盖”这样不容易出错。7.3 归约方向与复杂类判断在做 PSPACE 完全性或 NL 完全性判断题时最容易出错的是一不留神把归约方向写反。你要证明 A 是某个类 C 完全的需要把已知的 C 完全问题归约到 A而不是把 A 归约到已知问题。方向错了只能说明 A 可能比 C 容易什么完全性也推不出来。还有一个细节对数空间归约本身是确定性计算输出可以很长但不能在归约过程中使用超过对数空间的工作带。有的同学写归约时直接生成一个指数长度的输出忘了检查工作带。实际上输出带不计空间生成超长输出是允许的只要计算每一段输出的指针和计数器只占对数空间。这个听起来矛盾但和定义是一致的做题时别被“输出很大”吓到。7.4 几个值得反复琢磨的边界案例第一个案例空集和全集都属于 L。它们显然不需要任何工作带空间直接根据输入判定接受或拒绝即可。这里容易忽略的是常数空间也是 O(1)而 O(1) 和对数空间的关系是 O(1) ⊆ O(log n)所以它们属于更小的类。第二个案例所有长度是偶数的字符串集合也属于 L只要用一个计数器在输入上扫描并判断最终奇偶即可。这个案例能帮你确认“对数空间计数器”的基本功。第三个案例判断一个二进制数是否质数目前已知属于 P但它在 L 还是 NL 里就复杂多了。这些边界案例不一定都出现在教材题集里但把它们放在一起对比能训练出判断“哪些信息只需要指针和计数器哪些信息必须要存整块数据”的直觉。直觉建立了后面再看空间复杂性里的构造就不那么晕了。7.5 把组态图当作万能钥匙如果你只能从这一章拿走一个工具我建议是“把计算过程看成组态图上的可达性问题”。这个工具不止在空间复杂性的证明里反复出现在很多算法设计里也是核心思路。当一个计算过程很难直接分析时试着列出它的所有可能状态把状态之间的转移看成边问题往往就变成“初始状态能否达到目标状态”然后你可以借用图论里的可达性、最短路径、连通分量等算法直觉。实际操作中组态图可能会指数级大所以你不可能真的建图。但理论的乐趣正在于此你不需要展开整张图而是用空间换时间地搜索它。对数空间算法和 PSPACE 算法本质上都在做这种压缩式搜索。理解这一点第八章的整体脉络就清楚了。我自己在讲空间复杂性时总喜欢跟同学说一句话时间复杂性是在卷“速度”空间复杂性是在卷“记忆”。速度很难无中生有但记忆可以被覆盖、被压缩、被共享所以空间类的结构比时间类更丰富也更好证明。你如果能把“覆盖”“计数”“组态图”这三板斧练熟不管考试还是做研究遇到新的空间复杂性结论都不会慌。