复杂度类 L

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

判断回文时，先扫描取得长度 $n$。然后依次取 $i=1,\dots ,\lfloor n/2\rfloor$，定位第 $i$ 位，暂存一个字符，再移动到第 $n+1-i$ 位比较；一旦不同便拒绝，全部相同则接受。位置计数器和 $n$ 各占 $O(\log n)$ 位，暂存字符只占常数空间。单个输入头来回移动可花 $O(n^2)$ 时间，却始终不需要保存整串，因此该语言属于 L。小输入统一以 $max(1,\log n)$ 处理。

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

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

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

流式输出不等于可以把输出免费读回。STCON 的 NL 完全性理路STCON 的 NL 完全性NL-completeness of STCON · Directed reachability is NL-complete有向图可达性在确定性对数空间多一归约下是 NL 完全问题。中的虚拟输入模拟只保存目标输入头索引，每次需要第 $j$ 位就从头重算归约输出到该位，同时保留目标机的工作区。输出长度为多项式，所以索引、重算区和目标工作区合计仍为对数空间；这补全了 L 在对数空间归约下的封闭性论证。

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