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.

Circuit complexity

Main article: Circuit complexity

Several important complexity measures can be defined on Boolean circuits, including circuit depth, circuit size, and number of alternations between AND gates and OR gates. For example, the size complexity of a Boolean circuit is the number of gates.

It turns out that there is a natural connection between circuit size complexity and time complexity. Intuitively, a language with small time complexity (that is, requires relatively few sequential operations on a Turing machine), also has a small circuit complexity (that is, requires relatively few Boolean operations). Formally, it can be shown that if a language is in ${\mathsf {TIME}}(t(n))$, where $t$ is a function $t:\mathbb {N} \to \mathbb {N}$, then it has circuit complexity $O(t^{2}(n))$.

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.