Circuit complexity

Circuit complexity studies the size and depth of circuits computing finite-input functions.

A Boolean circuit is a finite directed acyclic graph of Boolean gates with designated inputs and outputs.

The circuit satisfiability problem asks whether a Boolean circuit has an input on which its designated output is one. It is NP-complete.

A circuit family $(C_n)$ contains one circuit for each input length $n$. The circuit for one length may be chosen independently of those for other lengths, so a family is a nonuniform model of computation.

A circuit family has polynomial size when $C_n$ has at most $n^{O(1)}$ gates.

$\mathbf{P}/\mathrm{poly}$ is the class of decision problems decided by polynomial-size circuit families.