Intheoretical computer science, acircuit is amodel 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 ofBoolean circuits and a mathematical model for digitallogic circuits. Circuits are defined by the gates they contain and the values the gates can produce. For example, the values in a Boolean circuit areBoolean 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.

A circuit is a triplet${\displaystyle (M,L,G)}$, where

• ${\displaystyle M}$ is a set of values,
• ${\displaystyle L}$ is a set of gate labels, each of which is a function from${\displaystyle M^i}$ to${\displaystyle M}$ for some non-negative integer${\displaystyle i}$ (where${\displaystyle i}$ represents the number of inputs to the gate), and
• ${\displaystyle G}$ is alabelleddirected acyclic graph with labels from${\displaystyle L}$.

The vertices of the graph are calledgates. For each gate${\displaystyle g}$ ofin-degree${\displaystyle i}$, the gate${\displaystyle g}$ can be labeled by an element${\displaystyle \ell }$ of${\displaystyle L}$ if and only if${\displaystyle \ell }$ is defined on${\displaystyle M^i.}$

The gates of in-degree 0 are calledinputs orleaves. The gates of out-degree 0 are calledoutputs. If there is an edge from gate${\displaystyle g}$ to gate${\displaystyle h}$ in the graph${\displaystyle G}$ then${\displaystyle h}$ is called achild of${\displaystyle g}$. We suppose there is an order on the vertices of the graph, so we can speak of the${\displaystyle k}$th child of a gate when${\displaystyle k}$ is less than or equal to the out-degree of the gate.

Thesize of a circuit is the number of nodes of a circuit. Thedepth of a gate${\displaystyle g}$ is the length of thelongest path in${\displaystyle G}$ beginning at${\displaystyle g}$ up to an output gate. In particular, the gates of out-degree 0 are the only gates of depth 1. Thedepth of a circuit is the maximum depth of any gate.

Level${\displaystyle i}$ is the set of all gates of depth${\displaystyle i}$. Alevelled circuit is a circuit in which the edges to gates of depth${\displaystyle i}$ comes only from gates of depth${\displaystyle i+1}$ or from the inputs. In other words, edges only exist between adjacent levels of the circuit. Thewidth of a levelled circuit is the maximum size of any level.

The exact value${\displaystyle V(g)}$ of a gate${\displaystyle g}$ with in-degree${\displaystyle i}$ and label${\displaystyle l}$ is defined recursively for all gates${\displaystyle g}$.

where each${\displaystyle g_j}$ is a parent of${\displaystyle g}$.

The value of the circuit is the value of each of the output gates.

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

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

Computing the output of a givenBoolean circuit on a specific input is aP-complete problem. If the input is aninteger circuit, however, it is unknown whether this problem isdecidable.

Circuit complexity attempts to classifyBoolean functions with respect to the size or depth of circuits that can compute them.

• Arithmetic circuit complexity
• Boolean circuit
• Circuit complexity
• Circuits over sets of natural numbers
• Thecomplexity classesNC,AC andTC
• Quantum circuit andBQP

• 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.

• Theory of computation
• Circuit complexity

• Articles with short description
• Short description matches Wikidata