
In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...
and
circuit complexity, a Boolean circuit is a mathematical
model
A model is an informative representation of an object, person, or system. The term originally denoted the plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin , .
Models can be divided in ...
for
combinational digital logic circuits. A
formal language
In logic, mathematics, computer science, and linguistics, a formal language is a set of strings whose symbols are taken from a set called "alphabet".
The alphabet of a formal language consists of symbols that concatenate into strings (also c ...
can be decided by a family of Boolean circuits, one circuit for each possible input length.
Boolean circuits are defined in terms of the
logic gate
A logic gate is a device that performs a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic gate, one that has, for ...
s they contain. For example, a circuit might contain
binary AND and
OR gates and
unary NOT gates, or be entirely described by binary
NAND gates. Each gate corresponds to some
Boolean function that takes a fixed number of
bits as input and outputs a single bit.
Boolean circuits provide a model for many digital components used in
computer engineering
Computer engineering (CE, CoE, or CpE) is a branch of engineering specialized in developing computer hardware and software.
It integrates several fields of electrical engineering, electronics engineering and computer science.
Computer engi ...
, including
multiplexer
In electronics, a multiplexer (or mux; spelled sometimes as multiplexor), also known as a data selector, is a device that selects between several Analog signal, analog or Digital signal (electronics), digital input signals and forwards the sel ...
s,
adders, and
arithmetic logic unit
In computing, an arithmetic logic unit (ALU) is a Combinational logic, combinational digital circuit that performs arithmetic and bitwise operations on integer binary numbers. This is in contrast to a floating-point unit (FPU), which operates on ...
s, but they exclude
sequential logic. They are an abstraction that omits many aspects relevant to designing real digital logic circuits, such as
metastability,
fanout,
glitches,
power consumption, and
propagation delay
Propagation delay is the time duration taken for a signal to reach its destination, for example in the electromagnetic field, a wire, speed of sound, gas, fluid or seismic wave, solid body.
Physics
* An electromagnetic wave travelling through ...
variability.
Formal definition
In giving a formal definition of Boolean circuits,
Vollmer starts by defining a basis as set ''B'' of Boolean functions, corresponding to the gates allowable in the circuit model. A Boolean circuit over a basis ''B'', with ''n'' inputs and ''m'' outputs, is then defined as a finite
directed acyclic graph. Each vertex corresponds to either a basis function or one of the inputs, and there is a set of exactly ''m'' nodes which are labeled as the outputs.
The edges must also have some ordering, to distinguish between different arguments to the same Boolean function.
[
As a special case, a propositional formula or Boolean expression is a Boolean circuit with a single output node in which every other node has fan-out of 1. Thus, a Boolean circuit can be regarded as a generalization that allows shared subformulas and multiple outputs.
A common basis for Boolean circuits is the set , which is functionally complete, i. e. from which all other Boolean functions can be constructed.
]
Computational complexity
Background
A particular circuit acts only on inputs of fixed size. However, formal language
In logic, mathematics, computer science, and linguistics, a formal language is a set of strings whose symbols are taken from a set called "alphabet".
The alphabet of a formal language consists of symbols that concatenate into strings (also c ...
s (the string-based representations of decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...
s) contain strings of different lengths, so languages cannot be fully captured by a single circuit (in contrast to the Turing machine model, in which a language is fully described by a single Turing machine). A language is instead represented by a ''circuit family''. A circuit family is an infinite list of circuits , where has input variables. A circuit family is said to decide a language if, for every string , is in the language if and only if , where is the length of . In other words, a language is the set of strings which, when applied to the circuits corresponding to their lengths, evaluate to 1.
Complexity measures
Several important complexity measures can be defined on Boolean circuits, including circuit depth, circuit size, and the number of alternations between AND gates and OR gates. For example, the size complexity of a Boolean circuit is the number of gates in the circuit.
There is a natural connection between circuit size complexity and time complexity
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations ...
.[ Intuitively, a language with small time complexity (that is, requires relatively few sequential operations on a ]Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
), also has a small circuit complexity (that is, requires relatively few Boolean operations). Formally, it can be shown that if a language is in , where is a function , then it has circuit size complexity .
Complexity classes
Several important complexity classes are defined in terms of Boolean circuits. The most general of these is P/poly, the set of languages that are decidable by polynomial-size circuit families. It follows directly from the fact that languages in have circuit complexity that PP/poly. In other words, any problem that can be computed in polynomial time by a deterministic Turing machine can also be computed by a polynomial-size circuit family. It is further the case that the inclusion is proper (i.e. PP/poly) because there are undecidable problems that are in P/poly. P/poly turns out to have a number of properties that make it highly useful in the study of the relationships between complexity classes. In particular, it is helpful in investigating problems related to P versus NP. For example, if there is any language in NP that is not in P/poly then PNP. P/poly also helps to investigate properties of the polynomial hierarchy. For example, if NP ⊆ P/poly, then PH collapses to . A full description of the relations between P/poly and other complexity classes is available at " Importance of P/poly". P/poly also has the interesting feature that it can be equivalently defined as the class of languages recognized by a polynomial-time Turing machine with a polynomial-bounded advice function.
Two subclasses of P/poly that have interesting properties in their own right are NC and AC. These classes are defined not only in terms of their circuit size but also in terms of their ''depth''. The depth of a circuit is the length of the longest directed path from an input node to the output node. The class NC is the set of languages that can be solved by circuit families that are restricted not only to having polynomial-size but also to having polylogarithmic depth. The class AC is defined similarly to NC, however gates are allowed to have unbounded fan-in (that is, the AND and OR gates can be applied to more than two bits). NC is an important class because it turns out that it represents the class of languages that have efficient parallel algorithms.
Circuit evaluation
The circuit value problem — the problem of computing the output of a given Boolean circuit on a given input string — 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 ...
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...
. Therefore, this problem is considered to be "inherently sequential" in the sense that there is likely no efficient, highly parallel algorithm that solves the problem.
Completeness
Logic circuits are physical representation of simple logic operations, AND, OR and NOT (and their combinations, such as non-sequential flip-flops or circuit networks), that form a mathematical structure known as Boolean algebra
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variable (mathematics), variables are the truth values ''true'' and ''false'', usually denot ...
. They are complete in sense that they can perform any deterministic algorithm. However, it just happens that this is not all there is. In the physical world we also encounter randomness, notable in small systems governed by quantization effects, which is described by theory of quantum mechanics
Quantum mechanics is the fundamental physical Scientific theory, theory that describes the behavior of matter and of light; its unusual characteristics typically occur at and below the scale of atoms. Reprinted, Addison-Wesley, 1989, It is ...
. Logic circuits cannot produce any randomness, and in that sense they form an incomplete logic set. Remedy to that is found in adding an ad-hoc random bit generator to logic networks, or computers, such as in probabilistic Turing machine. A recent work has introduced a theoretical concept of an inherently random logic circuit named ''random flip-flop'', which completes the set. It conveniently packs randomness and is inter-operable with deterministic Boolean logic circuits. However, an algebraic structure equivalent of Boolean algebra and associated methods of circuit construction and reduction for the extended set is yet unknown.
See also
* Circuit satisfiability
* Logic gate
A logic gate is a device that performs a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic gate, one that has, for ...
* Boolean logic
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variable (mathematics), variables are the truth values ''true'' and ''false'', usually denot ...
* Switching lemma
Footnotes
{{DEFAULTSORT:Boolean Circuit
Computational complexity theory
Digital circuits
Logic in computer science