无环的逻辑运算网络
布尔电路是表示布尔函数的抽象计算模型。输入节点承载0或1，内部节点执行与、或、非等逻辑运算，连线把输出送往后续节点。作为有向无环图，电路没有反馈环，因此可以按拓扑顺序逐门求值，最终读取指定输出。
这一定义抓住的是逻辑依赖，而不是实体芯片的全部性质。电压、晶体管尺寸、传播延迟和散热并未自动包含在模型中。讨论电路复杂度时，还须说明允许哪些门、每个门能接受多少输入，以及输出是否可以分送给多个门。
参考：[1]
异或例子中的大小与深度
以二输入异或为例，x⊕y可写成(x∧¬y)∨(¬x∧y)。若使用二输入与、或门和单输入非门，并把所有门都计入，则需要两个非门、两个与门和一个或门，共五个门；最长输入到输出路径经过三个门。这个计数明确了采用的门基和约定。
不同资料可能不计非门，或允许无界扇入，因此具体数值要随约定解释。大小衡量逻辑硬件量，深度衡量最长串行依赖链，两者不能互代。把多个异或单元排成平衡树，可用线性数量的门、对数深度计算多位奇偶性；串联结构则会有更长依赖链。
固定输入长度与统一生成
一个n输入电路只计算从{0,1}^n到输出位的函数。要处理任意长度字符串，需要为每个n指定电路C_n，形成电路族。仅要求这些电路分别存在，并没有要求一个算法能够生成它们，这便是非统一计算的重要特点。
P中的语言都有多项式大小电路族，但反向不能仅凭大小成立；无限电路族的选择可以携带不可计算的信息。统一性条件把生成过程也纳入约束，例如要求一台多项式时间图灵机在输入1^n时输出C_n的描述。这样才把“每个长度有一个小电路”与“存在统一有效的构造算法”区分开。