Formal definition
A circuit is a triple , where * is a set of values, * is a set of gate labels, each of which is a function from to for some non-negative integer (where represents the number of inputs to the gate), and * is a labelledTerminology
The gates of in-degree 0 are called ''inputs'' or ''leaves''. The gates of out-degree 0 are called ''outputs''. If there is an edge from gate to gate in the graph then is called a ''child'' of . We suppose there is an order on the vertices of the graph, so we can speak of the th child of a gate when is less than the out-degree of the gate. The ''size'' of a circuit is the number of nodes of a circuit. The ''depth of a gate'' is the length of the longest path in beginning at up to an output gate. In particular, the gates of out-degree 0 are the only gates of depth 1. The ''depth of a circuit'' is the maximum depth of any gate. ''Level '' is the set of all gates of depth . A ''levelled circuit'' is a circuit in which the edges to gates of depth comes only from gates of depth or from the inputs. In other words, edges only exist between adjacent levels of the circuit. The ''width'' of a levelled circuit is the maximum size of any level.Evaluation
The exact value of a gate with in-degree and label is defined recursively for all gates . : where each is a parent of . The value of the circuit is the value of each of the output gates.Circuits as functions
The labels of the leaves can also be variables which take values in . If there are leaves, then the circuit can be seen as a function from to . It is then usual to consider a family of circuits , a sequence of circuits indexed by the integers where the circuit has variables. Families of circuits can thus be seen as functions from to . The notions of size, depth and width can be naturally extended to families of functions, becoming functions from to ; for example, is the size of the th circuit of the family.Complexity and algorithmic problems
Computing the output of a given Boolean circuit on a specific input is a P-complete problem. If the input is an integer circuit, however, it is unknown whether this problem is decidable. Circuit complexity attempts to classify Boolean functions with respect to the size or depth of circuits that can compute them.See also
* Arithmetic circuit complexity * Boolean circuit * Circuit complexity * Circuits over sets of natural numbers * TheReferences
* *{{cite journal, last= Yang , first= Ke, title= Integer Circuit Evaluation Is PSPACE-Complete, year = 2001, journal= Journal of Computer and System Sciences , volume =63 , issue =2, September 2001 , pages= 288–303 , issn= 0022-0000, doi= 10.1006/jcss.2001.1768, doi-access= free Theory of computation Circuit complexity