Circuit (computer science). In theoretical computer science, a circuit is a model of computation in which input values proceed through a sequence of gates, each of which computes a function. Circuits of this kind provide a generalization of Boolean circuits and a mathematical model for digital logic circuits. Circuits are defined by the gates they contain and the values the gates can produce.  For example, the values in a Boolean circuit are Boolean values, and the circuit includes conjunction, disjunction, and negation gates.  The values in an integer circuit are sets of integers and the gates compute set union, set intersection, and set complement, as well as the arithmetic operations addition and multiplication.

Formal definition 
A circuit is a triplet , 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 labelled directed acyclic graph with labels from .

The vertices of the graph are called gates. For each gate  of in-degree , the gate  can be labeled by an element  of  if and only if  is defined on

Terminology 
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 or equal to 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
 The complexity classes NC, AC and TC
 Quantum circuit and BQP

References

Theory of computation
Circuit complexity