Content deleted Content added
Citation bot (talk | contribs) Added isbn. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Circuit complexity | #UCB_Category 1/19 |
|||
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.
| |||