logspace

定义

在计算复杂度理论中，logspace 最常指确定型对数空间类 L，也写作 LSPACE 或 DLOGSPACE，它是确定型图灵机在对数级工作空间内可以判定的问题集合。这类机器设有 2 条带：一条只读的输入带用于存放输入，另一条可读可写的工作带用于计算，空间限制只针对工作带，输入长度记为 n。形式化地，DSPACE(f(n)) 表示确定型图灵机在 O(f(n)) 空间内可判定的语言类，NSPACE(f(n)) 为非确定型图灵机的对应版本，于是 L = DSPACE(log n)；非确定型对数空间类记作 NL（又称 NLOGSPACE），即 NSPACE(log n)。^[1][2][3]

对数空间指的是可写存储空间的大小与输入规模呈对数关系的空间种类，这类空间只够存放常数个指向输入位置的指针、若干个计数器与少量布尔标志，许多基本算法正是按这种用法组织内存的。由定义可直接得到 REG ⊆ L ⊆ NL ⊆ P，其中 REG 是正则语言类，P 是确定型多项式时间可判定的问题类。更紧的包含关系还包括 NC¹ ⊆ L ⊆ NL ⊆ NC²。^[2][1]

原理

对数空间机器无法把整个输入保存在内存里，但 log n 位二进制数已经足以表示 0 到 n−1 之间的下标，因此它可以记住常数个输入位置指针，并在需要时反复扫描输入来完成计数与比较。由此，只需常数个计数器或指针就能求解的问题通常属于 L，只需常数个计数器或指针就能验证解的问题通常属于 NL。^[4][1]

把非确定型图灵机的每个格局视为顶点、把一步转移视为有向边，就得到该机器的配置图。对数空间机器的不同格局数目只有多项式多个，机器接受输入当且仅当配置图中存在从初始格局到接受格局的路径，所以 NL 包含在 P 之中。有向图的可达性问题（STCON，也称 PATH）在对数空间归约下是 NL-完全的，图是否强连通、2SAT 等同样被证明为 NL-完全问题。^[5][6]

由于 L 与 NL 都包含在 P 内，用多项式时间归约已无法区分这两个类内部的难度，因此 NL-完全性改用对数空间归约来定义：归约工作由一个带有只读输入带、只写输出带和 O(log n) 工作带的确定型图灵机完成。确定性空间与非确定型空间的关系由Savitch 定理描述，即对任意满足 s(n) ≥ log n 的空间函数都有 NSPACE(s(n)) ⊆ DSPACE(s(n)²)，取 s(n) = log n 便得到 NL ⊆ DSPACE(log² n)。^[4][7]

graph LR

NC1 --> L

L --> NL

NL --> P

P --> NP

NP --> PSPACE

发展历程

对数空间类的研究是随着空间复杂度理论的建立而展开的。1964 年，Kuroda 提出非确定型线性空间类（即上下文相关语言类）是否对补运算封闭的问题，该问题与 NL 的补封闭性密切相关，此后长期悬而未决。1970 年，Walter Savitch 证明了对满足 s(n) ≥ log n 的空间函数有 NSPACE(s(n)) ⊆ DSPACE(s(n)²)，从而把非确定型对数空间类放进 DSPACE(log² n)。^[8][7]

1982 年，Harry Lewis 与 Christos Papadimitriou 为安放无向图连通性定义了对称图灵机与对称对数空间类 SL，证明 USTCON 对 SL 完全，并给出 L ⊆ SL ⊆ NL。1987 年至 1988 年，Neil Immerman 与 Róbert Szelepcsényi 各自独立证明了对任意适当空间函数都有 NSPACE(s(n)) = co-NSPACE(s(n))，其对数空间特例即 NL = coNL，这一结果同时回答了 Kuroda 的提问。^[9][8][10]

20 世纪 90 年代之后，无向图连通性的空间上界被逐步压低：Nisan、Szemerédi 与 Wigderson 给出了使用 $O(\log^{3/2} n)$ 空间的确定性算法，Armoni、Ta-Shma、Wigderson 与 Zhou 在 2000 年进一步改进到 $O(\log^{4/3} n)$。2004 年，Omer Reingold 借助扩展图的构造证明 USTCON 可以在确定型对数空间内求解，等价于 SL = L；同期 Trifonov 也独立给出了 $O(\log n \log\log n)$ 空间的算法。^[11][9][12]

应用

对数空间类刻画的是内存极小条件下的可计算问题，最直接的用途是各类图连通性与可达性判定，例如判断无向图中两个顶点是否连通、有向图中是否存在一条路径、一张图是否为强连通图，以及 2SAT 的判定。^[9][6]

在数据库领域，如果把数据规模看作输入规模，那么用关系代数等方式表达的关系数据库查询具有对数空间的数据复杂度，也就是说回答一个固定查询所需的空间随数据规模对数增长；在信息完整（不含空值）的情形下，这类查询问题落在 L 中。对数空间归约同样是把 P-完全问题与 NL-完全问题区分开来的常用工具，例如电路求值问题被证明在对数空间归约下是 P-完全的。^[1][13]

局限

对数空间机器只能保存常数个指针和计数器，无法在工作带上容纳完整输入、较大的数据结构或很深的调用栈，只能通过多次重读输入来补偿。这一限制也影响到归约的复合：两个对数空间归约首尾相接时，不能把前一个归约产生的多项式长输出整体写出，必须在使用时按需重新计算，否则空间会超出对数界。^[1][6]

该领域仍有多项基本问题没有答案。L 与 NL 是否相等尚未解决，其等价问法是有向图可达性能否在确定型对数空间内判定；L 与 P 是否相等同样未知，这两个问题常与 P 和 NP 的关系相提并论。^[2][1]此外，Savitch 定理给出的算法虽然只需 O(log² n) 空间，运行时间却可能达到超多项式级别，在多数实际场景中并不实用。^[9]还有一点值得注意：L 中每个非平凡问题在对数空间归约下都与其他问题相互完全，因此刻画 L-完全性往往要采用比对数空间更弱的归约，最常用的是一阶归约。^[1]

参见

• NL (复杂度类) —— 非确定型对数空间类，是 logspace 的非确定型版本，二者是否相等尚未解决。

• Savitch 定理 —— 给出 NSPACE(s(n)) ⊆ DSPACE(s(n)²)，由此得到 NL 的空间上界。

• Immerman–Szelepcsényi 定理 —— 证明非确定型空间类对补运算封闭，其特例为 NL = coNL。

• 对数空间归约 —— 定义 NL-完全性所使用的归约方式。

• SL (复杂度类) —— 对称对数空间类，已被证明等于 L。

• P (复杂度类) —— 确定型多项式时间类，包含 NL。