电路规模与深度

规模统计总门数，回答“总共做多少局部操作”，近似衡量硬件面积或总工作；深度统计输入到输出的最长依赖链，回答“关键路径上必须串行等待多少轮”，近似衡量门可并行执行时的延迟。同样大小的图可以因依赖组织不同而具有完全不同延迟，两者也可以互相权衡：复制中间结果可能增大规模却减少串行依赖，复用子电路则可能相反。只有在门基、fan-in 和 uniformity 固定后，规模与深度比较才有明确含义。

以八个输入的 OR 为例，第一层用四个门合并相邻输入，第二层用两个门合并前一层结果，第三层再用一个门输出，合计 $4+2+1=7$ 个门、深度 $3$。链式写法则依次把下一个输入并入当前结果，同样用七个门，却必须等七轮。对 $n\ge 1$，平衡二叉树有 $n-1$ 个门、深度 $\lceil {\log }_{2}n\rceil$；AND 完全同理。这个对比依靠结合律重新组织依赖，并没有减少总运算次数。若允许无界 fan-in，同一函数可由一个 OR 或 AND 门完成、深度降为 1，因此讨论 AC/NC 时必须说明扇入。

门的位复杂度也重要：把任意真值表当作一个“超级门”会使大小失去意义。最小电路大小通常难以计算，存在上界构造不等于已证明下界最优。

深度不是处理器数量：即使深度很小，某一层可能含多项式个门，需要相应并行资源。规模下界也不能自动推出深度下界；反之，一条长依赖链可能由很少门构成。

大小—深度权衡用于并行算法、硬件时序、VLSI 与电路复杂性；许多下界正是证明某函数无法同时拥有很小尺寸和很浅深度。典型例子是AC⁰理路AC⁰AC0 · AC^0 · Constant-depth unbounded-fan-in circuits由多项式规模、常数深度、无界扇入 AND/OR 门电路族计算的布尔函数类。：它允许多项式规模和无界扇入，却把深度固定为常数；Parity 不属于 AC⁰理路Parity 不属于 AC⁰Parity not in AC0 · AC0 parity lower bound逐层核算独立随机限制、决策树转换与失败概率，在保留自由变量的同一实验中证明 PARITY 的常深电路指数下界。说明这些限制足以排除一个有线性规模、对数深度电路的简单函数。

它细化 布尔电路理路布尔电路Boolean circuit由逻辑门构成的有限无环有向图，计算布尔函数。 的资源分析，并在 NC理路复杂性类 NCNick's Class · NC由多项式规模、多对数深度的有界扇入电路族判定的语言类，并区分一致与非一致版本。 中把多项式规模与 polylog 深度结合起来。一致性理路电路族一致性Circuit family uniformity要求输入长度 n 对应电路可由统一算法有效生成的条件。 保证这些资源受控的电路可被统一生成；电路下界研究则试图证明某些函数在给定门基下必须使用超多项式规模或大深度。