The Classes L and NL

到目前为止讨论的空间界都是至少线性的（\(f(n) \ge n\)）。现在考虑亚线性空间，此时 work space 甚至不够存下整个输入。为此需要修改计算模型。

Two-Tape Model

NoteDefinition: Two-Tape TM for Sublinear Space

A Turing machine with two tapes:

  1. A read-only input tape: the head can read symbols but cannot modify them; it must stay within the input region.
  2. A read/write work tape: standard read-write operations.

Only the cells scanned on the work tape count toward the space complexity.

graph LR
    subgraph model["Two-tape TM Model"]
        direction TB
        IT["Input Tape (read-only): w₁ w₂ ⋯ wₙ"]
        WT["Work Tape (read/write): O(log n) cells"]
        FSM["Finite Control"]
    end
    FSM -->|"read"| IT
    FSM <-->|"read/write"| WT

直觉上：input tape 相当于光盘（CD-ROM），work tape 相当于主存。空间复杂度只计 work tape 的用量。

Classes L and NL

NoteDefinition: L and NL

\[\mathrm{L} = \mathrm{SPACE}(\log n)\]

\[\mathrm{NL} = \mathrm{NSPACE}(\log n)\]

其中 SPACE 和 NSPACE 使用上述二带模型，仅统计 work tape 的空间。

\(\log n\) 位空间能存什么？

  • 一个指向输入位置的指针（\(1, \dots, n\)）
  • 常数个大小不超过 \(n\) 的计数器
  • 一个 \(n\) 个节点的图中的顶点编号

但不够存一个 \(n\)-bit 串、邻接矩阵或完整路径。

Basic Examples

\(\{0^k 1^k\} \in \mathrm{L}\)

\[A = \{0^k 1^k \mid k \ge 0\} \in \mathrm{L}.\]

方法：在 work tape 上用二进制计数器分别统计 0 和 1 的个数，只需 \(O(\log n)\) 空间。同时用一个 1-bit flag 确认输入形如”全 0 后全 1”。

PATH \(\in\) NL

\[\mathrm{PATH} = \{\langle G, s, t \rangle \mid G \text{ is a directed graph with a directed path from } s \text{ to } t\}.\]

NTM 算法：

  1. 从节点 \(s\) 开始。
  2. 非确定性地猜下一个节点。
  3. Work tape 上只存当前节点（\(O(\log n)\) bits），不存整条路径。
  4. 重复至多 \(m\) 步（\(m\) 为节点数）。若到达 \(t\) 则接受，否则拒绝。

因此 \(\mathrm{PATH} \in \mathrm{NL}\)。目前不知道 \(\mathrm{PATH} \in \mathrm{L}\) 是否成立（即 \(\mathrm{L} \stackrel{?}{=} \mathrm{NL}\) 是开放问题）。

Space vs Time at Small Bounds

对于”大”空间界（\(f(n) \ge n\)），有 \(f(n)\)-space TM 的运行时间 \(\le 2^{O(f(n))}\)。但对于极小的空间界，这个结论需要修正。例如，\(O(1)\)-space TM 可能运行 \(n\) 步。

NoteDefinition: Configuration (Two-Tape Model)

For a two-tape TM \(M\) on input \(w\), a configuration consists of the state, the work tape contents, and the positions of both tape heads. The input \(w\) itself is not part of the configuration.

If \(M\) runs in \(f(n)\) space on inputs of length \(n\), the number of configurations is \(n \cdot 2^{O(f(n))}\).

多出的因子 \(n\) 来自 input head 有 \(n\) 个可能位置。当 \(f(n) \ge \log n\) 时，时间仍然至多是空间的指数级，Savitch 定理也可推广到亚线性空间的情形。

NL-Completeness

Why Logspace Reductions?

多项式时间归约对 NL 来说”太强”：NL 中除 \(\varnothing\) 和 \(\Sigma^*\) 以外的所有问题在多项式时间下都互相可归约，无法区分问题的内部结构。因此改用对数空间归约。

NoteDefinition: Logspace Transducer

A logspace transducer is a TM with:

  • a read-only input tape,
  • a write-only output tape (head never moves left, cannot read what it has written),
  • a read/write work tape with \(O(\log n)\) symbols.

It computes a function \(f : \Sigma^* \to \Sigma^*\), where \(f(w)\) is the output on the output tape after halting on input \(w\). Such \(f\) is a logspace computable function.

Language \(A\) is logspace reducible to \(B\), written \(A \le_L B\), if \(A\) mapping-reduces to \(B\) via a logspace computable function.

NoteDefinition: NL-Complete

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

  1. \(B \in \mathrm{NL}\), and
  2. every \(A \in \mathrm{NL}\) satisfies \(A \le_L B\).

Logspace Reductions Preserve L

Theorem: If \(A \le_L B\) and \(B \in \mathrm{L}\), then \(A \in \mathrm{L}\).

设 \(f\) 为对数空间归约，\(M_B\) 在对数空间判定 \(B\)。构造 \(M_A\)：

难点：\(f(w)\) 可能远大于 \(\log n\)，不能整个存下来。

解决方案：\(M_A\) 按需计算 \(f(w)\) 的单个符号：

  • 追踪 \(M_B\) 的输入头在 \(f(w)\) 上的位置。
  • 每当 \(M_B\) 移动一步，\(M_A\) 就从头重新运行 transducer 计算 \(f\)，忽略所有输出直到所需位置的那个符号。
  • 任何时刻只需存储 \(f(w)\) 的一个符号。

这是一种”用时间换空间”的策略。总空间 = \(M_B\) 的 \(O(\log n)\) + transducer 的 \(O(\log n)\) + 位置指针 \(O(\log n)\) = \(O(\log n)\)。\(\square\)

Corollary: If any NL-complete language is in L, then \(\mathrm{L} = \mathrm{NL}\).

PATH is NL-Complete

Theorem: PATH is NL-complete.

已知 \(\mathrm{PATH} \in \mathrm{NL}\)。下面证明 NL-hardness。

设 \(A \in \mathrm{NL}\)，NTM \(M\) 在 \(O(\log n)\) 空间判定 \(A\)。对输入 \(w\)，构造 \(\langle G, s, t \rangle\)：

  1. Nodes of \(G\)：\(M\) 在 \(w\) 上的所有格局（configuration）。
  2. Edges：\((c_1, c_2)\) 是边 iff \(c_2\) 是从 \(c_1\) 出发的一个可能后继格局。
  3. \(s\)：\(M\) 在 \(w\) 上的起始格局。
  4. \(t\)：将 \(M\) 改造为有唯一接受格局，该格局为 \(t\)。

则 \(G\) 中 \(s\) 到 \(t\) 有路径 \(\iff\) \(M\) 接受 \(w\)。

对数空间可实现性：每个格局用 \(c \log n\) bits 表示。Transducer \(T\) 的工作：

  • 列节点：枚举所有长 \(c \log n\) 的 bitstring，检查是否为 \(M\) 在 \(w\) 上的合法格局。
  • 列边：枚举所有格局对 \((c_1, c_2)\)，检查 \(c_2\) 是否为 \(c_1\) 的合法后继。

枚举和检查都只需 \(O(\log n)\) 工作空间。\(\square\)

\(\mathrm{NL} \subseteq \mathrm{P}\)

Corollary: \(\mathrm{NL} \subseteq \mathrm{P}\).

  1. \(A \in \mathrm{NL}\) \(\Rightarrow\) \(A \le_L \mathrm{PATH}\)。
  2. 使用 \(f(n)\) 空间的 TM 运行时间 \(\le n \cdot 2^{O(f(n))}\)，故对数空间归约器也在多项式时间内运行。
  3. 因此 \(A\) 可多项式时间归约到 PATH。
  4. \(\mathrm{PATH} \in \mathrm{P}\)（BFS/DFS 可在 \(O(|V| + |E|)\) 时间判定有向可达性）。\(\square\)

\(\mathrm{NL} = \mathrm{coNL}\) (Immerman–Szelepcsényi)

Theorem (Immerman–Szelepcsényi, 1987/1988): \[\mathrm{NL} = \mathrm{coNL}.\]

这是与时间复杂度的重大区别——\(\mathrm{NP} \stackrel{?}{=} \mathrm{coNP}\) 仍是开放问题，但在对数空间层面，非确定性类恰好等于其补类。

核心目标：将 \(\overline{\mathrm{PATH}} = \{\langle G, s, t \rangle \mid s \text{ 到 } t \text{ 无路径}\}\) 放进 NL。

High-level Idea

设 \(m = |V|\)，\(c\) = 从 \(s\) 可达的节点数。如果我们知道 \(c\)，就可以非确定性地验证 \(t\) 不可达：

  • 对每个节点 \(u\)，猜测它是否从 \(s\) 可达；若猜 YES 则验证（猜路径）。
  • 遇到 \(u = t\) 且可达则 reject。
  • 最后检查已验证的可达节点数是否恰为 \(c\)（确保没有漏掉的可达节点）。

关键问题：如何在对数空间中计算 \(c\)？

Computing the Reachable Count

定义 \(A_i\) = 从 \(s\) 出发距离 \(\le i\) 的节点集，\(c_i = |A_i|\)。则 \(A_0 = \{s\}\)，\(c_0 = 1\)，\(c = c_m\)。

从 \(c_i\) 计算 \(c_{i+1}\)：对每个节点 \(v\)，检查 \(v\) 是否在 \(A_{i+1}\) 中（即 \(v \in A_i\) 或存在 \(u \in A_i\) 使得 \((u, v) \in E\)）。验证 \(u \in A_i\) 的方式和前面类似：猜长 \(\le i\) 的路径。用计数器 \(\theta\) 追踪已验证的 \(A_i\) 节点数，最终检查 \(\theta = c_i\)。

The Final Algorithm (Sipser-style)

\(M\) on input \(\langle G, s, t \rangle\)（\(m = |V|\)）:

  1. Let \(c_0 = 1\).
  2. For \(i = 0\) to \(m - 1\):
    • Let \(c_{i+1} = 1\)（\(s\) 总是可达的）.
    • For each node \(v \ne s\) in \(G\):
      • Let \(d = 0\).
      • For each node \(u\) in \(G\):
        • Nondeterministically either perform or skip the following:
          • Nondeterministically follow a path of length \(\le i\) from \(s\); reject if it doesn’t end at \(u\).
          • Increment \(d\).
          • If \((u, v)\) is an edge, increment \(c_{i+1}\) and go to the next \(v\).
      • If \(d \ne c_i\), reject.
  3. Let \(d = 0\).
  4. For each node \(u\) in \(G\):
    • Nondeterministically either perform or skip:
      • Nondeterministically follow a path of length \(\le m\) from \(s\); reject if it doesn’t end at \(u\).
      • If \(u = t\), reject.
      • Increment \(d\).
  5. If \(d \ne c_m\), reject. Otherwise, accept.

空间分析：需要存储的变量为 \(m, u, v, c_i, c_{i+1}, d, i\) 以及猜路径时的当前节点指针——每个变量 \(O(\log m) = O(\log n)\)，总空间 \(O(\log n)\)。

因此 \(\overline{\mathrm{PATH}} \in \mathrm{NL}\)。由于 PATH 是 NL-complete 的，\(\mathrm{coNL} \subseteq \mathrm{NL}\)。又由定义对称性 \(\mathrm{NL} \subseteq \mathrm{coNL}\)，故 \(\mathrm{NL} = \mathrm{coNL}\)。\(\square\)

Complexity Classes Summary

\[\mathrm{L} \subseteq \mathrm{NL} = \mathrm{coNL} \subseteq \mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE}\]

flowchart TB
    subgraph PSPACE_box["PSPACE"]
        subgraph NP_box["NP"]
            subgraph P_box["P"]
                subgraph NL_box["NL = coNL"]
                    subgraph L_box["L"]
                    end
                end
            end
        end
    end

目前不知道上述包含关系中哪些是严格的，但普遍猜测所有包含都是严格的。后续的层次定理（Hierarchy Theorems）可以证明某些分离，例如 \(\mathrm{NL} \subset \mathrm{PSPACE}\) 和 \(\mathrm{P} \subset \mathrm{EXPTIME}\)。