Editing Complexity class (section)

===Boolean circuits===
{{Main|Circuit complexity}}
[[File:Three input boolean circuit.svg|thumb|right|350px|Example Boolean circuit computing the Boolean function <math>f_C(x_1,x_2,x_3)=\neg (x_1 \wedge x_2) \wedge ((x_2 \wedge x_3) \vee \neg x_3)</math>, with example input <math>x_1=0</math>, <math>x_2=1</math>, and <math>x_3=0</math>. The <math>\wedge</math> nodes are [[AND gate]]s, the <math>\vee</math> nodes are [[OR gate]]s, and the <math>\neg</math> nodes are [[NOT gate]]s.]]
An alternative model of computation to the [[Turing machine]] is the '''[[Boolean circuit]]''', a simplified model of the [[digital circuit]]s used in modern [[computer]]s. Not only does this model provide an intuitive connection between computation in theory and computation in practice, but it is also a natural model for [[non-uniform computation]] (computation in which different input sizes within the same problem use different algorithms).

Formally, a Boolean circuit <math>C</math> 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 gate]]s (generally the [[AND gate|AND]], [[OR gate|OR]], and [[NOT gate]]s). One logic gate is designated the output gate, and represents the end of the computation. The input/output behavior of a circuit <math>C</math> with <math>n</math> input variables is represented by the [[Boolean function]] <math>f_C:\{0,1\}^n \to \{0,1\}</math>; for example, on input bits <math>x_1,x_2,...,x_n</math>, the output bit <math>b</math> of the circuit is represented mathematically as <math>b = f_C(x_1,x_2,...,x_n)</math>. The circuit <math>C</math> is said to ''compute'' the Boolean function <math>f_C</math>.

Any particular circuit has a fixed number of input vertices, so it can only act on inputs of that size. [[Formal language|Languages]] (the formal representations of [[decision problem]]s), however, contain strings of differing lengths, so languages cannot be fully captured by a single circuit (this contrasts with the Turing machine model, in which a language is fully described by a single Turing machine that can act on any input size). A language is thus represented by a '''circuit family'''. A circuit family is an infinite list of circuits <math>(C_0,C_1,C_2,...)</math>, where <math>C_n</math> is a circuit with <math>n</math> input variables. A circuit family is said to decide a language <math>L</math> if, for every string <math>w</math>, <math>w</math> is in the language <math>L</math> if and only if <math>C_n(w)=1</math>, where <math>n</math> is the length of <math>w</math>. In other words, a string <math>w</math> of size <math>n</math> is in the language represented by the circuit family <math>(C_0,C_1,C_2,...)</math> if the circuit <math>C_n</math> (the circuit with the same number of input vertices as the number of bits in <math>w</math>) evaluates to 1 when <math>w</math> is its input.

While complexity classes defined using Turing machines are described in terms of [[time complexity]], circuit complexity classes are defined in terms of circuit size — the number of vertices in the circuit. The size complexity of a circuit family <math>(C_0,C_1,C_2,...)</math> is the function <math>f:\mathbb{N} \to \mathbb{N}</math>, where <math>f(n)</math> is the circuit size of <math>C_n</math>. The familiar function classes follow naturally from this; for example, a polynomial-size circuit family is one such that the function <math>f</math> is a [[polynomial]].

====Important complexity classes====
The complexity class '''[[P/poly]]''' is the set of languages that are decidable by polynomial-size circuit families. It turns out that there is a natural connection between circuit 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 <math>\mathsf{DTIME}(t(n))</math>, where <math>t</math> is a function <math>t:\mathbb{N} \to \mathbb{N}</math>, then it has circuit complexity <math>O(t^2(n))</math>.{{sfn|Sipser|2006|p=355}} It follows directly from this fact that [[P (complexity)|<math>\mathsf{\color{Blue}P}\subset\textsf{P/poly}</math>]]. In other words, any problem that can be solved in polynomial time by a deterministic Turing machine can also be solved by a polynomial-size circuit family. It is further the case that the inclusion is proper, i.e. <math>\textsf{P}\subsetneq \textsf{P/poly}</math> (for example, there are some [[undecidable problem]]s that are in '''P/poly''').

'''P/poly''' has a 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|'''P''' versus '''NP''']]. For example, if there is any language in '''NP''' that is not in '''P/poly''', then <math>\mathsf{P}\neq\mathsf{NP}</math>.{{sfn|Arora|Barak|2009|p=286}} '''P/poly''' is also helpful in investigating properties of the [[polynomial hierarchy]]. For example, if '''[[NP (complexity)|NP]]''' ⊆ '''P/poly''', then '''PH''' collapses to <math>\Sigma_2^{\mathsf P}</math>. A full description of the relations between '''P/poly''' and other complexity classes is available at "[[P/poly#Importance of P/poly|Importance of P/poly]]". '''P/poly''' is also helpful in the general study of the properties of [[Turing machine]]s, as the class can be equivalently defined as the class of languages recognized by a polynomial-time Turing machine with a polynomial-bounded [[advice (complexity)|advice function]].

Two subclasses of '''P/poly''' that have interesting properties in their own right are '''[[NC (complexity)|NC]]''' and '''[[AC (complexity)|AC]]'''. These classes are defined not only in terms of their circuit size but also in terms of their '''depth'''. The depth of a circuit is the length of the longest [[directed path]] from an input node to the output node. The class '''NC''' is the set of languages that can be solved by circuit families that are restricted not only to having polynomial-size but also to having polylogarithmic depth. The class '''AC''' is defined similarly to '''NC''', however gates are allowed to have unbounded fan-in (that is, the AND and OR gates can be applied to more than two bits). '''NC''' is a notable class because it can be equivalently defined as the class of languages that have efficient [[parallel algorithm]]s.