电路族一致性

一族电路像每种输入长度各有一块专用芯片，但若这些芯片可以任意指定，族本身就可能把无限答案表藏在“设计图”里。一致性要求存在一个资源受限的通用过程，根据 $1^n$ 或门索引生成第 $n$ 张电路及其连线；生成规则使所有输入长度上的电路共享同一个有效构造。不同的一致性强度会影响极小深度电路类，必须与电路基和编码方式一同说明。

对运行 $T(n)$ 步的固定机器，可让第 $t$ 层编码时刻 $t$ 的配置，并用固定局部逻辑算出下一层；用“时间、纸带位置、局部位编号”遍历门，就能统一生成这张计算展开图。若 $T(n)$ 是多项式，展开规模也是多项式。这才把同一程序在不同长度上的运行连成一族，而非分别猜出每张电路。

反例取一个不可判定的一元语言 $U\subseteq \{1{\}}^{\ast }$。以一元字母表作为输入域时，第 $n$ 张电路只需硬编码常量 $[1^n\in U]$；若采用二进制输入域，还须先检查所有位是否为 $1$，规模仍为 $O(n)$。假如存在可计算生成器，生成 $C_n$ 再求值即可判定 $U$，矛盾。因此“小电路逐长度存在”甚至不保证语言可判定。

一致性把布尔电路理路布尔电路Boolean circuit由逻辑门构成的有限无环有向图，计算布尔函数。族与图灵机理路图灵机Turing machine通过有限控制、可读写纸带和移动读写头刻画一般算法计算能力的模型。的统一算法联系起来。P/poly理路非一致电路类 P/polyP/poly · Nonuniform polynomial size由每个输入长度各自选取的多项式规模布尔电路族判定、无需统一生成算法的语言类。允许非一致的多项式规模电路族，相当于为每个输入长度提供多项式长度的 advice；AC⁰理路AC⁰AC0 · AC^0 · Constant-depth unbounded-fan-in circuits由多项式规模、常数深度、无界扇入 AND/OR 门电路族计算的布尔函数类。再叠加常深、无界扇入和门基，并分别标注 uniform 或 nonuniform 版本。NC理路复杂性类 NCNick's Class · NC由多项式规模、多对数深度的有界扇入电路族判定的语言类，并区分一致与非一致版本。通常采用 logspace-uniform 或更强条件。