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

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}$ .^[1]

Formal languages

Computational problems are represented as collections of strings known as languages. In the Turing machine model, a particular language can be defined as the set of input strings that a Turing machine running a particular algorithm accepts. For example, a Turing machine can run an algorithm that accepts all strings that contain only zeros; this Turing machine is said to accept the language $L=\{0^{n}|n\geq 0\}$ . It will be shown below how a circuit family can similarly be used to define a 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

Complexity measures

The complexity measures of Boolean circuits naturally extend to circuit families. The two most important such complexity measures are size (the number of nodes in a circuit) and depth (the length of the longest directed path from an input node to the output node).

Circuit size generalizes in the following way: 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}$ .^[2] In other words, the size complexity of a circuit family is a function that maps the input size to the number of nodes in the circuit in the circuit family corresponding to that input size. Circuit depth extends to circuit families in a similar manner.

Complexity classes

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). More explicitly, 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))$ .^[3]