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 edit

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 edit

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 edit

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 edit

A circuit family is an infinite list of circuits $(C_{0},C_{1},C_{2},...)$ , where $C_{n}$ has $n$ input variables. In other words, for every possible 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 edit

Complexity measures edit

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 edit

The complexity measures described above enable the use of different classes of functions to define complexity classes over circuit families. One essential such class, known as P/poly, is the circuit analogue to the time-complexity class P. This class is defined as the class of circuits for which the circuit size complexity function $f$ is a polynomial.^[3] P/poly is not only an intuitive analogue to P, but it also has number of properties that make it highly useful in the study of the relationships between complexity classes. In particular, it is helpful in investigating problems related to P versus NP. For example, it is known that if there is any language in NP that is not in P/poly, then P $\neq$ NP.^[4] P/poly also aids in the general study of Turing machines, for it can be equivalently be defined as the class of languages recognized by a polynomial-time Turing machine with a polynomial-bounded advice function.

Relation to time complexity edit

There turns out to be 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))$ .^[5]

It follows directly from this result that P $\subseteq$ P/poly. It is further known that P/poly is strictly larger than P (i.e. P $\subsetneq$ P/poly); that is, there are languages that are known to be in P/poly that are not in P.

Notes edit

^ Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). USA: Thomson Course Technology. pp. 352–353. ISBN 978-0-534-95097-2.
^ Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). USA: Thomson Course Technology. p. 354. ISBN 978-0-534-95097-2.
^ Arora, Sanjeev; Barak, Boaz (2009). Computational Complexity: A Modern Approach. Cambridge University Press. p. 108. ISBN 978-0-521-42426-4.
^ Arora and Barak p. 286
^ Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). USA: Thomson Course Technology. p. 355. ISBN 978-0-534-95097-2.

[1] Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). USA: Thomson Course Technology. pp. 352–353. ISBN 978-0-534-95097-2.

[2] Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). USA: Thomson Course Technology. p. 354. ISBN 978-0-534-95097-2.

[3] Arora, Sanjeev; Barak, Boaz (2009). Computational Complexity: A Modern Approach. Cambridge University Press. p. 108. ISBN 978-0-521-42426-4.

[4] Arora and Barak p. 286

[5] Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). USA: Thomson Course Technology. p. 355. ISBN 978-0-534-95097-2.

[1]

[2]

[3]

[4]

[5]