Circuit complexity: Difference between revisions

Revision as of 17:41, 21 June 2020

Revision as of 09:39, 22 June 2020

Line 15:

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|formal languages]]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.

Line 56:

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 (1997) 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-3524–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. 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==

Line 91:

*[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].

[[Category:Computational complexity theory]]

[[Category:Circuit complexity| ]]

[[Category:Computational complexity theory]]