TCS Lec9总结

1. 空间复杂度基础

• 定义：
  • SPACE($f(n)$)：由确定型图灵机（TM）在 $O(f(n))$ 空间内可判定的语言集合（$f(n) \geq n$）。
  • NSPACE($f(n)$)：由非确定型图灵机（NTM）在 $O(f(n))$ 空间内可判定的语言集合。
• 示例：
  • SAT 问题 可用线性空间算法求解（遍历所有赋值组合并验证）。
• 时间与空间关系：
  1. $\text{TIME}(t(n)) \subseteq \text{SPACE}(t(n))$
  2. $\text{SPACE}(t(n)) \subseteq \text{TIME}(2^{O(t(n))})$
• PSPACE 类：

  $\text{PSPACE} = \bigcup_{k \geq 0} \text{SPACE}(n^k)$

  • P ⊆ PSPACE（多项式时间算法最多消耗多项式空间）。
  • NP ⊆ PSPACE（例如 3-SAT ∈ PSPACE）。
  • coNP ⊆ PSPACE（因 coPSPACE = PSPACE）。

2. 多项式空间（PSPACE）

(1) PSPACE 完备性

• 定义：问题 $B$ 是 PSPACE-完全 的需满足：
  1. $B \in \text{PSPACE}$；
  2. 所有 PSPACE 中的问题 $A$ 可在 多项式时间 内归约到 $B$。
• 关键问题：TQBF（全量化布尔公式）
  • 描述：判定形如 $\exists x_1 \forall x_2 \exists x_3 \cdots Q x_n [\phi]$ 的公式是否为真（$\phi$ 是无量词的布尔公式）。
  • 性质：
    • TQBF ∈ PSPACE（递归验证，每层消耗常数空间，总空间 $O(n)$）。
    • TQBF 是 PSPACE-完全 的（证明核心：将 PSPACE 问题归约为 TQBF，通过递归构造配置转移公式，并利用 缩写技巧（Abbreviation Trick） 避免公式膨胀）。
  • 特例：SAT 是 TQBF 的子问题（仅存在量词）。

(2) Savitch 定理

• 定理：对任意 $f(n) \geq n$，有

  $\text{NSPACE}(f(n)) \subseteq \text{SPACE}(f^2(n)).$

• 推论：$\text{PSPACE} = \text{NPSPACE}$。
• 证明思路：
  • 定义 可达性问题（Yieldability）：检查 NTM 能否在 $t$ 步内从配置 $c_1$ 到 $c_2$。
  • 递归算法：二分法枚举中间配置 $c_m$，验证 $c_1 \to c_m$ 和 $c_m \to c_2$。
  • 空间分析：递归深度 $\log t = O(f(n))$，每层存配置需 $O(f(n))$ 空间，总空间 $O(f^2(n))$。

(3) 游戏与 PSPACE 完备性

• 公式游戏（FORMULA-GAME）：
  • 玩家 $\exists$ 和 $\forall$ 按量词顺序赋值，$\exists$ 获胜当且仅当公式为真。
  • FORMULA-GAME = TQBF，故为 PSPACE-完全。
• 广义地理学（GENERAL-GEOGRAPHY）：
  • 在有向图上交替选点，不可重复，无法移动者输。
  • PSPACE-完全（归约自 FORMULA-GAME）。
• 引申：国际象棋、围棋等博弈在 $n \times n$ 棋盘上是 PSPACE-难 的。

3. 对数空间（Logarithmic Space）

(1) 模型与复杂度类

• 模型调整：输入带 只读，工作带空间限制为 $O(\log n)$。
• 复杂度类：
  • $\text{L} = \text{SPACE}(\log n)$（确定型对数空间）。
  • $\text{NL} = \text{NSPACE}(\log n)$（非确定型对数空间）。
• 示例：
  • PAL（回文串）∈ L。
  • PATH（有向图可达性）∈ NL（非确定地猜测路径节点）。

(2) 基本性质

• 包含关系：
  • $\text{L} \subseteq \text{NL} \subseteq \text{P}$（Savitch 定理得 $\text{NL} \subseteq \text{SPACE}(\log^2 n)$）。
• NL 问题判定：
  • 构造配置图 $G_{M,w}$（节点为配置，边为一步转移）。
  • $M$ 接受 $w$ 当且仅当存在 $c_{\text{init}}$ 到 $c_{\text{acc}}$ 的路径。

(3) NL 完备性

• 对数空间归约（$\leq_L$）：
  • 使用 对数空间转换器（Transducer）（输入带只读，工作带 $O(\log n)$，输出带只写）。
  • 关键性质：若 $A \leq_L B$ 且 $B \in \text{L}$，则 $A \in \text{L}$（需动态生成输出符号，避免存储长字符串）。
• NL-完全问题：

  • PATH问题：给定一个有向图 $G = (V, E)$ 和两个节点 $s$ 和 $t$，判断是否存在一条从 $s$ 到 $t$ 的有向路径。该问题属于非确定性对数空间类（NL），原因在于存在一个非确定性图灵机算法，在空间复杂度 $O(\log n)$ 内解决它，其中 $n = |V|$ 是图的节点数。以下我将逐步解释原因，并给出具体算法。

    1. PATH问题的特性：

       • 如果存在一条从 $s$ 到 $t$ 的路径，那么一定存在一条简单路径（无环路径），长度不超过 $n - 1$（因为路径中节点不重复）。
       • 因此，算法只需考虑最多 $n$ 步（节点数），避免无限循环。

    2. 非确定性算法的优势：

       • 非确定性图灵机可以“猜测”一条路径的每一步，而无需存储整个路径（这需要线性空间）。
       • 算法只需存储当前节点和一个计数器（记录步数），两者都可用 $O(\log n)$ 空间表示（因为节点ID和计数器值范围是 $[0, n]$，二进制编码需 $\log_2 n$ 位）。
       • 如果存在路径，非确定性机器会通过正确的“猜测”序列在多项式步数内接受；否则，所有猜测序列都拒绝。
       • 因此，PATH问题可以在非确定性对数空间内解决，故 PATH ∈ NL。事实上，PATH 是 NL-完全问题（NL-complete），但这不影响其属于 NL 的结论。

  • 算法思路：从 $s$ 开始，非确定性地“猜测”路径的每一步，并限制步数不超过 $n$（防止循环）。如果达到 $t$，则接受；否则拒绝。

  • 算法输入：

    • 有向图 $G = (V, E)$（节点数 $|V| = n$，节点用唯一ID表示，如 $1, 2, \dots, n$)。
    • 起始节点 $s$ 和目标节点 $t$。

  • 算法输出：

    • “是”（存在路径）或“否”（不存在路径）。

  • 算法步骤：

    1. 初始化：

       • 设置当前节点 $current \gets s$。
       • 设置步数计数器 $steps \gets 0$。
       • 设最大步数 $max\_steps = n$（因为简单路径长度不超过 $n$）。

    2. 重复以下过程最多 $n$ 次（使用非确定性选择）：
       a. 如果 $current = t$，则 接受（输出“是”并停止）。
       b. 非确定性地猜测一个节点 $next$，使得存在边 $(current, next) \in E$（即从 $current$ 出发的出边）。

       • 如果无出边，或猜测无效（如 $next$ 不是邻居），则本分支 拒绝。
         c. 更新当前节点： $current \gets next$。
         d. 增加步数： $steps \gets steps + 1$。
         e. 如果 $steps > max\_steps$（即 $steps > n$），则 拒绝（路径过长，可能陷入循环）。

    3. 循环结束后，检查当前节点：

       • 如果 $current = t$，则 接受（输出“是”）。
       • 否则， 拒绝（输出“否”）。

  • 非确定性解释：

    • 在步骤 2b，机器非确定性地“分支”出多个计算路径，每个分支尝试不同的邻居节点。
    • 如果存在一条从 $s$ 到 $t$ 的路径，则至少有一个分支能正确“猜测”整条路径（步数不超过 $n$），并在某步满足 $current = t$ 而接受。
    • 如果不存在路径，则所有分支都会在步数超限或无法继续时拒绝。

  • 空间复杂度分析：

    • 存储 $current$：节点 ID 需 $O(\log n)$ 位（因为 $n$ 个节点，ID 大小不超过 $\lceil \log_2 n \rceil$)。
    • 存储 $steps$ 和 $max\_steps$：计数器值范围是 $0$ 到 $n$，需 $O(\log n)$ 位（二进制表示）。
    • 其他变量：常数空间。
    • 总空间：$O(\log n)$，符合 NL 要求。
    • 注意：非确定性“猜测”不占用额外空间（是机器内部机制），且算法不存储整个路径，只维护当前状态。

  • 正确性证明**：

    • 完备性（存在路径则接受）：如果存在从 $s$ 到 $t$ 的路径，则存在一条简单路径（长度 $\leq n-1$）。非确定性机器会有一个分支正确“猜测”这条路径的每个节点，并在步数 $\leq n$ 内使 $current = t$，从而接受。
    • 可靠性（不存在路径则拒绝）：如果不存在路径，无论非确定性选择如何，算法要么无法找到有效邻居（拒绝），要么步数超限（拒绝）。循环结束后 $current \neq t$，故所有分支拒绝。

  • **PATH 的 NL-完全性：

    1. $\text{PATH} \in \text{NL}$（非确定搜索路径）。
    2. 任意 NL 问题归约到 PATH（构造配置图 $G_{M,w}$，对数空间输出边和起止点）。

(4) NL = coNL

• Immerman-Szelepcsényi 定理：$\text{NL} = \text{coNL}$。
• 意义：NL 类对补运算封闭（与 NP 是否等于 coNP 的开放问题形成对比）。

4. 空间层次定理

• 定理：对任意 空间可构造 函数 $f(n)$，存在语言 $A$ 满足：

  $A \in \text{SPACE}(f(n)) \quad \text{但} \quad A \notin \text{SPACE}(o(f(n))).$

• 推论：$\text{L} \subsetneq \text{PSPACE}$（对数空间严格包含于多项式空间）。

关键结论与关系图

• 复杂度类包含关系：

  $\text{L} \subseteq \text{NL} \subseteq \text{P} \subseteq \text{NP} \subseteq \text{PH} \subseteq \text{P}^{\#\text{P}} \subseteq \text{PSPACE}$

• 严格性：$\text{L} \neq \text{PSPACE}$（由空间层次定理证明）。
• 核心问题与定理：

  问题/定理	复杂度类	重要性
  TQBF	PSPACE-完全	首个 PSPACE 完备问题
  Savitch 定理	NSPACE ⊆ SPACE($f^2$)	连接确定与非确定空间类
  PATH	NL-完全	NL 类的代表问题
  Immerman-Szelepcsényi	NL = coNL	NL 对补封闭