形式陈述

$\mathrm{DSPACE}(s(n))$ 包含能由确定性图灵机在每个长度 $n$ 输入上使用至多 $O(s(n))$ 个工作带单元判定的语言。输入带通常只读且不计入空间，输出与有限控制也按约定处理；机器必须停机。只要配置总数有限，重复配置会导致循环，因此空间 $s$ 的停机计算可有指数于 $s$ 的时间。常见类包括 $L=\mathrm{DSPACE}(\log n)$ 与 $PSPACE=\bigcup _k\mathrm{DSPACE}(n^k)$。

直觉

空间衡量同时需要保留多少信息，而非总共写过多少位置；工作单元可以反复利用，所以很小空间的算法也可能运行很久。

例子与边界

图可达性可用保存当前顶点和计数器的非确定对数空间算法处理。深度优先递归若存整条路径可能用线性空间。输入带不计费使 $o(n)$ 空间有意义；若把输入存储全部计入，所有非空问题会平凡需要 $\mathrm{\Omega }(n)$ 空间。DSPACE 与内存峰值近似，但具体机器编码、随机访问和字长需要在精细分析中明确。

推论与应用

空间类用于研究可复用内存、Savitch 定理和空间层级，也解释为何某些指数时间搜索仍能以多项式空间完成。

参考资料

• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009，Chs. 1–8。
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，Chs. 0–10。