Content deleted Content added
replaced "size" in definition of "circuit-size complexity" with "number of gates" since "size" is ambiguous and according to Boolean_circuit the size complexity is the number of gates. Tag: Reverted |
Undid own revision, due to it not being an *useful* clarification (and some might argue not a clarification at all) |
||
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
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.
| |||