In
theoretical computer science
Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumsc ...
, 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
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
. Circuits of this kind provide a generalization of
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 input ...
s and a mathematical model for
digital logic
A logic gate is an idealized or physical device implementing a Boolean function, a logical operation performed on one or more Binary number, binary inputs that produces a single binary output. Depending on the context, the term may refer to an id ...
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
Conjunction may refer to:
* Conjunction (grammar), a part of speech
* Logical conjunction, a mathematical operator
** Conjunction introduction, a rule of inference of propositional logic
* Conjunction (astronomy), in which two astronomical bodies ...
,
disjunction
In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor S ...
, and
negation
In logic, negation, also called the logical complement, is an operation that takes a proposition P to another proposition "not P", written \neg P, \mathord P or \overline. It is interpreted intuitively as being true when P is false, and false ...
gates. The values in 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.
...
are
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
s of
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s and the gates compute
set union
In set theory, the union (denoted by ∪) of a collection of sets is the set of all elements in the collection. It is one of the fundamental operations through which sets can be combined and related to each other.
A refers to a union of ze ...
,
set intersection
In set theory, the intersection of two sets A and B, denoted by A \cap B, is the set containing all elements of A that also belong to B or equivalently, all elements of B that also belong to A.
Notation and terminology
Intersection is writt ...
, and
set complement
In set theory, the complement of a set , often denoted by (or ), is the set of elements not in .
When all sets in the universe, i.e. all sets under consideration, are considered to be members of a given set , the absolute complement of is the ...
, as well as the
arithmetic operation
Arithmetic () is an elementary part of mathematics that consists of the study of the properties of the traditional operations on numbers—addition, subtraction, multiplication, division, exponentiation, and extraction of roots. In the 19th cen ...
s
addition
Addition (usually signified by the Plus and minus signs#Plus sign, plus symbol ) is one of the four basic Operation (mathematics), operations of arithmetic, the other three being subtraction, multiplication and Division (mathematics), division. ...
and
multiplication
Multiplication (often denoted by the cross symbol , by the mid-line dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four elementary mathematical operations of arithmetic, with the other ones being additi ...
.
Formal definition
A circuit is a triple
, 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 ve ...
with labels from
.
The vertices of the graph are called ''gates''. For each gate
of
in-degree
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pai ...
, 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 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 graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called ''simple'' if it does not have any repeated vertices; the length of a path may ...
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 input ...
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 usef ...
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 function ( ...
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 input ...
*
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 Circuits over natural numbers are a mathematical model used in studying computational complexity theory. They are a special case of circuits. The object is a labeled directed acyclic graph the nodes of which evaluate to sets of natural numbers, th ...
* The
complexity class
In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.
In general, a complexity class is defined in terms of ...
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 othe ...
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