Content deleted Content added
m →Complexity classes: add unsourced section template |
|||
| (5 intermediate revisions by 5 users not shown) | |||
Line 1:
{{Short description|Model of computational complexity}}
{{Use dmy dates|date=May 2019|cs1-dates=y}}
[[File:Three input boolean circuit.svg|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).
Line 12:
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.<ref name="Sipser_1997"/> 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''' 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.
Line 27:
===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>
Line 107:
| 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 Elwood |author-link=Claude Elwood 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>
<ref name="Håstad_1987">{{cite book |author-first=Johan Torkel |author-last=Håstad |author-link=Johan Torkel 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}}</ref>
<ref name="Razborov_1985">{{cite journal |author-first=Aleksandr Aleksandrovich |author-last=Razborov |author-link=Aleksandr Aleksandrovich Razborov |title=Lower bounds on the monotone complexity of some Boolean functions |date=1985 |journal=[[Soviet Mathematics - Doklady]] |issn=0197-6788 |volume=31 |pages=354–357}}</ref>
| |||