Circuit (computer science)

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

Circuits are defined in terms of the gates they contain and the values the gates can take. For example, binary circuits' values are boolean values, and the gates can be binary AND and OR gates and unary NOT gates. In integer circuits, the values are set of integers and the gates are set union, intersection, complement, and the arithmetic operations + and $\times$

Formal definition

A circuit is composed of a set of values $M$, a set of gate labels $L$ which are families of functions from $M^{i}$ to $M$, where $i$ is a non-negative integer (with $i=0$ for constant gates), and a labelled directed acyclic graph, the labels of which are elements of $L$, a gate $g$ can label a node $n$ of in-degree $i$ if and only if $g$ is defined on $M^{i}$.

Notions

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

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

The depth of a node $n$ is the size of the longest path beginning 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 levelled 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$. It is then usual to consider a family of circuits $(C_{n})_{n\in \mathbb {N} }$, a sequence of circuits indexed by the integers where the circuit $C_{n}$ has got $n$ variables. Families of circuits can thus be seen as functions from $M^{*}$ to $M$.

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

It is usual for some kind of circuits, like boolean circuit, to add restrictions to the circuits one can accept in the family, like having a bounded width, that $size(n)=n^{O(1)}$, which means that the size function of a given family is bounded by a polynomial, that $depth(n)=O(f(n))$ for any function $f$, that the in-degree should be bounded, either by a constant or by a polynomial in the number of inputs.

Complexity and algorithmic problems

Circuit are often used in computational complexity and algorithm theory, there are two different questions one may want to answer:

• Given a circuit, what is the complexity of computing the value of its output. For example, over boolean circuits, this question is P complete and over integer circuits it is not known to be decidable.
• Given a language, what is the minimal size (resp. depth) function which recognizes the language. It is here that, usually, some restrictions are added to the form of the circuits. Over boolean circuit this creates formalism like NC.

References

Circuit is an object used in many fields, but there is no publication about circuit themselves, so those reference are example of book and article speaking of some kind of circuit, but not directly speaking of "circuit" for themselves.

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