Content deleted Content added
added image |
MCT-890220 (talk | contribs) No edit summary |
||
Line 5:
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>NP\not\subseteq 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<sup>0</sup>]], [[AC (complexity)|AC]], [[TC0|TC<sup>0</sup>]] and [[NC (complexity)|NC]].▼
▲[[Complexity class]]es defined in terms of Boolean circuits include [[AC0|AC<sup>0</sup>]], [[AC (complexity)|AC]], [[TC0|TC<sup>0</sup>]],
== Size and Depth ==
Line 35 ⟶ 37:
Circuit complexity goes back to [[Claude Shannon|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 (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''.
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>.
Line 53 ⟶ 55:
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|last1=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}}</ref>
Razborov and Rudich showed that many known circuit lower bounds for explicit Boolean functions imply the existence of so called [[Natural proof|natural properties]] useful against the respective circuit class.<ref name="RazRu">{{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 for explicit Boolean functions. 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|}}</ref>
==Complexity classes==
| |||