确定性空间复杂性类

确定性机器在给定输入上只有一条配置轨迹。空间界限制每个配置需要多少位，却不限制同一工作格可被重写多少次，因此一条小空间轨迹可以很长。若判定机再次到达完全相同的状态、输入头位置、工作头位置和带内容，之后的确定性演化会永久重复；总停机要求排除了这种回环。

与非确定性空间类公理库非确定性空间复杂性类Nondeterministic space class · NSPACE由非确定性图灵机在给定空间界内判定的语言集合。相比，DSPACE 不需要在多个后继中寻找接受路径。两者都按单条轨迹的工作空间峰值计费，但确定性配置图的每个节点至多有一个后继。

用对数空间判定回文 ​

输入 $x=x_0\cdots x_{n-1}$ 放在双向只读输入带上。机器先扫描一次，用二进制计数器得到 $n$；随后对 $i=0,1,\dots ,\lfloor (n-1)/2\rfloor$，反复扫描输入以读取 $x_i$ 与 $x_{n-1-i}$，只保存索引和一个待比较字符。两个索引都只需 $O(\log n)$ 位，因此工作空间为 $O(\log n)$，总时间可达 $O(n^2)$。

对 0110，机器依次核对外层 $0=0$、内层 $1=1$ 后接受；对 0100，第二对字符 $1\ne 0$，因而拒绝。这个算法以反复扫描换取小空间，具体展示了时间可以远大于空间。

配置数给出的时间上界 ​

固定长度为 $n$ 的输入后，一个 $O(s(n))$ 空间配置由有限状态、至多 $O(s)$ 个工作带符号、工作头位置和一个输入头位置组成。配置总数至多

当 $s(n)\ge \log n$ 时，这可吸收到 $2^{O(s(n))}$。确定性判定机不能重复配置，所以它的运行时间也至多为 $2^{O(s(n))}$。若低于对数空间，前面的 $n$ 因子不能直接吸收，模型细节便不可忽略。

递归栈和保存的迭代状态都属于工作空间；只有经过尾调用消除或显式复用后，才能从分析中删去。允许读回输出同样会提供额外存储，因此不属于这里的标准模型。

DSPACE 对补封闭：确定性判定机交换接受与拒绝即可。它也对并与交封闭，因为可顺序运行两个判定器并复用工作带，总空间取两者较大者加低阶控制信息。

典型缩写包括

空间层级定理公理库空间层级定理Space hierarchy theorem在适当空间可构造性条件下，更多渐近空间严格提升可判定语言能力。在可构造预算下证明更多空间确实能判定更多语言；Savitch 定理则比较本页与非确定空间的能力。任何 $O(t(n))$ 时间判定机至多访问 $O(t(n))$ 个工作格，所以还有 $\mathrm{DTIME}(t(n))\subseteq \mathrm{DSPACE}(t(n))$。