Circuit complexity is a measure of how hard it is to express or compute a boolean function.

Boolean Functions

Boolean functions can be classified according to the size or depth of the Boolean circuits that compute them.

A Boolean circuit with $n$ input bits is a directed acyclic graph in which every node is either an input node labelled by one of the $n$ input bits, an AND gate, an OR gate, or a NOT gate. The input node has in-degree 0, the AND gate has in-degree 2,

A Motivating Example

Circuit Lower Bound

$NC^0\subsetneq AC^0 \subsetneq TC^0\subset NC^1 \subset P$