03 空间复杂性

空间复杂性(Space Complexity)

时间复杂性刻画的是计算所需要的时间资源。空间复杂性刻画的是计算所需要的空间资源。对于图灵机来说，空间指的就是所需要用到的纸带上的格子数（对于现在计算机来说，指的是内存（存储）单元的个数）。空间资源和时间资源有很大的区别，其中最重要的是：空间资源是可以重复使用的。我们可以在一个内存单元上写入，并在一段时间后擦除，重写上其它内容。一个需要指数时间的DFS算法所需要的内存空间也只是多项式的，因为DFS是在相同的内存上反复修改上面存储的值。

对于判定问题$L$，如果对于任意输入$x$，存在确定性图灵机$\mathbb{M}$使得计算$L(x)$时最多只用到工作带上的$C\cdot S(|x|)$个格子（$C$为常数），就称$L$的空间复杂度为$O(S(n))$，$S(n)$称为空间函数。注意，以上定义中强调“工作带”，我们不考虑输入带上本来就含有的$|x|$个格子。很多时候，工作带所需要的格子数远小于$|x|$。但是我们需要假定，图灵机要有能力追踪输入带上读写头的位置（不然这就是一个毫无章法的程序），因此我们至少需要一个长度为$\log |x|$的“计数器(counter)”。因此我们默认$S(n)\geq \log n$。

和时间复杂性类似，可以定义空间可构造函数：如果存在以$O(S(n))$的空间复杂度计算函数$1^n\to S(n)$的图灵机，就称$S(n)$是空间可构造的(space constructable)；如果存在恰好用$S(n)$个格子计算函数$1^n\to S(n)$的图灵机，就称$S(n)$是完全空间可构造的(fully space constructable)。在空间复杂性里，可以证明，空间可构造和完全空间可构造是等价的。

空间复杂性类

所有确定性图灵机在空间复杂度$O(S(n))$下可计算的判定问题构成空间复杂性类$\text{SPACE}(S(n))$。

对于判定问题$L$，如果对于任意输入$x$，存在非确定图灵机$\N$使得计算$L(x)$时，叠加态中的任何一条路径都只最多用到工作带上的$C\cdot S(|x|)$个格子，就称$L$在非确定图灵机下的空间复杂度为$O(S(n))$。所有非确定性图灵机在$O(S(n))$下可计算的判定问题构成空间复杂性类$\text{NSPACE} (S(n))$。

$\text{SPACE}(\log(n))$称为对数空间类，记为$\text{L}$。$\text{NSPACE}(\log(n))$称为非确定对数空间类，记为$\text{NL}$。$\bigcup\limits_{C>0}\text{SPACE}(n^C)$称为多项式空间类，记为$\text{PSPACE}$。$\bigcup\limits_{C>0}\text{NSPACE}(n^C)$称为非确定多项式空间类，记为$\text{NPSPACE}$。

容易发现，因为时间复杂性类$\text{NP}$中的问题都是多项式可验证的，所以尽管在确定性上“搜索”可能进行指数时间，却只需多项式的空间。因此$\text{NP}\subseteq \text{PSPACE}$。

对于任意空间可构造的函数$S(n)$，总有如下关系成立：$\text{TIME}(S(n))\subseteq$ $\text{SPACE}(S(n))\subseteq \text{NSPACE}(S(n))\subseteq \text{TIME}(2^{O(S_n)})$。第一个包含关系是因为，确定性图灵机每一步计算最多多写一格，因此$S(n)$的时间最多只能写$S(n)$格；第二个包含关系显然，因为确定性图灵机只是一种特殊的非确定性图灵机；为了证明第三个包含关系，可以引入configuration graph(格局图)的概念（此处待补充），构造格局图只需$2^{O(S(n))}$的时间，并且可达性只需图的遍历算法。

和时间复杂性类比，可以得到空间谱系定理，证明几乎是完全相同的：如果空间函数$f,g$是空间可构造的，并且$f(n)=o(g(n))$，那么有$\text{SPACE}(f(n))\subsetneq \text{SPACE}(g(n))$。