作为计算模型的电路是一个有向无回图（directed acyclic graph，简称dag），入度为0的节点称为输入（input）节点，标记为常数或输入变元，出度为0的节点称为输出（output）节点，可以有多个输出。入度不为0的节点称为门（gate），标记有运算。布尔电路（Boolean circuit）允许的运算有与（and）、或（or）、非（not），单调布尔电路（monotone Boolean circuit）允许的运算只有与、或。代数电路（algebraic circuit）或算术电路（arithmatic circuit）允许某个域上的加、乘等运算。给定输入后，从输入节点开始，依次计算每个门的输出，直到输出节点为止，输出节点的值就是函数值。

电路的规模通常是指电路的节点数或边数，而边数至多是节点数的平方。电路的深度是从输入到输出的最长路线上的边数。电路的扇入（fan-in）度是指所有门的最大入度，扇出（fan-out）度是所有门的最大出度。对于一个n元布尔函数，如果在所有长度为n的0-1输入上，布尔电路都正确输出函数的值，则称电路计算这个函数。给定一个函数，规模最优电路是计算这个函数的规模最小电路，深度最优电路是计算这个函数的深度最小电路。一个函数的电路复杂性通常是指计算这个函数的最优电路的规模或深度。

通过限制电路的规模或深度，可以得出一些电路复杂性类，常见的有多项式规模电路P/poly类，多项式规模、O(log^kn)深度电路AC^k类，多项式规模、O(log^kn)深度、扇入度为2的电路NC^k类等。

与图灵机不同，电路是非一致（nonuniform）计算模型，在每个输入长度上需要一个不同的电路，计算一个函数需要一族无穷多个电路。因此上述非一致电路族中甚至包含不可计算问题。如果要求这一族电路可以由一个图灵机产生（该图灵机在输入1ⁿ上输出电路C_n的编码，而电路C_n负责计算长度为n的输入的函数值），则这族电路称为一致电路（uniform circuit）。一致电路等价于图灵机，比如，确定型多项式时间图灵机等价于对数空间一致（计算电路的图灵机在对数空间内运行）的多项式规模电路，所以多项式时间P类等于对数空间一致的多项式规模电路（L一致P/poly）类。对于其他常见的时间和空间复杂性类，也有类似的电路复杂性类的刻画。

由所有对数空间一致的NC^k类组成的对数空间一致NC类（），表示了在并行计算下易解的问题类。NC类是否等于P类的问题，类似于P类是否等于NP类的问题。如果利用对数空间归约证明一个问题是P完全问题，就给出了该问题在并行计算下难解（不属于NC类）的证据，这类似于如果利用多项式时间归约证明一个问题是NP完全问题，就给出了该问题在串行计算下难解（不属于P类）的证据。

为了彻底证明某个NP类中的问题不属于P类（这等价于证明P≠NP），只需证明该问题具有指数规模的电路复杂性。早在20世纪40年代，C.E.香农采用计数法（counting），通过比较n元布尔函数的个数与给定规模的电路的个数，证明了大多数布尔函数都需要指数规模的电路。到了20世纪80年代，针对NP中的具体问题或函数，对于受限制的布尔电路，比如单调布尔电路或者限制深度为常数的布尔电路（NC⁰电路），证明出电路复杂性的指数规模下界；而对于一般布尔电路，截至2020年，能证明的最好的规模下界是线性的。在计算复杂性中，电路复杂性的下界证明是难度很大、富有挑战性的研究方向。