|
'''Circuit complexity''' is a topic in [[computational complexity theory]], a branch of [[theoretical computer science]] which classifies [[booleanBoolean function]]s according to the amount of [[computational resource]]s needed to compute them. In circuit complexity, these resources are size and depth of [[booleanBoolean circuit]]s.
A booleanBoolean circuit with ''n'' input [[bit]]s is a [[directed acyclic graph]] in which every node (usually called ''gates'' in this context) is either an input node of [[in-degree]] 0 labeled by one of the ''n'' input bits, an [[AND gate]], an [[OR gate|OR]] or a [[NOT gate]]. One of these gates is designated as the output gate. Such a circuit naturally computes a function of its ''n'' inputs. The size of a circuit is the number of gates it contains and its depth is the maximal length of a path from an input gate to the output gate.
The circuit-size (respectively circuit-depth) complexity of a booleanBoolean function ''f'' is the minimal size (respectively minimal depth) of any circuit computing ''f''. The goal of circuit complexity is to determine this optimal size/depth for natural families of booleanBoolean functions. Most often the challenge involves the study of the [[asymptotic analysis|asymptotic behavior]] of size or depth complexity for sequences of booleanBoolean functions <math>f_1, f_2, ... </math> where each <math>f_n</math> is a function of ''n'' bits.
[[Complexity class]]es defined in terms of booleanBoolean circuits include [[AC0|AC<sup>0</sup>]], [[AC (complexity)|AC]], [[TC0|TC<sup>0</sup>]] and [[NC (complexity)|NC]].
==Uniformity==
Boolean circuits are one of the prime examples of so-called [[uniformity (complexity)|non-uniform]] [[abstract machine|models of computation]] in the sense that inputs of different lengths are processed by different circuits, in contrast with uniform models such as [[Turing machine]]s where the same computational device is used for all possible input lengths. An individual [[computational problem]] is thus associated with a particular ''family'' of booleanBoolean circuits <math>C_1, C_2, ... </math> where each <math>C_n</math> is the circuit handling inputs of ''n'' bits. A [[uniformity (complexity)|uniformity]] condition is often imposed on these families so that each individual circuit can be computed by some [[computational resource|resource-bounded]] Turing machine.
==History==
===Key results===
*The booleanBoolean function [[parity function|PARITY]], which is 1 if and only if the sum of its input bits is odd, does not lie in <math>AC^0</math>. The result was first established independently by Ajtai (1983) and by Furst, Saxe and Sipser (1984). Later improvements by Hastad (1987) in fact establish that any family of <math>AC^0</math> computing PARITY requires exponential size. Smolensky (1986) proved that this is true even if the circuit is augmented with gates computing the sum of its input bits modulo some odd prime p.
* Consider the [[clique problem]] of determining whether a graph with ''n'' vertices has a clique of size ''k''. For any particular choice of ''n'' and ''k'' this can be encoded as a booleanBoolean function on ''n''(''n''−1) inputs, one for each pair of vertices, specifying whether or not that edge is in the graph. This family of functions is monotone and can be computed by a family of circuits, but it has been shown that it cannot be computed by a polynomial-size family of monotone circuits (that is, circuits with AND and OR gates but no negation). This original result of [[Alexander Razborov|Razborov]] (1985) was later improved to an exponential-size lower bound by Alon and Boppana (1987). Raz and McKenzie later showed that the monotone NC hierarchy is infinite (1999).
*Division lies in uniform [[TC0|TC<sup>0</sup>]] (Hesse 2001).
==Complexity classes==
| 