Content deleted Content added
Matthiaspaul (talk | contribs) CE, improved refs |
Matthiaspaul (talk | contribs) improved refs |
||
Line 9:
[[Complexity class]]es defined in terms of Boolean circuits include [[AC0|AC<sup>0</sup>]], [[AC (complexity)|AC]], [[TC0|TC<sup>0</sup>]], [[NC1 (complexity)|NC<sup>1</sup>]], [[NC (complexity)|NC]], and [[P/poly]].
==
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.
Line 34:
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<sup>''n''</sup>/''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.
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<sup>0</sup>]] was first established independently by Ajtai in 1983<ref name="Ajtai_1983"/><ref name="Ajtai-Komlós-Szemerédi_1983"/> and by Furst, Saxe and Sipser in 1984.<ref name="Furst-Saxe-Sipser_1984"/> Later improvements by [[Johan Håstad|Håstad]] in 1987<ref name=Håstad_1987""/> established 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''.
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 name="Alon-Boppana_1987"/> In 2008, Rossman<ref name="Rossman_2008"/> showed 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>.
In 1999, [[Ran Raz|Raz]] and [[Pierre McKenzie|McKenzie]] later showed that the monotone NC hierarchy is infinite.<ref name="Raz-McKenzie_1999"/>
Line 44:
==Circuit lower bounds==
Circuit lower bounds are generally difficult. Known results include
* Parity is not in nonuniform [[AC0|AC<sup>0</sup>]], proved by Ajtai in 1983<ref name="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<sup>0</sup>]] 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 group="nb" name="NB1"/> and [[MA (complexity)|MA]]/1<ref name="Santhanam_2007"/> (MA with one bit of advice) are not in '''SIZE'''(n<sup>k</sup>) for any constant k.
Line 73:
<ref name="Sipser_1997">{{cite book |author-last3=Sipser |author-first3=Michael |author-link3=Michael Sipser |date=1997 |title=Introduction to the theory of computation |publication-place=Boston, USA |publisher=PWS Pub. Co. |page=324}}</ref>
<ref name="Ajtai-Komlós-Szemerédi_1983">{{cite book |author-last1=Ajtai |author-first1=Miklós |author-last2=Komlós |author-first2=János |author-last3=Szemerédi |author-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 |date=1983 |isbn=978-0-89791-099-6}}</ref>
<ref name="
<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>
<ref name="Williams_2011">{{cite conference |author-last=Williams |author-first=Ryan |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>
Line 83 ⟶ 84:
<ref name="Allender_1997">{{cite web |url=http://ftp.cs.rutgers.edu/pub/allender/fsttcs.pdf |title=Circuit Complexity before the Dawn of the New Millennium |date=1997 |editor-first=Eric |editor-last=Allender}} [http://ftp.cs.rutgers.edu/pub/allender/fsttcs.96.slides.ps] (NB. A 1997 survey of the field by Eric Allender.)</ref>
<ref name="Shannon_1949">{{cite journal |author-last=Shannon |author-first=Claude E. |author-link=Claude Shannon |title=The synthesis of two-terminal switching circuits |journal=Bell System Technical Journal |date=1949 |volume=28| number=1 |pages=59–98 |doi=10.1002/j.1538-7305.1949.tb03624.x}}</ref>
}}
==Further reading==
▲* {{cite journal |author-first1=Noga |author-last1=Alon |author-first2=Ravi B. |author-last2=Boppana |title=The monotone circuit complexity of Boolean functions |journal=Combinatorica |volume=7 |date=1987 |number=1 |pages=1–22 |doi=10.1007/bf02579196 |citeseerx=10.1.1.300.9623}}
▲* {{cite journal |author-first1=Merrick L. |author-last1=Furst |author-first2=James B. |author-last2=Saxe |author-first3=Michael |author-last3=Sipser |title=Parity, circuits, and the polynomial-time hierarchy |journal=Mathematical Systems Theory |volume=17 |number=1 |pages=13–27 |date=1984 |doi=10.1007/bf01744431}}
▲* {{cite book |author-first=Johan |author-last=Håstad |title=Computational limitations of small depth circuits |date=1987 |type=Ph.D. thesis |publisher=Massachusetts Institute of Technology |url=http://www.nada.kth.se/~johanh/thesis.pdf}}
▲* {{cite journal |author-first=Alexander A. |author-last=Razborov |author-link=Alexander Razborov |title=Lower bounds on the monotone complexity of some Boolean functions |date=1985 |journal=Mathematics of the USSR, Doklady |volume=31 |pages=354–357}}
▲* {{cite conference |author-first=Benjamin |author-last=Rossman |title=On the constant-depth complexity of k-clique |date=2008 |pages=721–730 |book-title=STOC 2008: Proceedings of the 40th annual ACM symposium on Theory of computing |publisher=ACM |doi=10.1145/1374376.1374480}}
▲* {{cite conference |author-first=Roman |author-last=Smolensky |title=Algebraic methods in the theory of lower bounds for Boolean circuit complexity |date=1987 |pages=77–82 |book-title=Proc. 19th Annual ACM Symposium on Theory of Computing |publisher=ACM |doi=10.1145/28395.28404}}
* {{cite book |title=Introduction to Circuit Complexity: a Uniform Approach |author-last=Vollmer |author-first=Heribert |publisher=[[Springer Verlag]] |date=1999 |isbn=978-3-540-64310-4}}
* {{cite book |author-last=Wegener |author-first=Ingo |author-link=Ingo Wegener |title=The Complexity of Boolean Functions |publisher=John Wiley and Sons Ltd, and B. G. Teubner, Stuttgart |date=1987 |isbn=978-3-519-02107-0}} (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]].)
| |||