In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of Boolean circuits that compute them. One speaks of the circuit complexity of a Boolean circuit. A related notion is the circuit complexity of a recursive language that is decided by a family of circuits (see below).
A Boolean circuit with input bits is a directed acyclic graph in which every node (usually called gates in this context) is either an input node of in-degree 0 labeled by one of the input bits, an AND gate, an OR or a NOT gate. One of these gates is designated as the output gate. Such a circuit naturally computes a function of its 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 (these are outlined in Sipser (1997)). The circuit-size complexity of a Boolean function is the minimal size of any circuit computing . The circuit-depth complexity of a Boolean function is the minimal depth of any circuit computing .
These notions generalize when one considers the circuit complexity of a recursive language: A formal language may contain strings with many different bit lengths. 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 where each accepts inputs of size . Each circuit family will naturally generate a recursive language by outputting when a string is a member of the family, and otherwise. We say that a family of circuits is size minimal if there is no other family that decides on inputs of any size, with a circuit of smaller size than (respectively for depth minimal families).
Hence, the circuit-size complexity of a recursive language is defined as the function, that relates a bit length of an input, to the circuit-size complexity of the minimal circuit that decides whether inputs of that length are in . The circuit-depth complexity is defined similarly.
Complexity classes defined in terms of Boolean circuits include AC0, AC, TC0 and NC.
Read more about Circuit Complexity: Uniformity, History, Circuit Lower Bounds, Complexity Classes, Relation To Time Complexity
Famous quotes containing the words circuit and/or complexity:
“each new victim treads unfalteringly
The never altered circuit of his fate,
Bringing twelve peers as witness
Both to his starry rise and starry fall.”
—Robert Graves (1895–1985)
“In times like ours, where the growing complexity of life leaves us barely the time to read the newspapers, where the map of Europe has endured profound rearrangements and is perhaps on the brink of enduring yet others, where so many threatening and new problems appear everywhere, you will admit it may be demanded of a writer that he be more than a fine wit who makes us forget in idle and byzantine discussions on the merits of pure form ...”
—Marcel Proust (1871–1922)