In
theoretical computer science
Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation.
It is difficult to circumscribe the theoretical areas precisely. The Associati ...
, a circuit is a
model of computation
In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input. A model describes how ...
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
In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ...
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
In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible inpu ...
on a specific input is a
P-complete
In computational complexity theory, a decision problem is P-complete ( complete for the complexity class P) if it is in P and every problem in P can be reduced to it by an appropriate reduction.
The notion of P-complete decision problems is use ...
problem. If the input is an
integer circuit In computational complexity theory, an integer circuit is a circuit model of computation in which inputs to the circuit are sets of integers and each gate of the circuit computes either a set operation or an arithmetic operation on its input sets. ...
, however, it is unknown whether this problem is
decidable.
Circuit complexity
In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circui ...
attempts to classify
Boolean function
In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth functi ...
s with respect to the size or depth of circuits that can compute them.
See also
*
Arithmetic circuit complexity In computational complexity theory, ''arithmetic circuits'' are the standard model for computing polynomials. Informally, an arithmetic circuit takes as inputs either variables or numbers, and is allowed to either add or multiply two expressions it ...
*
Boolean circuit
In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible inpu ...
*
Circuit complexity
In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circui ...
*
Circuits over sets of natural numbers
Circuit may refer to:
Science and technology
Electrical engineering
* Electrical circuit, a complete electrical network with a closed-loop giving a return path for current
** Analog circuit, uses continuous signal levels
** Balanced circ ...
* The
complexity class
In computational complexity theory, a complexity class is a set (mathematics), set of computational problems "of related resource-based computational complexity, complexity". The two most commonly analyzed resources are time complexity, time and s ...
es
NC,
AC and
TC
*
Quantum circuit
In quantum information theory, a quantum circuit is a model for quantum computation, similar to classical circuits, in which a computation is a sequence of quantum gates, measurements, initializations of qubits to known values, and possibly o ...
and
BQP
References
*
*{{cite journal, last= Yang , first= Ke, title= Integer Circuit Evaluation Is PSPACE-Complete, year = 2001, journal= Journal of Computer and System Sciences , volume =63 , issue =2, September 2001 , pages= 288–303 , issn= 0022-0000, doi= 10.1006/jcss.2001.1768, doi-access= free
Theory of computation
Circuit complexity