形式陈述

电路大小通常是门数（有时连同导线数），深度是从输入到输出的最长门路径长度。大小近似总工作量，深度是在无限处理器且每门单位延迟下的并行时间。对有界扇入门，深度 $d$$d$ 的单输出电路最多依赖 $2^d$$2^d$ 个输入，因此全局函数常需 $\Omega(\log n)$$\mathrm{\Omega }(\log n)$ 深度；无界扇入模型不满足该简单下界。电路族的大小、深度都是输入长度 $n$$n$ 的函数。

直觉

门数回答“总共做多少局部操作”，深度回答“关键路径上必须串行等待多少轮”。同样大小的图可以因依赖组织不同而具有完全不同延迟。

例子与边界

平衡二叉树计算 $n$$n$ 位 OR，大小 $n-1$$n-1$、深度 $\lceil\log_2 n\rceil$$\lceil {\log }_{2}n\rceil$；链式 OR 大小同阶但深度 $n-1$$n-1$。若允许一个无界扇入 OR 门，深度可降为 1，因此讨论 AC/NC 时必须说明扇入。门的位复杂度也重要：把任意真值表当作一个“超级门”会使大小失去意义。最小电路大小通常难以计算，存在上界构造不等于已证明下界最优。

推论与应用

大小—深度权衡用于并行算法、硬件时序、VLSI 与电路复杂性；许多下界正是证明某函数无法同时拥有很小尺寸和很浅深度。

参考资料

• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009，Chs. 1–8。
• Stasys Jukna, Boolean Function Complexity: Advances and Frontiers, Springer, 2012，Chs. 1–6。