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.

Circuits as functions

The labels of the leaves can also be variables which take values in $M$. If there are $n$ leaves, 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 $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, becoming functions from $\mathbb {N}$ to $\mathbb {N}$; for example, $size(n)$ is the size of the $n$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

• Vollmer, Heribert (1999). Introduction to Circuit Complexity. Berlin: Springer. ISBN 978-3-540-64310-4.
• Yang, Ke (2001). "Integer Circuit Evaluation Is PSPACE-Complete". Journal of Computer and System Sciences. 63 (2, September 2001): 288–303. doi:10.1006/jcss.2001.1768. ISSN 0022-0000.