Circuit complexity
Model of computational complexity
Top 10 Circuit complexity related articles

Contents
In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circuit complexity of a recursive language that is decided by a uniform family of circuits $C_{1},C_{2},\ldots$
Proving lower bounds on size of Boolean circuits computing explicit Boolean functions is a popular approach to separating complexity classes. For example, a prominent circuit class P/poly consists of Boolean functions computable by circuits of polynomialsize. Proving that $NP\not \subseteq P/poly$
Complexity classes defined in terms of Boolean circuits include AC^{0}, AC, TC^{0}, NC^{1}, NC, and P/poly.
Circuit complexity Intro articles: 4
Size and Depth
A Boolean circuit with $n$
There are two major notions of circuit complexity (these are outlined in Sipser (1997)^{[1]}^{:324}). The circuitsize complexity of a Boolean function $f$
These notions generalize when one considers the circuit complexity of any language that contains strings with different bit lengths, especially infinite formal languages. Boolean circuits, however, only allow a fixed number of input bits. Thus no single Boolean circuit is capable of deciding such a language. To account for this possibility, one considers families of circuits $C_{1},C_{2},\ldots$
Hence, the circuitsize complexity of a formal language $A$
Circuit complexity Size and Depth articles: 7
Uniformity
Boolean circuits are one of the prime examples of socalled nonuniform models of computation in the sense that inputs of different lengths are processed by different circuits, in contrast with uniform models such as Turing machines where the same computational device is used for all possible input lengths. An individual computational problem is thus associated with a particular family of Boolean circuits $C_{1},C_{2},\dots$
Polynomialtime uniform
A family of Boolean circuits $\{C_{n}:n\in \mathbb {N} \}$
 M runs in polynomial time
 For all $n\in \mathbb {N}$
, M outputs a description of $C_{n}$ on input $1^{n}$
Logspace uniform
A family of Boolean circuits $\{C_{n}:n\in \mathbb {N} \}$
 M runs in logarithmic space
 For all $n\in \mathbb {N}$
, M outputs a description of $C_{n}$ on input $1^{n}$
Circuit complexity Uniformity articles: 6
History
Circuit complexity goes back to Shannon (1949), who proved that almost all Boolean functions on n variables require circuits of size Θ(2^{n}/n). Despite this fact, complexity theorists have only been able to prove superpolynomial circuit lower bounds on functions explicitly constructed for the purpose of being hard to calculate.
More commonly, superpolynomial lower bounds have been proved under certain restrictions on the family of circuits used. The first function for which superpolynomial circuit lower bounds were shown was the parity function, which computes the sum of its input bits modulo 2. The fact that parity is not contained in AC^{0} was first established independently by Ajtai (1983)^{[2]} and by Furst, Saxe and Sipser (1984).^{[3]} Later improvements by Håstad (1987) in fact establish that any family of constantdepth circuits computing the parity function requires exponential size. Extending a result of Razborov, Smolensky (1987) 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.
The kclique problem is to decide whether a given graph on n vertices has a clique of size k. For any particular choice of the constants n and k, the graph can be encoded in binary using ${n \choose 2}$
Raz and McKenzie later showed that the monotone NC hierarchy is infinite (1999).
The Integer Division Problem lies in uniform TC^{0} (Hesse 2001).
Circuit complexity History articles: 7
Circuit lower bounds
Circuit lower bounds are generally difficult. Known results include
 Parity is not in nonuniform AC^{0}, proved by Ajtai (1983) and by Furst, Saxe and Sipser.
 Uniform TC^{0} is strictly contained in PP, proved by Allender.
 The classes S^{P}
_{2}, PP^{[4]} and MA/1^{[5]} (MA with one bit of advice) are not in SIZE(n^{k}) for any constant k.  While it is suspected that the nonuniform class ACC^{0} does not contain the majority function, it was only in 2010 that Williams proved that ${\mathsf {NEXP}}\not \subseteq {\mathsf {ACC}}^{0}$
.^{[6]}
It is open whether NEXPTIME has nonuniform TC^{0} circuits.
Proofs of circuit lower bounds are strongly connected to derandomization. A proof that ${\mathsf {P}}={\mathsf {BPP}}$
Razborov and Rudich (1997) showed that many known circuit lower bounds for explicit Boolean functions imply the existence of so called natural properties useful against the respective circuit class.^{[8]} On the other hand, natural properties useful against P/poly would break strong pseudorandom generators. This is often interpreted as a ``natural proofs" barrier for proving strong circuit lower bounds. Carmosino, Impagliazzo, Kabanets and Kolokolova (2016) proved that natural properties can be also used to construct efficient learning algorithms.^{[9]}
Circuit complexity Circuit lower bounds articles: 7
Complexity classes
Many circuit complexity classes are defined in terms of class hierarchies. For each nonnegative integer i, there is a class NC^{i}, consisting of polynomialsize circuits of depth $O(\log ^{i}(n))$
Relation to time complexity
Say that a certain language, $A$
Notes
 ^ ^{a} ^{b} Sipser, M. (1997). 'Introduction to the theory of computation.' Boston: PWS Pub. Co.
 ^ Ajtai, Miklós; Komlós, János; Szemerédi, Endre (1983). An 0(n log n) sorting network. STOC '83 Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing. pp. 1–9. ISBN 9780897910996.
 ^ Furst, Merrick; Saxe, James B.; Sipser, Michael (1984). "Parity, circuits, and the polynomialtime hierarchy". Mathematical Systems Theory. 17 (1): 13–27. doi:10.1007/BF01744431. MR 0738749.
 ^ See proof
 ^ Santhanam, Rahul (2007). "Circuit lower bounds for MerlinArthur classes". STOC 2007: Proceedings of the thirtyninth annual ACM symposium on Theory of computing. pp. 275–283. CiteSeerX 10.1.1.92.4422. doi:10.1145/1250790.1250832.
 ^ Williams, Ryan (2011). "NonUniform ACC Circuit Lower Bounds" (PDF). CCC 2011: Proceedings of the 26th Annual IEEE Conference on Computational Complexity. pp. 115–125. doi:10.1109/CCC.2011.36.
 ^ Kabanets, V.; Impagliazzo, R. (2004). "Derandomizing polynomial identity tests means proving circuit lower bounds". Computational Complexity. 13 (1): 1–46. doi:10.1007/s0003700401826.
 ^ Razborov, Alexander; Rudich, Stephen (1997). "Natural proofs". Journal of Computer and System Sciences. 55. pp. 24–35.
 ^ Carmosino, Marco; Impagliazzo, Russell; Kabanets, Valentine; Kolokolova, Antonina (2016). "Learning algorithms from natural proofs". Computational Complexity Conference.
References
 Ajtai, Miklós (1983). "$\Sigma _{1}^{1}$
formulae on finite structures". Annals of Pure and Applied Logic. 24: 1–24. doi:10.1016/01680072(83)900386.  Alon, Noga; Boppana, Ravi B. (1987). "The monotone circuit complexity of Boolean functions". Combinatorica. 7 (1): 1–22. CiteSeerX 10.1.1.300.9623. doi:10.1007/bf02579196.
 Furst, Merrick L.; Saxe, James B.; Sipser, Michael (1984). "Parity, circuits, and the polynomialtime hierarchy". Mathematical Systems Theory. 17 (1): 13–27. doi:10.1007/bf01744431.
 Håstad, Johan (1987), Computational limitations of small depth circuits (PDF), Ph.D. thesis, Massachusetts Institute of Technology.
 Hesse, William (2001). "Division is in uniform TC^{0}". Proc. 28th International Colloquium on Automata, Languages and Programming. Springer. pp. 104–114.
 Raz, Ran; McKenzie, Pierre (1999). "Separation of the monotone NC hierarchy". Combinatorica. 19 (3): 403–435. doi:10.1007/s004930050062.
 Razborov, Alexander A. (1985). "Lower bounds on the monotone complexity of some Boolean functions". Mathematics of the USSR, Doklady. 31: 354–357.
 Rossman, Benjamin (2008). "On the constantdepth complexity of kclique". STOC 2008: Proceedings of the 40th annual ACM symposium on Theory of computing. ACM. pp. 721–730. doi:10.1145/1374376.1374480.
 Shannon, Claude E. (1949). "The synthesis of twoterminal switching circuits". Bell System Technical Journal. 28 (1): 59–98. doi:10.1002/j.15387305.1949.tb03624.x.
 Smolensky, Roman (1987). "Algebraic methods in the theory of lower bounds for Boolean circuit complexity". Proc. 19th Annual ACM Symposium on Theory of Computing. ACM. pp. 77–82. doi:10.1145/28395.28404.
 Vollmer, Heribert (1999). Introduction to Circuit Complexity: a Uniform Approach. Springer Verlag. ISBN 9783540643104.
 Wegener, Ingo (1987). The Complexity of Boolean Functions. John Wiley and Sons Ltd, and B. G. Teubner, Stuttgart. ISBN 9783519021070. At the time an influential textbook on the subject, commonly known as the "Blue Book". Also available for download (PDF) at the Electronic Colloquium on Computational Complexity.
 Lecture notes for a course of Uri Zwick on circuit complexity
 Circuit Complexity before the Dawn of the New Millennium, a 1997 survey of the field by Eric Allender slides.