Circuit complexity

In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of Boolean circuits that compute them. One speaks of the circuit complexity of a Boolean circuit. A related notion is the circuit complexity of a recursive language that is decided by a family of circuits ${\displaystyle C_{1},C_{2},\ldots }$ (see below).

A Boolean circuit with ${\displaystyle n}$ input bits is a directed acyclic graph in which every node (usually called gates in this context) is either an input node of in-degree 0 labeled by one of the ${\displaystyle n}$ input bits, an AND gate, an OR gate, or a NOT gate. One of these gates is designated as the output gate. Such a circuit naturally computes a function of its ${\displaystyle n}$ inputs. The size of a circuit is the number of gates it contains and its depth is the maximal length of a path from an input gate to the output gate.

...
Wikipedia