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

Example Boolean circuit computing the Boolean function $f_{C}(x_{1},x_{2},x_{3})$, where $x_{1}=0$, $x_{2}=1$, and $x_{3}=0$. The $\wedge$ nodes are AND gates, the $\vee$ nodes are OR gates, and the $\neg$ nodes are NOT gates.

Boolean circuits

Main article: Boolean circuit

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}$.

Circuit families are a particular kind of collection of these Boolean circuits.

Formal languages

Main article: Formal language

Formal definition

A circuit family is an infinite list of circuits $(C_{0},C_{1},C_{2},...)$, where $C_{n}$ has $n$ input variables. This means that, for every input size, there is exactly one corresponding circuit in the circuit family.

A circuit family is said to decide a language $L$ if, for every string $w$, $w\in 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

See also

• Circuit satisfiability
• Logic gate
• Boolean logic

References

• Arora, Sanjeev; Barak, Boaz (2009). Computational Complexity: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4.
• Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). USA: Thomson Course Technology. ISBN 978-0-534-95097-2.