Circuit complexity: Difference between revisions

Revision as of 09:39, 22 June 2020

Latest revision as of 00:57, 18 May 2025

(40 intermediate revisions by 21 users not shown)

Line 1:

{{Short description|modelModel of computational complexity}}

{{Use dmy dates|date=May 2019|cs1-dates=y}}

[[File:Three_input_Boolean_circuitThree input boolean circuit.jpgsvg|thumb|right|300px|Example Boolean circuit. 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.]]

In [[theoretical computer science]], '''circuit complexity''' is a branch of [[computational complexity theory]] in which [[Boolean function]]s are classified according to the size or depth of the [[Boolean circuit]]s that compute them. A related notion is the circuit complexity of a [[recursive language]] that is [[Machine that always halts|decided]] by a '''uniform''' family of circuits <math>C_{1},C_{2},\ldots</math> (see below).

Proving lower bounds on size of Boolean circuits computing explicit Boolean functions is a popular approach to separating complexity classes. For example, a [[P/poly#Importance of P/poly|prominent]] circuit class [[P/poly]] consists of Boolean functions computable by circuits of polynomial- size. Proving that <math>\mathsf{NP}\not\subseteq \mathsf{P/poly}</math> would separate [[P (complexity)|P]] and [[NP (complexity)|NP]] (see below).

[[Complexity class]]es defined in terms of Boolean circuits include [[AC0|AC⁰]], [[AC (complexity)|AC]], [[TC0|TC⁰]], [[NC1 (complexity)|NC¹]], [[NC (complexity)|NC]], and [[P/poly]].

== Size and Depth depth==

A Boolean circuit with <math>n</math> 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 labelled by one of the <math>n</math> input bits, an [[AND gate]], an [[OR gate]], or a [[NOT gate]]. One of these gates is designated as the output gate. Such a circuit naturally computes a function of its <math>n</math> 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.

There are two major notions of circuit complexity (these are outlined in Sipser (1997).<ref name=Sipser>Sipser, M. (1997). 'Introduction to the theory of computation.' Boston: PWS Pub. Co.<"Sipser_1997"/ref>{{rp|324}}). The '''circuit-size complexity''' of a Boolean function <math>f</math> is the minimal size of any circuit computing <math>f</math>. The '''circuit-depth complexity''' of a Boolean function <math>f</math> is the minimal depth of any circuit computing <math>f</math>.

A Boolean circuit with <math>n</math> 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 labelled by one of the <math>n</math> input bits, an [[AND gate]], an [[OR gate]], or a [[NOT gate]]. One of these gates is designated as the output gate. Such a circuit naturally computes a function of its <math>n</math> 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.

These notions generalize when one considers the circuit complexity of any language that contains strings with different bit lengths, especially infinite [[formal language]]s. 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 <math>C_{1},C_{2},\ldots</math> where each <math>C_{n}</math> accepts inputs of size <math>n</math>. Each circuit family will naturally generate the language by circuit <math>C_{n}</math> outputting <math>1</math> when a length <math>n</math> string is a member of the family, and <math>0</math> otherwise. We say that a family of circuits is '''size minimal''' if there is no other family that decides on inputs of any size, <math>n</math>, with a circuit of smaller size than <math>C_n</math> (respectively for '''depth minimal''' families). Thus, circuit complexity is meaningful even for [[recursive language|non-recursive languages]]. The notion of a '''uniform family''' (see below) enables variants of circuit complexity to be related to algorithm based complexity measures of recursive languages. However, the non-uniform variant is helpful to find lower bounds on how complex any circuit family must be in order to decide given languages.

There are two major notions of circuit complexity (these are outlined in Sipser (1997)<ref name=Sipser>Sipser, M. (1997). 'Introduction to the theory of computation.' Boston: PWS Pub. Co.</ref>{{rp|324}}). The '''circuit-size complexity''' of a Boolean function <math>f</math> is the minimal size of any circuit computing <math>f</math>. The '''circuit-depth complexity''' of a Boolean function <math>f</math> is the minimal depth of any circuit computing <math>f</math>.

These notions generalize when one considers the circuit complexity of any language that contains strings with different bit lengths, especially infinite [[formal language]]s. 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 <math>C_{1},C_{2},\ldots</math> where each <math>C_{n}</math> accepts inputs of size <math>n</math>. Each circuit family will naturally generate the language by circuit <math>C_{n}</math> outputting <math>1</math> when a length <math>n</math> string is a member of the family, and <math>0</math> otherwise. We say that a family of circuits is '''size minimal''' if there is no other family that decides on inputs of any size, <math>n</math>, with a circuit of smaller size than <math>C_n</math> (respectively for '''depth minimal''' families). Thus circuit complexity is meaningful even for [[recursive language|non-recursive languages]]. The notion of a '''uniform family''' (see below) enables variants of circuit complexity to be related to algorithm based complexity measures of recursive languages. However, the non-uniform variant is helpful to find lower bounds on how complex any circuit family must be in order to decide given languages.

Hence, the '''circuit-size complexity''' of a formal language <math>A</math> is defined as the function <math>t:\mathbb{N}\to\mathbb{N}</math>, that relates a bit length of an input, <math>n</math>, to the circuit-size complexity of a minimal circuit <math>C_{n}</math> that decides whether inputs of that length are in <math>A</math>. The '''circuit-depth complexity''' is defined similarly.

==Uniformity==

Boolean circuits are one of the prime examples of so-called 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 Boolean circuits <math>C_1, C_2, \dots </math> where each <math>C_n</math> is the circuit handling inputs of ''n'' bits. A ''uniformity'' condition is often imposed on these families, requiring the existence of some possibly [[computational resource|resource-bounded]] Turing machine that, on input ''n'', produces a description of the individual circuit <math>C_n</math>. When this Turing machine has a running time polynomial in ''n'', the circuit family is said to be P-uniform. The stricter requirement of [[DLOGTIME]]-uniformity is of particular interest in the study of shallow-depth circuit-classes such as AC⁰ or TC⁰. When no resource bounds are specified, a language is recursive (i.e., decidable by a Turing machine) if and only if the language is decided by a uniform family of Boolean circuits.

Boolean circuits are one of the prime examples of so-called 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 Boolean circuits <math>C_1, C_2, \dots </math> where each <math>C_n</math> is the circuit handling inputs of ''n'' bits. A ''uniformity'' condition is often imposed on these families, requiring the existence of some possibly [[computational resource|resource-bounded]] Turing machine that, on input ''n'', produces a description of the individual circuit <math>C_n</math>. When this Turing machine has a running time polynomial in ''n'', the circuit family is said to be P-uniform. The stricter requirement of [[DLOGTIME]]-uniformity is of particular interest in the study of shallow-depth circuit-classes such as AC⁰ or TC⁰. When no resource bounds are specified, a language is recursive (i.e., decidable by a Turing machine) if and only if the language is decided by a uniform family of Boolean circuits.

===Polynomial-time uniform===

A family of Boolean circuits <math>\{C_n:n \in \mathbb{N}\}</math> is ''polynomial-time uniform'' if there exists a [[deterministic Turing machine]] ''M'', such that

* ''M'' runs in polynomial time

* For all <math>n \in \mathbb{N}</math>, ''M'' outputs a description of <math>C_n</math> on input <math>1^n</math>

===Logspace uniform===

A family of Boolean circuits <math>\{C_n:n \in \mathbb{N}\}</math> is ''[[Log-space reduction|logspace uniform]]'' if there exists a [[deterministic Turing machine]] ''M'', such that

* ''M'' runs in logarithmic work space (i.e. ''M'' is a [[log-space transducer]])

* For all <math>n \in \mathbb{N}</math>, ''M'' outputs a description of <math>C_n</math> on input <math>1^n</math>

==History==

Circuit complexity goes back to [[Claude Shannon|Shannon]] (in 1949),<ref name="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 onlyso far been ableunable to prove [[Timea complexity#Superpolynomial time|superpolynomial]] circuitsuperlinear lower bounds on functions explicitly constructedbound for theany purpose of being hard toexplicit calculatefunction.

More commonly, superpolynomialSuperpolynomial 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 [[AC0|AC⁰]] was first established independently by Ajtai (in 1983)<ref name="Ajtai_1983"/>{{cite book |<ref last1name="Ajtai | first1=Miklós | last2=-Komlós | first2=János | last3=Szemerédi | first3=Endre | title=An 0(n log n) sorting network | journal=STOC '83 Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing | pages=1–9 | year=1983 | isbn=978-0-89791-099-6 }}<Szemerédi_1983"/ref> and by Furst, Saxe and Sipser (in 1984).<ref>{{cite journal | last1 name= "Furst | first1 = Merrick | last2 = Saxe | first2 = James B. | author2-link = James B. Saxe | last3 = Sipser | first3 = Michael | author3-link = Michael Sipser | doi = 10.1007Sipser_1984"/BF01744431 | issue = 1 | journal = Mathematical Systems Theory | mr = 738749 | pages = 13–27 | title = Parity, circuits, and the polynomial-time hierarchy | volume = 17 | year = 1984}}</ref> Later improvements by [[Johan Håstad|Håstad]] (in 1987)<ref inname="Håstad_1987"/> fact establishestablished that any family of constant-depth circuits computing the parity function requires exponential size. Extending a result of Razborov,<ref name="Razborov_1985"/> Smolensky (in 1987)<ref name="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''.

Circuit complexity goes back to [[Claude Shannon|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 [[Time complexity#Superpolynomial time|superpolynomial]] circuit lower bounds on functions explicitly constructed for the purpose of being hard to calculate.

The [[clique problem|''k''-clique 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 <math>{n \choose 2}</math> bits, which indicate for each possible edge whether it is present. Then the ''k''-clique problem is formalized as a function <math>f_k:\{0,1\}^{{n \choose 2}}\to\{0,1\}</math> such that <math>f_k</math> outputs 1 if and only if the graph encoded by the string contains a clique of size ''k''. 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 without negation). The original result of [[Alexander Razborov|Razborov]] (in 1985)<ref name="Razborov_1985"/> was later improved to an exponential-size lower bound by Alon and Boppana (in 1987).<ref Rossmanname="Alon-Boppana_1987"/> In (2008), Rossman<ref name="Rossman_2008"/> showsshowed that constant-depth circuits with AND, OR, and NOT gates require size <math>\Omega(n^{k/4})</math> to solve the ''k''-clique problem even in the [[average-case complexity|average case]]. Moreover, there is a circuit of size <math>n^{k/4+O(1)}</math> that computes <math>f_k</math>.

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 [[AC0|AC⁰]] was first established independently by Ajtai (1983)<ref>{{cite book | last1=Ajtai | first1=Miklós | last2=Komlós | first2=János | last3=Szemerédi | first3=Endre | title=An 0(n log n) sorting network | journal=STOC '83 Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing | pages=1–9 | year=1983 | isbn=978-0-89791-099-6 }}</ref> and by Furst, Saxe and Sipser (1984).<ref>{{cite journal | last1 = Furst | first1 = Merrick | last2 = Saxe | first2 = James B. | author2-link = James B. Saxe | last3 = Sipser | first3 = Michael | author3-link = Michael Sipser | doi = 10.1007/BF01744431 | issue = 1 | journal = Mathematical Systems Theory | mr = 738749 | pages = 13–27 | title = Parity, circuits, and the polynomial-time hierarchy | volume = 17 | year = 1984}}</ref> Later improvements by [[Johan Håstad|Håstad]] (1987) in fact establish that any family of constant-depth 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''.

In 1999, [[Ran Raz|Raz]] and [[Pierre McKenzie|McKenzie]] later showed that the monotone NC hierarchy is infinite (1999).<ref name="Raz-McKenzie_1999"/>

The [[clique problem|''k''-clique 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 <math>{n \choose 2}</math> bits, which indicate for each possible edge whether it is present. Then the ''k''-clique problem is formalized as a function <math>f_k:\{0,1\}^{{n \choose 2}}\to\{0,1\}</math> such that <math>f_k</math> outputs 1 if and only if the graph encoded by the string contains a clique of size ''k''. 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 without negation). The original result of [[Alexander Razborov|Razborov]] (1985) was later improved to an exponential-size lower bound by Alon and Boppana (1987). Rossman (2008) shows that constant-depth circuits with AND, OR, and NOT gates require size <math>\Omega(n^{k/4})</math> to solve the ''k''-clique problem even in the [[average-case complexity|average case]]. Moreover, there is a circuit of size <math>n^{k/4+O(1)}</math> that computes <math>f_k</math>.

The Integer Division Problem lies in uniform [[TC0|TC⁰]].<ref (Hesse 2001).name="Hesse_2001"/>

[[Ran Raz|Raz]] and [[Pierre McKenzie|McKenzie]] later showed that the monotone NC hierarchy is infinite (1999).

The Integer Division Problem lies in uniform [[TC0|TC⁰]] (Hesse 2001).

==Circuit lower bounds==

Circuit lower bounds are generally difficult. Known results include

* Parity is not in nonuniform [[AC0|AC⁰]], proved by Ajtai (in 1983)<ref andname="Ajtai_1983"/><ref name="Ajtai-Komlós-Szemerédi_1983"/> as well as by Furst, Saxe and Sipser in 1984.<ref name="Furst-Saxe-Sipser_1984"/>

* Uniform [[TC0|TC⁰]] is strictly contained in [[PP (complexity)|PP]], proved by Allender.<ref name="Allender_1997"/>

* The classes [[S2P (complexity)|S{{su|p=P|b=2}}]], PP<ref>See [[Karp-Liptongroup="nb" theorem#Application for circuit lower bounds - Kannan's theorem|proof]]<name="NB1"/ref> and [[MA (complexity)|MA]]/1<ref>{{cite conference|last=Santhanam|first=Rahul|urlname=http:"Santhanam_2007"//citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.111.1811|title=Circuit lower bounds for Merlin-Arthur classes|booktitle=STOC 2007: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing|year=2007|pages=275–283|doi=10.1145/1250790.1250832|citeseerx=10.1.1.92.4422}}</ref> (MA with one bit of advice) are not in '''SIZE'''(''n^k'') for any constant k.

* While it is suspected that the nonuniform class [[ACC0|ACC⁰]] does not contain the majority function, it was only in 2010 that [[Ryan Williams (computer scientist)|Williams]] proved that {{nowrap|<math>\mathsf{NEXP} \not \subseteq \mathsf{ACC}^0</math>.<ref>{{cite conference|lastname=Williams|first=Ryan|title=Non-Uniform ACC Circuit Lower Bounds|url=http://www.stanford.edu/~rrwill/acc-lbs.pdf|doi=10.1109/CCC.2011.36|year=2011|booktitle=CCC 2011: Proceedings of the 26th Annual IEEE Conference on Computational Complexity|pages=115–125}}<"Williams_2011"/ref>}}

It is open whether NEXPTIME has nonuniform TC⁰ circuits.

Proofs of circuit lower bounds are strongly connected to [[derandomization]]. A proof that <math>\mathsf{P} = \mathsf{BPP}</math> would imply that either <math>\mathsf{NEXP} \not \subseteq \mathsf{P/poly}</math> or that permanent cannot be computed by nonuniform arithmetic circuits (polynomials) of polynomial size and polynomial degree.<ref>{{cite journal|last1name="Kabanets|first1=V.|last2=Impagliazzo|first2=R.|journal=Computational Complexity|doi=10.1007/s00037-004-0182-6|title=Derandomizing polynomial identity tests means proving circuit lower bounds|pages=1–46|volume=13|number=1|year=2004}}<Impagliazzo_2004"/ref>

In 1997, Razborov and Rudich (1997) showed that many known circuit lower bounds for explicit Boolean functions imply the existence of so called [[Naturalnatural proof|natural properties]] useful against the respective circuit class.<ref name="RazRuRazborov-Rudich_1997">{{cite news|first1=Alexander|last1=Razborov|first2=Stephen|last2=Rudich|title=Natural proofs|journal=Journal of Computer and System Sciences|volume=55|pages=24–35|year=1997}}</ref> 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. In 2016, Carmosino, Impagliazzo, Kabanets and Kolokolova (2016) proved that natural properties can be also used to construct efficient learning algorithms.<ref name="CIKK">{{cite news|first1=Marco|last1=Carmosino|first2=Russell|last2=-Impagliazzo|first3=Valentine|last3=-Kabanets|first4=Antonina|last4=Kolokolova|title=Learning algorithms from natural proofs|journal=Computational Complexity Conference|year=2016}}<-Kolokolova_2016"/ref>

==Complexity classes==

{{Unreferenced section|date=October 2024}}

Many circuit complexity classes are defined in terms of class hierarchies. For each nonnegativenon-negative integer ''i'', there is a class [[NC (complexity)|NCⁱ]], consisting of polynomial-size circuits of depth <math>O(\log^i(n))</math>, using bounded [[fan-in]] AND, OR, and NOT gates. We can talk about theThe union NC of all of these classes. is a subject to discussion. By considering unbounded fan-in gates, we construct the classes [[AC (complexity)|ACⁱ]] and AC (which is equal to NC). can Webe may constructconstructed. manyMany other circuit complexity classes with the same size and depth restrictions can be constructed by allowing different sets of gates.

==Relation to time complexity==

Say thatIf a certain language, <math>A</math>, belongs to the [[Complexity class|time-complexity class]] <math>\text{TIME}(t(n))</math> for some function <math>t:\mathbb{N}\to\mathbb{N}</math>., Thenthen <math>A</math> has circuit complexity <math>\mathcal{O}(t^(n) \log t(n))</math>. If the Turing Machine that accepts the language is [[Turing machine equivalents|oblivious]] (meaning that it reads and writes the same memory cells regardless of input), then <math>A</math> has circuit complexity <math>\mathcal{2O}(t(n))</math>.<ref>{{cite namejournal|first1=SipserNicholas|last1=Pippenger|authorlink=Nick Pippenger|first2=Michael J.|last2=Fischer|authorlink2=Michael J. Fischer|title=Relations Among Complexity Measures|journal=[[Journal of the ACM]]|year=1979|volume=26|issue=3|pages=361–381|doi=10.1145/>322123.322138|s2cid=2432526 |doi-access=free}}

</ref>

==Monotone circuits==

A monotone Boolean circuit is one that has only AND and OR gates, but no NOT gates. A monotone circuit can only compute a monotone Boolean function, which is a function <math>f:\{0,1\}^n \to \{0,1\}</math> where for every <math>x,y \in \{0,1\}^n</math>, <math>x \leq y \implies f(x) \leq f(y)</math>, where <math>x\leq y</math> means that <math>x_i \leq y_i</math> for all <math>i \in \{1,\ldots,n\}</math>.

==See also==

* [[Circuit minimization]]

==Notes==

{{reflist}}|group="nb"|refs=

<ref group="nb" name="NB1">See [[Karp-Lipton theorem#Application for circuit lower bounds - Kannan's theorem|proof]].</ref>

}}

==References==

{{reflist|refs=

*{{cite journal|first=Miklós|last=Ajtai|authorlink=Miklós Ajtai|title=<math>\Sigma^1_1</math>-formulae on finite structures|journal=Annals of Pure and Applied Logic|year=1983|volume=24|pages=1–24|doi=10.1016/0168-0072(83)90038-6}}

<ref name="Sipser_1997">{{cite book |author-last=Sipser |author-first=Michael |author-link=Michael Sipser |date=1997 |title=Introduction to the theory of computation |publication-place=Boston, USA |edition=1 |isbn= |publisher=PWS Publishing Company |page=324}}</ref>

*{{cite journal|first1=Noga|last1=Alon|first2=Ravi B.|last2=Boppana|title=The monotone circuit complexity of Boolean functions|journal=Combinatorica|volume=7|year=1987|number=1|pages=1–22|doi=10.1007/bf02579196|citeseerx=10.1.1.300.9623}}

<ref name="Ajtai-Komlós-Szemerédi_1983">{{cite book

*{{cite journal|first1=Merrick L.|last1=Furst|first2=James B.|last2=Saxe|first3=Michael|last3=Sipser|title=Parity, circuits, and the polynomial-time hierarchy|journal=Mathematical Systems Theory|volume=17|number=1|pages=13–27|year=1984|doi=10.1007/bf01744431}}

| last1 = Ajtai | first1 = Miklós | author1-link = Miklós Ajtai

*{{citation|first=Johan|last=Håstad|title=Computational limitations of small depth circuits|year=1987|publisher=Ph.D. thesis, Massachusetts Institute of Technology|url=http://www.nada.kth.se/~johanh/thesis.pdf|postscript=.}}

| last2 = Komlós | first2 = János | author2-link = János Komlós (mathematician)

*{{cite conference|first=William|last=Hesse|title=Division is in uniform TC⁰|year=2001|pages=104–114|booktitle=Proc. 28th International Colloquium on Automata, Languages and Programming|publisher=Springer}}

| last3 = Szemerédi | first3 = Endre | author3-link = Endre Szemerédi

*{{cite journal|first1=Ran|last1=Raz|first2=Pierre|last2=McKenzie|title=Separation of the monotone NC hierarchy|journal=Combinatorica|volume=19|number=3|year=1999|pages=403–435|doi=10.1007/s004930050062}}

| contribution = An <math>O(n\log n)</math> sorting network

*{{cite journal|first=Alexander A.|last=Razborov|authorlink=Alexander Razborov|title=Lower bounds on the monotone complexity of some Boolean functions|year=1985|journal=Mathematics of the USSR, Doklady|volume=31|pages=354–357}}

| doi = 10.1145/800061.808726

*{{cite conference|first=Benjamin|last=Rossman|title=On the constant-depth complexity of k-clique|year=2008|pages=721–730|booktitle=STOC 2008: Proceedings of the 40th annual ACM symposium on Theory of computing|publisher=ACM|doi=10.1145/1374376.1374480}}

| pages = 1–9

*{{cite journal|last=Shannon|first=Claude E.|authorlink=Claude Shannon|title=The synthesis of two-terminal switching circuits|journal=Bell System Technical Journal|year=1949|volume=28|number=1|pages=59–98|doi=10.1002/j.1538-7305.1949.tb03624.x}}

| publisher = Association for Computing Machinery

*{{cite conference|first=Roman|last=Smolensky|title = Algebraic methods in the theory of lower bounds for Boolean circuit complexity|year=1987|pages=77–82|booktitle=Proc. 19th Annual ACM Symposium on Theory of Computing|publisher=ACM|doi=10.1145/28395.28404}}

| title = Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25–27 April, 1983, Boston, Massachusetts, USA

*{{cite book|title=Introduction to Circuit Complexity: a Uniform Approach|last=Vollmer|first=Heribert|publisher=[[Springer Verlag]]|year=1999|isbn=978-3-540-64310-4}}

| year = 1983}}</ref>

*{{cite book

*<ref name="Ajtai_1983">{{cite journal |author-first=Miklós |author-last=Ajtai |authorlinkauthor-link=Miklós Ajtai |title=<math>\Sigma^1_1</math>-formulae on finite structures |journal=Annals of Pure and Applied Logic |yeardate=1983 |volume=24 |pages=1–24 |doi=10.1016/0168-0072(83)90038-6|doi-access= }}</ref>

|last = Wegener

<ref name="Furst-Saxe-Sipser_1984">{{cite journal |author-last1=Furst |author-first1=Merrick L. |author-last2=Saxe |author-first2=James Benjamin |author-link2=James Benjamin Saxe |author-last3=Sipser |author-first3=Michael Fredric |author-link3=Michael Fredric Sipser |doi=10.1007/BF01744431 |issue=1 |journal=[[Mathematical Systems Theory]] |mr=738749 |pages=13–27 |title=Parity, circuits, and the polynomial-time hierarchy |volume=17 |date=1984|s2cid=6306235 }}</ref>

|first = Ingo

<ref name="Santhanam_2007">{{cite conference |author-last=Santhanam |author-first=Rahul |url=http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.111.1811 |title=Circuit lower bounds for Merlin-Arthur classes |book-title=STOC 2007: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing |date=2007 |pages=275–283 |doi=10.1145/1250790.1250832 |citeseerx=10.1.1.92.4422}}</ref>

|authorlink = Ingo Wegener

<ref name="Williams_2011">{{cite conference |author-last=Williams |author-first=Richard Ryan |author-link=Richard Ryan Williams |title=Non-Uniform ACC Circuit Lower Bounds |url=http://www.stanford.edu/~rrwill/acc-lbs.pdf |doi=10.1109/CCC.2011.36 |date=2011 |book-title=CCC 2011: Proceedings of the 26th Annual IEEE Conference on Computational Complexity |pages=115–125}}</ref>

|title = The Complexity of Boolean Functions

<ref name="Kabanets-Impagliazzo_2004">{{cite journal |author-last1=Kabanets |author-first1=Valentine |author-last2=Impagliazzo |author-first2=Russell Graham |author-link3=Russell Graham Impagliazzo |journal=Computational Complexity |doi=10.1007/s00037-004-0182-6 |title=Derandomizing polynomial identity tests means proving circuit lower bounds |pages=1–46 |volume=13 |number=1 |date=2004|s2cid=12451799 }}</ref>

|publisher = John Wiley and Sons Ltd, and B. G. Teubner, Stuttgart

<ref name="Razborov-Rudich_1997">{{cite news |author-first1=Aleksandr Aleksandrovich |author-last1=Razborov |author-link1=Aleksandr Aleksandrovich Razborov |author-first2=Steven |author-last2=Rudich |author-link2=Steven Rudich |title=Natural proofs |journal=[[Journal of Computer and System Sciences]] |volume=55 |pages=24–35 |date=1997}}</ref>

|year = 1987

<ref name="Carmosino-Impagliazzo-Kabanets-Kolokolova_2016">{{cite news |author-first1=Marco |author-last1=Carmosino |author-first2=Russell Graham |author-last2=Impagliazzo |author-link2=Russell Graham Impagliazzo |author-first3=Valentine |author-last3=Kabanets |author-first4=Antonina |author-last4=Kolokolova |title=Learning algorithms from natural proofs |journal=Computational Complexity Conference |date=2016}}</ref>

|isbn = 978-3-519-02107-0}} At the time an influential textbook on the subject, commonly known as the "Blue Book". Also available for [http://eccc.hpi-web.de/static/books/The_Complexity_of_Boolean_Functions/ download (PDF)] at the [[Electronic Colloquium on Computational Complexity]].

*<ref name="Hesse_2001">{{cite conference |author-first=William |author-last=Hesse |title=Division is in uniform TC⁰ |yeardate=2001 |pages=104–114 |booktitlebook-title=Proc.Proceedings of the 28th International Colloquium on Automata, Languages and Programming |publisher=[[Springer Verlag]]}}</ref>

*[http://www.cs.tau.ac.il/~zwick/scribe-boolean.html Lecture notes for a course of Uri Zwick on circuit complexity]

*<ref name="Raz-McKenzie_1999">{{cite journal |author-first1=Ran |author-last1=Raz |author-link1=Ran Raz |author-first2=Pierre |author-last2=McKenzie |title=Separation of the monotone NC hierarchy |journal=[[Combinatorica]] |volume=19 |number=3 |yeardate=1999 |pages=403–435 |doi=10.1007/s004930050062}}</ref>

*[http://ftp.cs.rutgers.edu/pub/allender/fsttcs.pdf ''Circuit Complexity before the Dawn of the New Millennium''], a 1997 survey of the field by Eric Allender [http://ftp.cs.rutgers.edu/pub/allender/fsttcs.96.slides.ps slides].

<ref name="Allender_1997">{{cite book

| last = Allender | first = Eric | author-link = Eric Allender

| editor1-last = Chandru | editor1-first = Vijay

| editor2-last = Vinay | editor2-first = V.

| contribution = Circuit complexity before the dawn of the new millennium

| doi = 10.1007/3-540-62034-6_33

| pages = 1–18

| publisher = Springer

| series = Lecture Notes in Computer Science

| title = Foundations of Software Technology and Theoretical Computer Science, 16th Conference, Hyderabad, India, December 18–20, 1996, Proceedings

| volume = 1180

* | year = 1996| isbn = 978-3-540-62034-1 }}</ref><ref name="Shannon_1949">{{cite journal |author-last=Shannon |author-first=Claude E.Elwood |authorlinkauthor-link=Claude Elwood Shannon |title=The synthesis of two-terminal switching circuits |journal=[[Bell System Technical Journal]] |yeardate=1949 |volume=28| number=1 |pages=59–98 |doi=10.1002/j.1538-7305.1949.tb03624.x}}</ref>

*<ref name="Håstad_1987">{{citationcite book |author-first=Johan Torkel |author-last=Håstad |author-link=Johan Torkel Håstad |title=Computational limitations of small depth circuits |yeardate=1987 |publishertype=Ph.D. thesis, |publisher=Massachusetts Institute of Technology |url=http://www.nada.kth.se/~johanh/thesis.pdf|postscript=.}}</ref>

*<ref name="Razborov_1985">{{cite journal |author-first=AlexanderAleksandr Aleksandrovich A.|author-last=Razborov |authorlinkauthor-link=AlexanderAleksandr Aleksandrovich Razborov |title=Lower bounds on the monotone complexity of some Boolean functions |yeardate=1985 |journal=[[Soviet Mathematics of- theDoklady]] USSR,|issn=0197-6788 Doklady|volume=31 |pages=354–357}}</ref>

*<ref name="Rossman_2008">{{cite conference |author-first=Benjamin E. |author-last=Rossman |author-link=Benjamin E. Rossman |title=On the constant-depth complexity of k-clique |yeardate=2008 |pages=721–730 |booktitlebook-title=STOC 2008: Proceedings of the 40th annual ACM symposium on Theory of computing |publisher=ACM[[Association for Computing Machinery]] |doi=10.1145/1374376.1374480}}</ref>

*<ref name="Smolensky_1987">{{cite conference |author-first=Roman |author-last=Smolensky |title = Algebraic methods in the theory of lower bounds for Boolean circuit complexity |yeardate=1987 |pages=77–82 |booktitlebook-title=Proc.Proceedings of the 19th Annual ACM Symposium on Theory of Computing |publisher=ACM[[Association for Computing Machinery]] |doi=10.1145/28395.28404|doi-access=free }}</ref>

*<ref name="Alon-Boppana_1987">{{cite journal |author-first1=Noga |author-last1=Alon |author-link1=Noga Alon |author-first2=Ravi B. |author-last2=Boppana |title=The monotone circuit complexity of Boolean functions |journal=[[Combinatorica]] |volume=7 |yeardate=1987 |number=1 |pages=1–22 |doi=10.1007/bf02579196 |citeseerx=10.1.1.300.9623|s2cid=17397273 }}</ref>

}}

==Further reading==

* {{cite book |title=Introduction to Circuit Complexity: a Uniform Approach |author-last=Vollmer |author-first=Heribert |author-link=:de:Heribert Vollmer |publisher=[[Springer Verlag]] |yearseries=Texts in Theoretical Computer Science. An EATCS Series |date=1999 |isbn=978-3-540-64310-4}}

* {{cite book |isbnauthor-last=Wegener |author-first=Ingo 978|author-link=Ingo Wegener |title=The Complexity of Boolean Functions |series=Wiley–Teubner Series in Computer Sciences |publisher=[[John Wiley & Sons Ltd.]], and [[B. G. Teubner Verlag]], Stuttgart |date=1987 |orig-date=November 1986 |___location=Frankfurt am Main/Bielefeld, Germany |isbn=3-519-02107-02<!-- Teubner --> |lccn=87-10388}} (xii+457 pages) (NB. At the time an influential textbook on the subject, commonly known as the "Blue Book". Also available for [http://eccc.hpi-web.de/static/books/The_Complexity_of_Boolean_Functions/ download (PDF)] at the [[Electronic Colloquium on Computational Complexity]]. )

* {{cite web |title=Lecture notes for a course of Uri Zwick on circuit complexity |author-first=Uri |author-last=Zwick |author-link=Uri Zwick |url=http://www.cs.tau.ac.il/~zwick/scribe-boolean.html}}

[[Category:Circuit complexity| ]]