在计算复杂性理论和电路复杂性理论中，布尔电路是数字逻辑电路的数学模型。一种形式语言可以通过一族布尔电路确定，其中一个电路对应一个可能的输入长度。在数字电子学中，布尔电路也被用作组合逻辑的形式模型。
布尔电路是根据其包含的“逻辑门”来定义的。例如，一个电路可能包含二元“与”和“或”门以及一元“非”门，或者完全由二元“与非”门描述。每个门对应于一个布尔函数，该函数以固定位数作为输入，只输出一位。
布尔电路为计算机工程中使用的许多数字元件提供了模型，包括多路复用器、加法器和算术逻辑单元。
在给出布尔电路的形式化定义时，沃尔默首先将基定义为布尔函数的集合B，对应于电路模型中容许的门。然后，一个基于B的，有n个输入和m个输出的布尔电路被定义为一个有限有向无环图。每个顶点对应于一个基函数或一个输入，并且恰好存在一组m个节点被标记为输出。[1]图上的边还必须有某种顺序，以区分同一个布尔函数的不同参数。[2]
作为一种特例，命题公式（或布尔表达式）也是一个布尔电路，它只有一个输出节点，其他每个节点的扇出系数都为1。因此，布尔电路可以被视为允许共享子式和多个输出的一般形式。
所有布尔电路的一个共同基是集合{与，或，非}，该集合是功能完备的，也就是说，所有其他布尔函数都可以从这个集合中构造出来。
电路求值问题，即在给定输入串上计算给定布尔电路的输出问题，是一个P-完全决策问题。[3]因此，这个问题被认为是“内在有序”的，这意味着该问题不能通过高效、高度并行的算法来解决。
在布尔电路中可以定义几种重要的复杂度度量，包括电路深度、电路规模以及与门和或门之间的交替次数。例如，布尔电路的规模复杂度就是门的数量。
在布尔电路中定义了几个重要的复杂度类，其中包括NC类。NC类被定义为一组布尔函数，这些函数可以由统一的多项式大小和多对数深度的布尔电路决定。这里，“统一”意味着电路族上必须存在某种条件，以便仅根据电路的输入数量来推断电路的类型。
暂无