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

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 circuit corresponding to their length, evaluate to 1.

Circuit complexity

Main article: Circuit complexity

Complexity measures

The size of a circuit is the number of vertices in it. The size complexity of a circuit family $(C_{0},C_{1},...)$ is the function $f:\mathbb {N} \to \mathbb {N}$, where $f(n)$ is the circuit size of $C_{n}$. This enables the use of function classes to defined complexity classes over circuit families; for example, a circuit analogue to P can be defined as the class of circuits for which $f$ is a polynomial (indeed, this class is known as P/poly and is described in greater detail below).

Complexity classes

Main article: Complexity class § Boolean circuit

Relation to time complexity

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.