Circuit (computer science)

A circuit in computer theory is a theoritical structure simulating real circuit, where input values enter in one part of the circuit, go through gates which does some computation and output an answer. An important special case of circuits are the boolean circuit.

Circuits are defined in terms of the gates they contain and the values the gates can take. For example, binary circuit's value are boolean values, and the gates are binary AND and OR gates and unary NOT gates, or be entirely described by binary NAND gates. In integer circuit the values are set of integers and the gates are set unions, intersection, complement, and the arithmetic operations + and $\times$

Formal definition

A circuit is composed of a set of values $M$, a set of gates's label $L$ which are (families) of function from $M^{i}$ to $M$, where $i$ is a non negative integers (when $i=0$ it is a constant gate), and a labelled directed acyclic graph the labels of which are elements of $G$, a gate $g$ can label a node $n$ of in-degree $i$ if and only if $g$ is definded on $M^{i}$.

Notions

The nodes of in-degree 0 are called the input node, or the leaves. If there is an edge from $g$ to $g'$ then $g'$ is called a son of $g$, we suppose there is an order on the vertices, so we can speak of the $k$th son of a vertex when $k$ is less than the in-degree of this vertex.

The size of a circuit is the number of node of a circuit.

The depth of a node $n$ is a size of the longest path begining in $n$, in particular, the gates of out-degree 0 are the only gates of depth 1. The depth of the circuit is the size of the longest path in the circuit. The level $i$ is the set of gates of depth $i$.

A leveled circuit is a circuit where the edges to nodes of depth $i$ comes only from nodes of depth $i+1$ or from input nodes. Another way to see it is that there are edges only between adjacent levels.

The width of a labelled circuit is the size of the biggest level.

Evaluation

The value of a node is defined recursively on the depth of the nodes, the gate $g$ of in-degree $i$ and label $l$ is $l(v_{1},\dots ,v_{i})$ where $v_{k}$ is the value of the $k$th son of $g$.

There is one node of out-degree 0 which will be called the output node, the value of the circuit is the value of the output node.

Circuit as fonctions

The labels of the leaves can also be variables which take values in $M$, if there are $n$ variables, then the circuit can be seen as a function from $M^{n}$ to $M$. Then it is usual to consider a family of circuit $(C_{n})_{n\in \mathbb {N} }$, a sequence of circuit indexed by the integers where the circuit $C_{n}$ has got $n$ variables. Families of circuit can thus be seen as functions from $M^{*}$ to $M$.

The notions of size, depth and widh can be naturaly extended to family of function, they become function from $\mathbb {N}$ to $\mathbb {N}$, for example size($n$) is the size of the $n$th circuit of the family.

It is possible to add restriction

Complexity and algorithmic problems

Circuit are often used in computational complexity and algorithm theory, there is two differents question:

Given a circuit, what is the complexity of computing the value of his output. By example over boolean circuit this question is P complete and over integer circuit it is not known to be decidable.

Given a language, what is the minimal size (resp depth) function which recognize the language. Usually some restrictions are added to the form of the circuit. Over boolean circuit this create formalism like NC.

References

• Vollmer, Heribert (1999). Introduction to Circuit Complexity. Berlin: Springer. ISBN 3-540-64310-9.