形式陈述

复杂度类 $\mathrm{L}$ 由可被确定性图灵机使用 $O(\log n)$ 工作空间判定的语言组成。输入带只读、工作带可读写、输出或接受状态不计入工作空间；机器仍可使用多项式时间，因为只有多项式多个不同配置，若判定器重复配置就会循环。常数因子和合理机器模型不改变该类。

直觉

对长度为 $n$ 的输入，只能保存常数个顶点编号、计数器或指针，不能把整个输入复制到内存；算法必须反复扫描输入并复用极少状态。

例子与边界

判断一个字符串是否为回文可用两个 $O(\log n)$ 位索引反复读取输入，因此在 $\mathrm{L}$ 中。无向 $s$–$t$ 可达性也属于 $\mathrm{L}$，但其证明远非简单 DFS，因为显式访问集合需线性空间。定义中的对数空间通常要求 $n\ge 2$，以 $max(1,\log n)$ 处理小输入。

推论与应用

$\mathrm{L}\subseteq \mathrm{NL}\subseteq \mathrm{P}$。对数空间归约能够流式生成输出，因而比多项式时间归约更精细；它常用于描述解析、图遍历和电路求值中的低内存计算。

参考资料

• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009，Ch. 4, deterministic space complexity and logspace。
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，Ch. 8, space complexity and class L。