复杂度类 L

L 只允许 $O(\log n)$ 个工作位，却可反复读取只读输入，因此它不是“只能看对数个输入字符”。对数空间足以保存常数个顶点编号、输入位置、计数器或指针和有限状态，但不能把整个输入复制到内存，也无法显式存储长度为 $n$ 的访问数组；算法必须反复扫描输入并复用极少状态。由于可用配置数是多项式级，确定性对数空间停机计算可限制在多项式步内。

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

无向图 $s$-$t$ 可达性属于 L（Reingold 定理）；更基础的例子是比较两个二进制数或扫描输入计算模固定常数的余数，只需对数甚至常数工作空间。深度优先搜索若保存整个递归栈和 visited 集通常使用线性空间，不能直接作为 L 算法。

输出带通常只写不读且不计入工作空间，否则算法可把无限记忆藏在输出中。输入头位置是否计入配置、机器是否必须停机等细节需采用标准模型，但合理变体通常只造成常数因子差异。

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

空间复杂度公理库空间复杂度Space complexity计算在输入长度函数下使用的工作存储单元数量。 的可复用性使 L 能做比同等“存储位数”看起来更多的计算。它包含于 NL公理库复杂度类 NLComplexity class NL · Nondeterministic logspace可在非确定性对数空间内判定的语言类。 和 P公理库复杂度类 PP · Polynomial time能由确定性算法在输入长度的多项式时间内判定的语言集合。，并与 logspace-uniform NC公理库复杂性类 NCNick's Class · NC由多项式规模、复对数深度的统一布尔电路族判定的高度并行语言类。 电路、流式算法和归约计算紧密相连。