第六章：电路与非一致计算

图灵机描述一个程序处理所有输入长度；circuit family 允许每个长度 $n$ 使用独立有限线路。该模型适合分析并行深度、硬件规模和非一致计算。

Boolean function family

对每个 $n$ ，Boolean circuit $C_n$ 计算函数

f_n:\{0,1\}^n\to\{0,1\}.

线路族 $\{C_n\}$ 判定 language $L$ ，若

C_n(x)=1\iff x\in L \quad\text{for every }x\in\{0,1\}^n.

size 是 gate 数，depth 是最长路径。若 gate fan-in 有界，则深度 $d$ 的线路最多让一个输出依赖约 $2^d$ 个输入，因此全局函数至少需要 $\Omega(\log n)$ 深度。

Formula、circuit 与 branching program

formula 是每个 gate 输出只使用一次的树；circuit 可以共享中间结果。将 circuit 展开为 formula 可能指数增长，因此共享是计算资源。

branching program 用有向图表示根据输入 bit 转移的计算。宽度、长度和读取次数形成不同受限模型，并与空间复杂度、数据结构和证明复杂度相连。

模型之间的转换必须记录 size 与 depth 的变化，不能仅凭都表示 Boolean function 视为等价。

Uniformity

非一致线路族可能把任意长度相关信息写入 $C_n$ 。为连接算法，需要 uniformity 条件。例如 logspace-uniform 要求存在对数空间机器，根据 $(n,i)$ 输出 $C_n$ 的第 $i$ 个 gate 及连线。

uniformity 强弱影响小深度类。对多项式 size 的一般 circuit，有

\mathsf P\subseteq\mathsf{P/poly},

其中 $\mathsf{P/poly}$ 是具有多项式大小 circuit family 的 language。

反向包含关系未知且通常认为不成立，因为 $\mathsf{P/poly}$ 甚至包含某些不可判定 unary language：每个长度只需把答案硬编码为常数线路。

Advice 的等价刻画

$\mathsf{P/poly}$ 也可表示为多项式时间机器配合只依赖输入长度的 polynomial advice：

L\in\mathsf{P/poly} \iff \exists M,\{a_n\},\ |a_n|\le n^{O(1)}, \ M(x,a_{|x|})=L(x).

advice 不依赖具体输入 $x$ ，但不要求可计算。它精确表达了非一致线路中每个长度可携带的信息。

Karp–Lipton theorem 给出非一致 upper bound 的结构后果：若

\mathsf{NP}\subseteq\mathsf{P/poly},

则 polynomial hierarchy collapse 到第二层。这不是已知矛盾，但被视为该包含关系不太可能成立的证据。

小深度复杂度类

常见 circuit 类包括：

$\mathsf{AC^0}$ ：多项式 size、常数 depth、unbounded fan-in AND/OR/NOT；
$\mathsf{TC^0}$ ：在 $\mathsf{AC^0}$ 基础上允许 threshold gate；
$\mathsf{NC^i}$ ：多项式 size、 $O(\log^i n)$ depth、bounded fan-in；
$\mathsf{NC}=\bigcup_i\mathsf{NC^i}$ 。

$\mathsf{NC}$ 通常代表具有多项式总工作量和 polylog 并行时间的问题。uniformity 条件决定它是否对应可执行并行算法。

$\mathsf{AC^0}$ lower bound

PARITY 计算输入中 1 的个数是否为奇数。它不属于 $\mathsf{AC^0}$ ：

\mathrm{PARITY}\notin\mathsf{AC^0}.

证明可使用 switching lemma：随机限制变量后，小深度 CNF/DNF 高概率简化为浅 decision tree；PARITY 在保留多个自由变量时仍对每个变量敏感，无法被这种结构表示。

这是强 lower bound，但模型限制很关键。加入 threshold gate 后，PARITY 属于 $\mathsf{TC^0}$ 。对一般多项式 size circuit，尚不能证明 NP 中显式问题需要超多项式 size。

Monotone circuit

monotone circuit 只允许 AND/OR，不允许 NOT，用于计算 monotone function。某些问题具有指数 monotone circuit lower bound，但允许否定后可能出现小线路。

这说明受限模型 lower bound 不自动推广到一般模型。它仍有价值，因为：

能识别某类算法框架的限制；
提供可分析的组合结构；
发展可能用于更强模型的证明技术。

Circuit 与机器计算

运行时间为 $t(n)$ 的图灵机计算可以展开为大小约 $\operatorname{poly}(t(n))$ 的 circuit；每个 gate 表示局部配置更新。因此

\mathsf P\subseteq\mathsf{P/poly}.

若 circuit family 具有适当 uniformity，则可由机器按层求值。depth 对应并行时间，size 对应工作量，但实际 PRAM 或硬件还需考虑 fan-out、布线和 memory contention。

本章自测

circuit 与 formula 的主要结构差异是什么？
为什么非一致多项式线路可以判定某些不可判定 unary language？
advice 为什么只能依赖输入长度而不能依赖具体输入？
PARITY 的 $\mathsf{AC^0}$ lower bound 为什么不能推广到 $\mathsf{TC^0}$ ？
circuit depth 与现实并行时间之间还缺少哪些成本？

第六章：电路与非一致计算 ​

Boolean function family ​

Formula、circuit 与 branching program ​

Uniformity ​

Advice 的等价刻画 ​

小深度复杂度类 ​

AC0\mathsf{AC^0}AC0 lower bound ​

Monotone circuit ​

Circuit 与机器计算 ​

本章自测 ​