空间复杂性

与时间复杂性类似，我们可以如下定义空间复杂性：
定义.
(1) 设离线DTM u,若对所有的输入，u总停机，且把u关于输入w的计算中，在每一条带上占用的方格的最大值记为\(s_u(w).\)
(2) 称\[s_u(n)=\max\{s_u(w)|w\in A^*,|w|\le n\}\]为u的空间复杂度。
(3) 如果\(s_u(n) = O(s(n))\), 称\(s(n)\)是\(u\)的空间复杂度上界，u是s(n)空间界限的。
(4) 空间复杂性类\(SPACE(f(n))\)和\(NSPACE(f(n))\)分别定义为L是被DTM(NTM) u判定的语言，且u是\(f(n)\)空间界限的。

一些常用的空间复杂性类定义如下：
(1) \(L=DSPACE(\log n)\);
(2) \(NL = NSPACE(\log n)\);
(3) \(PSAPCE = \bigcup_{k} DSPACE(n^k)\);
(4) \(NSAPCE = \bigcup_{k} NSPACE(n^k)\);
(5) \(EXPSPACE = \bigcup_{k} DSPACE(2^{O(n^k)})\);
(6) \(NEXPSPACE = \bigcup_{k} NSPACE(2^{O(n^k)})\);

Savitch定理刻画了NTM与DTM的空间复杂度关系。我们先引入空间可构造性的概念。

定义. 设全函数\(f:N\to N.\) 如果存在一\(f(n)\)空间界限的离线DTM u，对每一个输入\(1^n\), u输出\(f(n)\)的二进制表示，称f是空间可构造的。
相应地，我们有时间可构造的概念：对于函数\(f(x)\), 如果存在DTM使得输入为\(1^n\)时能在\(O(f(n)\)时间内停机，并输出\(f(x)\)的二进制表示，则称\(f(x)\)为时间可构造函数。
可构造函数实际上表示了一类可以计算的函数，并对计算时间/空间进行了一定约束，而这个约束与\(f(n)\)本身相关。

引理1. 设s(n)是空间可构造的，\(s(n)\ge \log_2(n).\) 则存在DTM u，使得对任意长度为n的输入，能够在\(O(s(n))\)空间、\(2^{O(s(n))}\)步以内标明\(s(n)\)个方格。
证明思路：构造一台有三条工作带的DTM。对于输入n，利用空间可构造性，先将其二进制表示写在带1上。然后，先在带2上写一个1，将带1的读写头移至最左。若带1读到1，将带2内容复制到带3上，将带2内容复制一倍，最后将带1读写头右移。重复上述操作直到读完带1。

定理1. 设s是空间可构造的，\(s(n)\ge \log_2(n),L\in NSPACE(s(n)).\) 则\(L\in DTIME(2^{O(s(n))}).\)
证明思路：设\(L=L(U)\). U有a个状态，b个带符号。U在工作带上至多使用\(c\cdot s(n)\)个方格，c为常数。可以计算U至多有\(a(n+2)\cdot cs(n)b^{cs(n)}\)个不同的格局。又\(s(n)\ge \log_2 n,\)故格局数为\(2^{O(s(n))}\).
构造有向图，顶点为U的各格局及一个终点格局\(\sigma_f\),并且任两个格局有指向当且仅当出发点可以经U的一步计算到达终点。因此，U接受w当且仅当有一条\(\sigma_0\to\sigma_f.\)
构造DTM U', 对每个输入w，县构造如上的有向图G，然后检查是否有\(\sigma_0\to\sigma_f\)的通路，\(L(U')=L(U),\)时间复杂度为\(2^{O(s(n))}\).

推论. \(NL\subseteq P,NPSPACE\subseteq EXPTIME.\)

Savitch定理. 设s是空间可构造的，\(s(n)\ge \log_2(n).\) u是一台s(n)空间界限的的NTM，则存在\(s^2(n)\)空间界限的DTM u'使得\(L(u)=L(u').\)
证明思路：采取递归。对于U的两个格局\(\sigma_1,\sigma_2.\)定义\(\sigma_1\vdash^i \sigma_2\)当且仅当可以由\(2^i\)步以内计算得出。
因此，对于\(i\ge 1,\sigma_1\vdash^i \sigma_2 \Leftrightarrow \sigma,\sigma_1\vdash^{i-1}\sigma\vdash^{i-1}\sigma_2.\)
用\(TEST(\sigma_1,\sigma_2,i)\)作为递归函数。因为\(s(n)\)空间可构造，所以每个U的格局至多占用\(O(s(n))\)个格。
U至多有\(2^{as(n)}\)个格局。用某条带作为记录TEST运行记录的栈，则至多记录\(as(n)\)个格局，总空间为\(O(s^2(n))\).

推论. PSPACE=NPSPACE, EXPSPACE=NEXPSPACE

类似NP完全问题，我们也有PSPACE完全问题。
定义. 如果\(\forall L'\in PSPACE,L'\le_m L,\)称L是PSPACE难的；如果还有\(L\in PSPACE,\) 称L是PSPACE完全的。

    所属分类：TCS     发表于2021-12-18