Intractability

本章证明可判定但不可行（intractable）问题的存在性，并介绍三个重要工具：层次定理（Hierarchy Theorems）、相对化（Relativization）和电路复杂度（Circuit Complexity）。

Hierarchy Theorems

直觉上，给 TM 更多时间或空间，应当能扩大它能解的问题类。层次定理将此直觉形式化。

Space Hierarchy

NoteDefinition: Space Constructible

A function \(f : \mathbb{N} \to \mathbb{N}\) with \(f(n) \ge O(\log n)\) is space constructible if the mapping \(1^n \mapsto \text{bin}(f(n))\) is computable in \(O(f(n))\) space.

常见例子：\(n^2\)，\(n \log n\)，\(\log n\)。

对亚线性函数 \(f(n) = o(n)\)，需使用 read-only input tape 模型。

Theorem (Space Hierarchy): For any space constructible \(f : \mathbb{N} \to \mathbb{N}\), there exists a language \(A\) decidable in \(O(f(n))\) space but not in \(o(f(n))\) space.

思路：构造 DTM \(D\)，在 \(O(f(n))\) 空间判定语言 \(A\)，并通过对角化保证 \(A\) 不在 \(o(f(n))\) 空间内。对每个 \(o(f(n))\)-space TM \(M\)，\(D\) 在编码 \(\langle M \rangle\) 对应的输入上与 \(M\) 的判定结果相反。

两个技术细节：

  1. Small-\(n\) anomaly：\(M\) 渐近地用 \(o(f(n))\) 空间，但小 \(n\) 时可能超过 \(f(n)\)。Fix：padding——使用 \(\langle M \rangle 1 0^*\) 形式的输入，产生无穷多次对角化机会。
  2. Non-halting：\(M\) 可能在某些输入上循环，但 \(D\) 必须是 decider。Fix：counting——若模拟超过 \(2^{f(n)}\) 步则 reject（空间 \(f(n)\) 下格局总数至多 \(2^{O(f(n))}\)，重复格局意味着循环）。

Algorithm \(D\) on input \(w\):

  1. Let \(n = |w|\). Compute \(f(n)\) and mark off \(f(n)\) work tape cells. If later stages exceed this, reject.
  2. If \(w\) is not of the form \(\langle M \rangle 1 0^*\) for some TM \(M\), reject.
  3. Simulate \(M\) on \(w\), counting steps. If the count exceeds \(2^{f(n)}\), reject.
  4. If \(M\) accepts, reject. If \(M\) rejects, accept.

\(D\) 运行在 \(O(f(n))\) 空间，由对角化 \(A = L(D)\) 不在 \(o(f(n))\) 空间内。\(\square\)

Corollary: If \(f_1(n) = o(f_2(n))\) and \(f_2\) is space constructible, then \(\mathrm{SPACE}(f_1(n)) \subset \mathrm{SPACE}(f_2(n))\).

Corollary: For \(0 \le \varepsilon_1 < \varepsilon_2\), \(\mathrm{SPACE}(n^{\varepsilon_1}) \subset \mathrm{SPACE}(n^{\varepsilon_2})\).

Corollary: \(\mathrm{NL} \subset \mathrm{PSPACE}\).

由 Savitch 定理 \(\mathrm{NL} \subseteq \mathrm{SPACE}(\log^2 n)\)，由空间层次定理 \(\mathrm{SPACE}(\log^2 n) \subset \mathrm{SPACE}(n)\)，故 \(\mathrm{NL} \subset \mathrm{PSPACE}\)。推论：\(\mathrm{TQBF} \notin \mathrm{NL}\)。

EXPSPACE

NoteDefinition: EXPSPACE

\[\mathrm{EXPSPACE} = \bigcup_k \mathrm{SPACE}(2^{n^k})\]

Corollary: \(\mathrm{PSPACE} \subset \mathrm{EXPSPACE}\)（由 \(\mathrm{SPACE}(n^k) \subseteq \mathrm{SPACE}(n \log n) \subset \mathrm{SPACE}(2^n) \subseteq \mathrm{EXPSPACE}\)）。

扩展正则表达式：在 \((a,\; \varepsilon,\; \varnothing,\; R_1 \cup R_2,\; R_1 \circ R_2,\; R^*)\) 基础上增加指数运算 \(\uparrow\)： \[R^k = R \uparrow k = \underbrace{R \circ R \circ \cdots \circ R}_{k \text{ times}}\]

Theorem: \(\mathrm{EQREX}_\uparrow = \{\langle Q, R \rangle \mid Q, R \text{ are equivalent regular expressions with exponentiation}\}\) is EXPSPACE-complete.

“Equivalent” 指两个表达式描述相同语言。指数运算允许简洁地描述指数级长的连接，这是该判定问题到达 EXPSPACE 的关键原因。

Time Hierarchy

NoteDefinition: Time Constructible

A function \(t : \mathbb{N} \to \mathbb{N}\) with \(t(n) \ge O(n \log n)\) is time constructible if the mapping \(1^n \mapsto \text{bin}(t(n))\) is computable in \(O(t(n))\) time.

常见例子：\(n \log n\)，\(n\sqrt{n}\)，\(n^2\)，\(2^n\)。

Theorem (Time Hierarchy): For any time constructible \(t : \mathbb{N} \to \mathbb{N}\), there exists a language \(A\) decidable in \(O(t(n))\) time but not in \(o(t(n) / \log t(n))\) time.

比空间层次定理多一个 \(\log\) 因子——这是因为模拟时用二进制步数计数器引入了 \(O(\log t(n))\) 的额外开销。

Algorithm \(D\) on input \(w\):

  1. Let \(n = |w|\). Compute \(t(n)\) and store \(\lfloor t(n) / \log t(n) \rfloor\) in a binary counter. Decrement before each simulated step; if it hits 0, reject.
  2. If \(w\) is not of the form \(\langle M \rangle 1 0^*\) for some TM \(M\), reject.
  3. Simulate \(M\) on \(w\).
  4. If \(M\) accepts, reject; if \(M\) rejects, accept.

\(D\) 在 \(O(t(n))\) 时间内运行，通过对角化排除所有 \(o(t(n)/\log t(n))\)-time TM。\(\square\)

Corollary: If \(t_1(n) = o(t_2(n) / \log t_2(n))\) and \(t_2\) is time constructible, then \(\mathrm{TIME}(t_1(n)) \subset \mathrm{TIME}(t_2(n))\).

Corollary: For \(1 \le \varepsilon_1 < \varepsilon_2\), \(\mathrm{TIME}(n^{\varepsilon_1}) \subset \mathrm{TIME}(n^{\varepsilon_2})\).

Corollary: \(\mathrm{P} \subset \mathrm{EXPTIME}\).

graph LR
    L["L"] -->|"⊂"| NL["NL"]
    NL -->|"⊆"| P["P"]
    P -->|"⊂ (time hierarchy)"| EXPTIME["EXPTIME"]
    NL -->|"⊂ (space hierarchy)"| PSPACE["PSPACE"]
    PSPACE -->|"⊂ (space hierarchy)"| EXPSPACE["EXPSPACE"]
    P -->|"⊆"| PSPACE

Relativization

Oracle Model

NoteDefinition: Oracle TM

An oracle for a language \(A\) is a device that can answer, in one step, whether any queried string \(w\) belongs to \(A\).

An oracle TM \(M^A\) is a TM equipped with an oracle tape; writing a query string instantly yields an answer about membership in \(A\).

  • \(\mathrm{P}^A\)：polynomial-time oracle TM using oracle \(A\) 可判定的语言类。
  • \(\mathrm{NP}^A\)：类似，但为非确定性多项式时间。

Examples：

  • \(\mathrm{NP} \subseteq \mathrm{P}^{\mathrm{SAT}}\)
  • \(\mathrm{coNP} \subseteq \mathrm{P}^{\mathrm{SAT}}\)
  • \(\mathrm{MIN\text{-}FORMULA} \subseteq \mathrm{NP}^{\mathrm{SAT}}\)

这些包含关系反映了 SAT 作为 NP-complete 问题的”完全性”：有了 SAT oracle，多项式时间机器就能解决所有 NP 问题。

Limits of Diagonalization

对角化的本质是一个 TM 模拟另一个，然后在某个输入上给出不同结果。如果给两台机器同一个 oracle \(O\)，\(M_1^O\) 仍然可以模拟 \(M_2^O\)。因此，纯对角化/模拟方法证明的定理会相对化——在有 oracle 时仍然成立。

这对 P vs NP 问题至关重要：

Theorem (Baker–Gill–Solovay):

  1. There exists an oracle \(A\) such that \(\mathrm{P}^A \ne \mathrm{NP}^A\).
  2. There exists an oracle \(B\) such that \(\mathrm{P}^B = \mathrm{NP}^B\).

令 \(B = \mathrm{TQBF}\)。则 \[\mathrm{NP}^{\mathrm{TQBF}} \subseteq \mathrm{NPSPACE} \subseteq \mathrm{PSPACE} \subseteq \mathrm{P}^{\mathrm{TQBF}}\]

故 \(\mathrm{P}^{\mathrm{TQBF}} = \mathrm{NP}^{\mathrm{TQBF}}\)。\(\square\)

定义 \(L^A = \{w \mid \exists x \in A,\; |x| = |w|\}\)。对任何 \(A\)，\(L^A \in \mathrm{NP}^A\)（NTM 猜 \(x\) 并查询 oracle）。

我们构造 \(A\) 使 \(L^A \notin \mathrm{P}^A\)，方法是对所有多项式时间 oracle TM 逐个对角化：

列出所有多项式时间 oracle TM \(M_1, M_2, \dots\)，其中 \(M_i\) 运行时间 \(n^i\)。分阶段构造 \(A\)：

Stage \(i\)：

  1. 选 \(n\) 足够大，使 \(2^n > n^i\) 且 \(n\) 超过之前固定的所有串长。
  2. 运行 \(M_i\) on \(1^n\)，对 oracle 查询的串：若已确定其状态则一致回答，否则回答 NO 并声明不在 \(A\) 中。
  3. 若 \(M_i\) accepts \(1^n\)：声明 \(A\) 不含任何长 \(n\) 的串。
  4. 若 \(M_i\) rejects \(1^n\)：将一个未被查询的长 \(n\) 的串放入 \(A\)（这样的串存在，因为 \(2^n > n^i\)，而 \(M_i\) 至多查询 \(n^i\) 个串）。
  5. 将所有长度 \(\le n\) 且状态未定的串声明不在 \(A\) 中。

于是每个 stage 保证 \(M_i^A\) 无法正确判定 \(L^A\)。\(\square\)

相对化告诉我们：解决 P vs NP 必须使用超越纯模拟/对角化的方法——必须分析计算的内部结构。

Circuit Complexity

计算机由电子器件构成数字电路，其理论模型是布尔电路。

Boolean Circuits

NoteDefinition: Boolean Circuit

A Boolean circuit is a collection of gates (AND, OR, NOT) and inputs connected by wires. Cycles are not permitted.

  • Inputs: \(x_1, \dots, x_n\)
  • One gate is designated as the output gate
  • Wires carry Boolean values \(0\) and \(1\)

AND/OR/NOT gate symbols Example Boolean circuit Circuit evaluation

电路 \(C\) 有 \(n\) 个输入，计算函数 \(f_C : \{0,1\}^n \to \{0,1\}\)。多输出门的电路计算 \(f_C : \{0,1\}^n \to \{0,1\}^k\)。

Example: \(n\)-input parity function \(\mathrm{parity}_n : \{0,1\}^n \to \{0,1\}\) 在输入中有奇数个 1 时输出 1。

Parity circuit

Circuit Families

单个电路只处理固定长度输入。为了判定语言（任意长度），需要电路族。

NoteDefinition: Circuit Family

A circuit family \(\mathcal{C} = (C_0, C_1, C_2, \dots)\) where \(C_n\) has \(n\) input variables.

\(\mathcal{C}\) decides language \(A \subseteq \{0,1\}^*\) if for every string \(\omega\) of length \(n\): \[\omega \in A \iff C_n(\omega) = 1.\]

Size and Depth

  • Size of a circuit：门的数目。Size complexity of a family：\(f(n) = \mathrm{size}(C_n)\)。
  • Depth of a circuit：从输入到输出的最长路径长度。
  • Circuit complexity of a language：最小电路族的 size complexity。
  • 例：\(\mathrm{parity}_n\) 的电路复杂度为 \(O(n)\)。

TIME \(\Rightarrow\) Circuits

Theorem: Let \(t(n) \ge n\). If \(A \in \mathrm{TIME}(t(n))\), then \(A\) has circuit complexity \(O(t(n)^2)\).

设 DTM \(M\) 在 \(t(n)\) 时间判定 \(A\)。考虑 \(M\) 在长 \(n\) 输入上的tableau：

  • 行 = 时间步 \(0, 1, \dots, t(n)\)
  • 列 = 带格 \(1, 2, \dots, t(n)\)

假设 \(M\) 接受时读头在最左格且该格含接受符号；停机后配置不变。则接受与否可从 tableau 特定格读出。

局部性：每个格 \((i, j)\) 仅由上一行的 \((i-1, j-1)\)、\((i-1, j)\)、\((i-1, j+1)\) 三个格决定（由转移函数）。

Tableau layout Local dependency

“Lights” representation：设 \(k = |\Gamma \cup (Q \times \Gamma)|\)。引入指示线 \(\mathrm{light}[i,j,s]\)：

  • \(\mathrm{light}[i,j,s] = 1\) 表示格 \((i,j)\) 的内容为 \(s\)
  • 每个格恰有一个 light 亮

对每个 light，枚举所有使 \(s\) 出现在 \((i,j)\) 的前驱三元组 \((a,b,c)\)，用 AND 门检查、OR 门汇总。

每个格用常数个门，总共 \(O(t(n)^2)\) 个格，故电路大小 \(O(t(n)^2)\)。\(\square\)

CIRCUIT-SAT

\[\mathrm{CIRCUIT\text{-}SAT} = \{\langle C \rangle \mid C \text{ is a satisfiable Boolean circuit}\}\]

Theorem: CIRCUIT-SAT is NP-complete.

\(\mathrm{CIRCUIT\text{-}SAT} \in \mathrm{NP}\)：猜一组输入赋值，多项式时间内从输入门到输出门逐层评估电路。

NP-hard：与 Cook-Levin 定理思路一致。给定任意 \(A \in \mathrm{NP}\)，设 NTM \(N\) 在 \(O(n^k)\) 时间判定 \(A\)。对输入 \(w\)，构造电路 \(C\)：

  1. 使用 Cook-Levin 的 tableau 构造：\(n^k \times n^k\) 的配置表
  2. 将 tableau 中的每个格编码为电路中的变量
  3. \(\phi_{\text{cell}}, \phi_{\text{start}}, \phi_{\text{move}}, \phi_{\text{accept}}\) 对应电路中的门
  4. 输出门为 \(\phi_{\text{accept}}\)

关键差异：Cook-Levin 归约到 SAT（公式），这里直接归约到电路。电路允许”扇出”（fan-out），共享变量可直接复用，无需重复。因此电路大小 \(O(n^{2k})\)，多项式。

Q.E.D.

3SAT via CIRCUIT-SAT

Theorem: 3SAT is NP-complete.

给定电路 \(C\)，输入线 \(x_1, \dots, x_\ell\)，门输出 \(g_1, \dots, g_m\)。

构造公式 \(\varphi\)，变量对应电路的线：输入线变量 \(x_i\)，门输出变量 \(g_j\)，统一重编号为 \(w_1, \dots, w_{\ell+m}\)。

对每个门添加约束：

Gate constraints

  • NOT gate: \(w_j = \mathrm{NOT}(w_i)\)

\[(\overline{w_i} \to w_j) \land (w_i \to \overline{w_j})\]

  • AND gate: \(w_k = \mathrm{AND}(w_i, w_j)\)

\[\bigwedge_{(a,b) \in \{0,1\}^2} \left((w_i = a \land w_j = b) \to (w_k = a \land b)\right)\]

  • OR gate: \(w_k = \mathrm{OR}(w_i, w_j)\)

\[\bigwedge_{(a,b) \in \{0,1\}^2} \left((w_i = a \land w_j = b) \to (w_k = a \lor b)\right)\]

最后加单子句 \(w_{\text{out}}\)（输出线为 1），并将每个蕴含 \((a \to b)\) 展开为 \((\overline{a} \lor b)\)。超过 3 个文字的子句引入辅助变量拆成 3-CNF，仅产生多项式膨胀。\(\square\)