电路族一致性

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

多项式时间 TM 可展开为多项式大小的一致电路族；加法器或排序网络也能由统一规则生成。相反，一元语言可让 $C_n$ 硬编码 $1^n$ 是否属于语言，形成很小却未必可计算生成的非一致族。每张电路有限不代表整族一致，P-uniform、logspace-uniform 与 DLOGTIME-uniform 的资源标签也不能省略。

“每张电路都有限且容易画出”不等于族一致；要求涉及所有 $n$ 的单一生成器。P-uniform、logspace-uniform 与 DLOGTIME-uniform 不是可随意互换的标签，在 $NC$、$A{C}^0$ 等细粒度结果中差别会进入定理陈述。

一致性把布尔电路公理库布尔电路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 或更强条件。各电路类不反向成为“一致性”概念的理解前置。