电路规模与深度

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

平衡二叉树计算 $n$ 位 OR，大小 $n-1$、深度 $\lceil {\log }_{2}n\rceil$；链式 OR 大小同阶但深度 $n-1$。同理，用二叉树计算 $n$ 个比特的 AND 需要 $n-1$ 个二输入 AND 门，规模 $O(n)$、深度 $O(\log n)$；串行链同样规模 $O(n)$，深度却为 $O(n)$。若允许无界 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证明任何多项式规模、常数深度、无界扇入 AND/OR/NOT 电路族都不能计算奇偶函数。说明这些限制足以排除一个有线性规模、对数深度电路的简单函数。

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