Space Complexity

时间复杂度度量 TM 的步数，空间复杂度度量 TM 使用的带格数（worst-case）。

Definition: Space Complexity of a DTM

Let \(M\) be a DTM that halts on all inputs. The space complexity of \(M\) is the function \(f : \mathbb{N} \to \mathbb{N}\), where \(f(n)\) is the maximum number of tape cells that \(M\) scans on any input of length \(n\).

If \(M\) has space complexity \(f(n)\), we say “\(M\) runs in space \(f(n)\).”

Definition: Space Complexity of an NTM

Let \(M\) be an NTM that halts on all branches. The space complexity of \(M\) is \(f(n)\), where \(f(n)\) is the maximum number of tape cells that \(M\) scans on any branch of its computation for any input of length \(n\).

Definition: SPACE and NSPACE

\[\mathrm{SPACE}(f(n)) = \{L \mid L \text{ is decided by some DTM using } O(f(n)) \text{ space}\}\]

\[\mathrm{NSPACE}(f(n)) = \{L \mid L \text{ is decided by some NTM using } O(f(n)) \text{ space}\}\]

Examples

SAT \(\in\) SPACE\((n)\)

\[\mathrm{SAT} = \{\langle \varphi \rangle \mid \varphi \text{ is a satisfiable Boolean formula}\}.\]

\(M_1\) on input \(\langle \varphi \rangle\)（\(\varphi\) 有变量 \(x_1, \dots, x_m\)）：

系统地枚举所有 \(2^m\) 个真值赋值（用长 \(m\) 的二进制计数器）。
对每个赋值，扫描 \(\varphi\) 并求值。
若某个赋值使 \(\varphi\) 为真则接受；否则拒绝。

空间：计数器 \(O(m)\) + 求值 \(O(m)\) = \(O(n)\)（因为 \(m = O(n)\)）。时间是指数的，但空间只是线性的——这是空间与时间分离的经典例子。

\(\mathrm{ALL_{NFA}} \in \mathrm{NSPACE}(n)\)

\[\mathrm{ALL_{NFA}} = \{\langle A \rangle \mid A \text{ is an NFA and } L(A) = \Sigma^*\}.\]

\(N\) on input \(\langle M \rangle\)（\(M\) 有 \(q\) 个状态）：

在 NFA 的起始状态放一个标记。
重复至多 \(2^q\) 次：
- 非确定性地选一个输入符号，更新状态标记（模拟子集构造）。
若在某一时刻没有任何标记在接受状态上（发现了被拒串），则 accept（即 \(L(M) \ne \Sigma^*\)）。否则 reject。

空间：只需存当前状态子集（\(q\) bits）+ 计数器（\(O(q)\)），总计 \(O(q) = O(n)\)。

因此 \(\mathrm{ALL_{NFA}} \in \mathrm{NSPACE}(n)\)。非确定性在这里的作用是”猜一个反例串”。

Savitch’s Theorem

Theorem (Savitch, 1969): For any function \(f : \mathbb{N} \to \mathbb{R}^+\) with \(f(n) \ge n\), \[\mathrm{NSPACE}(f(n)) \subseteq \mathrm{SPACE}(f(n)^2).\]

非确定性空间至多是确定性空间的平方——这与时间复杂度中 P vs NP 的巨大鸿沟形成鲜明对比。

Proof Idea: Configuration Graph Reachability

设 \(A \in \mathrm{NSPACE}(f(n))\)，由 NTM \(N\) 在 \(O(f(n))\) 空间内判定。\(N\) 在输入 \(w\) 上的格局图：

顶点 = 使用至多 \(f(n)\) 空间的所有格局
边 = \(N\) 的合法一步转移

判定 \(N\) 是否接受 \(w\) 等价于：从 \(c_{\mathrm{start}}\) 到 \(c_{\mathrm{accept}}\) 在格局图中是否有路径？

graph LR
    cs["c_start"] -->|"?"| cm["c_mid"]
    cm -->|"?"| ca["c_accept"]
    cs -.->|"≤ t steps"| ca

Savitch 的想法：用分治法确定性地判断可达性，空间开销仅 \(O(f(n)^2)\)。

The Recursive Procedure CANYIELD

\(\mathrm{CANYIELD}(c_1, c_2, t)\)：判断 \(c_1\) 能否在 \(\le t\) 步内到达 \(c_2\)。

If \(t = 1\): check whether \(c_1 = c_2\) or \(c_2\) is a one-step successor of \(c_1\). Accept if either holds; reject otherwise.
If \(t > 1\): for each configuration \(c_m\) (over \(f(n)\) space):
- Run \(\mathrm{CANYIELD}(c_1, c_m, \lfloor t/2 \rfloor)\).
- Run \(\mathrm{CANYIELD}(c_m, c_2, \lfloor t/2 \rfloor)\).
- If both accept, accept.
- If no such \(c_m\) found, reject.

graph TD
    Q["CANYIELD(c₁, c₂, t)"] --> L["CANYIELD(c₁, cₘ, t/2)"]
    Q --> R["CANYIELD(cₘ, c₂, t/2)"]
    L --> LL["CANYIELD(c₁, c', t/4)"]
    L --> LR["CANYIELD(c', cₘ, t/4)"]
    R --> RL["CANYIELD(cₘ, c'', t/4)"]
    R --> RR["CANYIELD(c'', c₂, t/4)"]

Full Proof

将 \(N\) 改造为接受时清空带并回到最左格、进入唯一接受格局 \(c_{\mathrm{accept}}\)。设 \(c_{\mathrm{start}}\) 为起始格局。

\(N\) 使用 \(f(n)\) 空间时，格局总数 \(\le T = 2^{d \cdot f(n)}\)（\(d\) 为常数）。因此接受路径长度 \(\le T\)。

DTM \(M\) on input \(w\)：输出 \(\mathrm{CANYIELD}(c_{\mathrm{start}}, c_{\mathrm{accept}}, T)\)。

空间分析：

递归深度 = \(\log T = O(f(n))\)
每层存储 \(c_1, c_2, c_m\) 等格局（每个 \(O(f(n))\)）+ 局部变量

\[\text{Total space} = O(f(n)) \times O(f(n)) = O(f(n)^2)\]

如何获得 \(f(n)\)：\(f\) 是 space-constructible 的，\(M\) 可直接计算 \(f(n)\) 并据此确定 \(T\)。若不确切知道 \(f(n)\)，可令 \(M\) 依次尝试 \(f(n) = 1, 2, 3, \dots\)

\(\square\)

PSPACE and NPSPACE

Definition: PSPACE

\[\mathrm{PSPACE} = \bigcup_{k \ge 1} \mathrm{SPACE}(n^k)\]

\[\mathrm{NPSPACE} = \bigcup_{k \ge 1} \mathrm{NSPACE}(n^k)\]

由 Savitch 定理，\(\mathrm{NSPACE}(n^k) \subseteq \mathrm{SPACE}(n^{2k})\)，因此 \[\mathrm{NPSPACE} = \mathrm{PSPACE}.\]

非确定性不增加多项式空间的能力。

Class Relationships

时间 \(t\) 的 TM 至多使用 \(t\) 个格子，故 \(\mathrm{P} \subseteq \mathrm{PSPACE}\)，\(\mathrm{NP} \subseteq \mathrm{NPSPACE} = \mathrm{PSPACE}\)。
使用 \(f(n)\) 空间的 TM 至多有 \(f(n) \cdot 2^{O(f(n))}\) 种格局，故运行时间 \(\le f(n) \cdot 2^{O(f(n))}\)。多项式空间 \(\Rightarrow\) 指数时间。

\[\mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE} = \mathrm{NPSPACE} \subseteq \mathrm{EXPTIME}\]

已知 \(\mathrm{P} \ne \mathrm{EXPTIME}\)，因此链中至少有一个包含是严格的。普遍猜测每个包含都是严格的。

flowchart TB
    subgraph EXPTIME_box["EXPTIME"]
        subgraph PSPACE_box["PSPACE = NPSPACE"]
            subgraph NP_box["NP"]
                subgraph P_box["P"]
                end
            end
            subgraph coNP_box["coNP"]
            end
        end
    end

PSPACE-Completeness

Definition: PSPACE-Complete

A language \(B\) is PSPACE-complete if:

\(B \in \mathrm{PSPACE}\), and
every \(A \in \mathrm{PSPACE}\) satisfies \(A \le_P B\)（多项式时间归约）.

若只满足条件 2，称 \(B\) 是 PSPACE-hard。

Why Polynomial-Time Reductions?

为什么不用多项式空间归约？因为：

若 \(B\) 是任意非平凡语言（\(\varnothing \ne B \ne \Sigma^*\)），则每个 PSPACE 语言 \(A\) 都可多项式空间归约到 \(B\)（空间足够直接判定 \(A\)）。
若 \(B \in \mathrm{P}\) 且 \(A\) 多项式空间归约到 \(B\)，不能推出 \(A \in \mathrm{P}\)。

因此多项式空间归约太强，丧失了”完全问题在 P 中则整个类坍缩到 P”的性质。

TQBF

Quantified Boolean Formulas

布尔公式由变量、常量 \(\{0, 1\}\) 和运算 \(\wedge, \vee, \neg\) 构成。加上量词 \(\forall x\)（对所有 \(x \in \{0,1\}\)）和 \(\exists x\)（存在 \(x \in \{0,1\}\)），得到量化布尔公式。

若每个变量都在某个量词作用域内，称公式是全量化的（fully quantified）。全量化布尔公式有确定真值。

例：\(\forall x \exists y\; [(x \lor y) \land (\neg x \lor y)]\)。

Definition: TQBF

\[\mathrm{TQBF} = \{\langle \varphi \rangle \mid \varphi \text{ is a true fully quantified Boolean formula}\}\]

TQBF \(\in\) PSPACE

递归算法 \(T\) on input \(\langle \varphi \rangle\)：

If \(\varphi\) has no quantifiers: evaluate \(\varphi\) directly; accept if true, reject if false.
If \(\varphi = \exists x\, \psi\): recursively evaluate \(T(\psi[x := 0])\) and \(T(\psi[x := 1])\). Accept if either accepts.
If \(\varphi = \forall x\, \psi\): recursively evaluate \(T(\psi[x := 0])\) and \(T(\psi[x := 1])\). Accept only if both accept.

每层递归去掉一个量词，深度 \(\le m\)（变量数），每层空间 \(O(|\varphi|)\)，总空间多项式。故 \(\mathrm{TQBF} \in \mathrm{PSPACE}\)。

TQBF is PSPACE-Complete

Theorem: TQBF is PSPACE-complete.

Proof (PSPACE-hardness)

设 \(A \in \mathrm{PSPACE}\)，由 DTM \(M\) 在 \(n^k\) 空间判定。对输入 \(w\)，构造全量化布尔公式 \(\varphi\) 使得 \(M\) accepts \(w \iff \varphi\) is true。

编码格局：每个格局用 \(O(n^k)\) 个布尔变量表示（带内容、读头位置、状态），方法同 Cook-Levin 定理。

定义 \(\varphi_{c_1, c_2, t}\)：当 \(c_1, c_2\) 被赋值为具体格局时，公式为真当且仅当 \(M\) 能在 \(\le t\) 步从 \(c_1\) 到 \(c_2\)。

Base case (\(t = 1\))：\(\varphi_{c_1, c_2, 1}\) 表达”\(c_1 = c_2\) 或 \(c_2\) 是 \(c_1\) 的合法后继”，大小 \(O(n^k)\)，构造方法同 Cook-Levin。

Recursive case (\(t > 1\))：

朴素方法： \[\varphi_{c_1, c_2, t} \stackrel{?}{=} \exists m\; (\varphi_{c_1, m, t/2} \land \varphi_{m, c_2, t/2})\]

问题：公式大小 \(|\varphi_t| = 2 \cdot |\varphi_{t/2}| + O(n^k)\)，递归 \(\log t = O(n^k)\) 层，总大小 \(2^{O(n^k)}\)——指数级！

\(\forall\)-quantifier trick：

\[\varphi_{c_1, c_2, t} = \exists m_1\; \forall (c_3, c_4) \in \{(c_1, m_1),\; (m_1, c_2)\}\; [\varphi_{c_3, c_4, t/2}]\]

含义：\(\exists m_1\) 猜中间格局。\(\forall (c_3, c_4)\) 表示”对两对端点，\(c_3\) 都能在 \(t/2\) 步内到达 \(c_4\)“。

关键：子公式 \(\varphi_{c_3, c_4, t/2}\) 只写一次，被 \(\forall\) 复用。于是 \(|\varphi_t| = |\varphi_{t/2}| + O(n^k)\)，递归 \(O(n^k)\) 层，总大小 \(O(n^{2k})\)——多项式！

实现 \(\forall (c_3, c_4) \in \{(c_1, m_1), (m_1, c_2)\}\)：引入选择变量 \(b\)，令 \(c_3 = (b\;?\;c_1 : m_1)\)，\(c_4 = (b\;?\;m_1 : c_2)\)，然后写 \(\forall b\; \varphi_{c_3(b), c_4(b), t/2}\)。

最终公式：令 \(h = 2^{d \cdot n^k}\)（格局总数上界），则 \[f(\langle M, w \rangle) = \varphi_{c_{\mathrm{start}}, c_{\mathrm{accept}}, h}\]

\(M\) accepts \(w \iff \varphi\) is true \(\iff f(\langle M, w \rangle) \in \mathrm{TQBF}\)。

\(f\) 在多项式时间内可计算，输出的公式大小为多项式。故 \(A \le_P \mathrm{TQBF}\)。\(\square\)

Formula Game

给定全量化布尔公式 \[\varphi = \exists x_1 \forall x_2 \exists x_3 \cdots Q x_k\; [\psi]\] （\(\psi\) 无量词），定义二人博弈：

Player E（Existential）：选择 \(\exists\) 量词绑定的变量的值。
Player A（Universal）：选择 \(\forall\) 量词绑定的变量的值。
双方轮流为 \(x_1, x_2, \dots, x_k\) 赋值。赋完后求值 \(\psi\)：若 \(\psi\) 为真则 E wins，否则 A wins。

Examples

Example 1: Player E wins.

\[\varphi = \exists x_1 \forall x_2 \exists x_3\; [(x_1 \lor x_2) \land (\neg x_2 \lor x_3) \land (x_2 \lor \neg x_3)]\]

E 的必胜策略：

E 选 \(x_1 = 1\)（使 \((x_1 \lor x_2)\) 恒真）
A 选 \(x_2\)：
- \(x_2 = 0\)：E 选 \(x_3 = 0\)。验证 \((1 \lor 0)(1 \lor 0)(0 \lor 1) = 1\)。\(\checkmark\)
- \(x_2 = 1\)：E 选 \(x_3 = 1\)。验证 \((1 \lor 1)(0 \lor 1)(1 \lor 0) = 1\)。\(\checkmark\)

Example 2: Player A wins.

\[\psi = \forall x_1 \forall x_2\; [x_1 \land x_2]\]

A 选 \(x_1 = 0\)（或 \(x_2 = 0\)）即可使公式为假。

\[\mathrm{FORMULA\text{-}GAME} = \{\langle \varphi \rangle \mid \text{Player E has a winning strategy in Formula-Game}(\varphi)\}\]

Theorem: FORMULA-GAME is PSPACE-complete.

这直接来自 TQBF 的 PSPACE-completeness：\(\varphi \in \mathrm{TQBF} \iff\) Player E has a winning strategy。

Generalized Geography

地名接龙游戏的抽象版本。

Definition: Generalized Geography (GG)

Given a directed graph \(G\) and a start vertex \(b\):

Player I starts at \(b\).
Players alternate; each turn, the current player follows an outgoing edge to a new vertex.
No vertex may be visited twice (simple path).
The player unable to move loses.

\[\mathrm{GG} = \{\langle G, b \rangle \mid \text{Player I has a winning strategy}\}\]

GG \(\in\) PSPACE

递归算法 \(M\) on input \(\langle G, b \rangle\)：

If \(b\) has outdegree 0, reject（Player I 无法移动，输了）。
Remove \(b\) and所有相关边，得到 \(G'\)。
For each successor \(b_i\) of \(b\): recursively call \(M(G', b_i)\).
If all recursive calls accept（对手从每个 \(b_i\) 出发都能赢），then reject（当前玩家必输）。
If some recursive call rejects（对手从某个 \(b_i\) 出发输了），then accept（选该 \(b_i\) 即可赢）。

递归深度 \(\le m\)（节点数），每层 \(O(m)\) 空间（标记已删除节点），总计 \(O(m^2)\) = polynomial。故 \(\mathrm{GG} \in \mathrm{PSPACE}\)。

GG is PSPACE-Complete

Theorem: GG is PSPACE-complete.

Proof (PSPACE-hardness via FORMULA-GAME)

给定 \(\varphi = \exists x_1 \forall x_2 \cdots \exists x_k\; [\psi]\)（量词交替，以 \(\exists\) 开始和结束，\(\psi\) 为 CNF），构造有向图 \(G\) 和起始点 \(b\)。

Left side — Diamond gadgets for variables：

对每个变量 \(x_i\) 构造菱形结构（diamond），有两条路径分别对应 \(x_i = \mathrm{TRUE}\) 和 \(x_i = \mathrm{FALSE}\)。结构保证：

当 \(x_i\) 的量词为 \(\exists\) 时，轮到 Player I 选择分支。
当量词为 \(\forall\) 时，轮到 Player II 选择。

由于量词交替且玩家交替行动，这与公式博弈的语义一致。

Right side — Clause checking：

所有变量赋值完成后，token 进入右半部分，编码 \(\psi = C_1 \land \cdots \land C_m\)：

Player II 选择一个子句 \(C_j\)（试图找到假子句）。
Player I 选择 \(C_j\) 中的一个文字，声称该文字为真。
图结构保证：只有当该文字在先前的赋值下确实为真时，Player I 才能继续移动。

若 \(\psi\) 在当前赋值下为真：无论 Player II 选哪个子句，Player I 都能选到真文字，最终 Player II 无路可走。若 \(\psi\) 为假：Player II 选到假子句，Player I 被卡住。

构造可在多项式时间完成，且 Player I wins in GG \(\iff\) Player E wins in FORMULA-GAME \(\iff\) \(\varphi \in \mathrm{TQBF}\)。\(\square\)