User:Jaydavidmartin/Circuit complexity

In computational complexity theory, a circuit family is an infinite list of Boolean circuits that represents a formal language. Each circuit in the circuit family has a different input size.

Background

Boolean circuits are simplified models of the digital circuits used in modern computers. Formally, a Boolean circuit $C$ is a directed acyclic graph in which edges represent wires (which carry the bit values 0 and 1), the input bits are represented by source vertices (vertices with no incoming edges), and all non-source vertices represent logic gates (generally the AND, OR, and NOT gates). One logic gate is designated the output gate, and represents the end of the computation. The input/output behavior of a circuit $C$ with $n$ input variables is represented by the Boolean function $f_{C}:\{0,1\}^{n}\to \{0,1\}$; for example, on input bits $x_{1},x_{2},...,x_{n}$, the output bit $b$ of the circuit is represented mathematically as $b=f_{C}(x_{1},x_{2},...,x_{n})$. The circuit $C$ is said to compute the Boolean function $f_{C}$.

Formal definition

A circuit family is an infinite list of circuits $(C_{0},C_{1},C_{2},...)$, where $C_{n}$ has $n$ input variables.

A circuit family is said to decide a language $L$ if, for every string $w$, $w$ is in the language $L$ if and only if $C_{n}(w)=1$, where $n$ is the length of $w$. In other words, a language is the set of strings which, when applied to the circuits corresponding to their lengths, evaluate to 1