Boolean circuit: Difference between revisions

Content deleted Content added

Inline

Revision as of 17:19, 16 August 2024

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

Boolean circuits are defined in terms of the logic gates 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, including multiplexers, adders, and arithmetic logic units, 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 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.^[1]^: 8 The edges must also have some ordering, to distinguish between different arguments to the same Boolean function.^[1]^: 9

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 {AND, OR, NOT}, 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 languages (the string-based representations of decision problems) 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 $(C_{0},C_{1},C_{2},...)$ , where $C_{n}$ has $n$ input variables. A circuit family is said to decide a language $L$ if, for every string $w$ , $w$ is in the language $L$ if and only if $C_{n}(w)=1$ , where $n$ is the length of $w$ . In other words, a language is the set of strings which, when applied to the circuits corresponding to their lengths, evaluate to 1.^[2]^: 354

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.^[2]^: 355 Intuitively, a language with small time complexity (that is, requires relatively few sequential operations on a Turing machine), also has a small circuit complexity (that is, requires relatively few Boolean operations). Formally, it can be shown that if a language is in ${\mathsf {TIME}}(t(n))$ , where $t$ is a function $t:\mathbb {N} \to \mathbb {N}$ , then it has circuit complexity $O(t^{2}(n))$ .

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 ${\mathsf {TIME}}(t(n))$ have circuit complexity $O(t^{2}(n))$ that P $\subseteq$ P/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. P $\subsetneq$ P/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 P $\neq$ NP.^[3]^: 286 P/poly also helps to investigate properties of the polynomial hierarchy. For example, if NP ⊆ P/poly, then PH collapses to $\Sigma _{2}^{\mathsf {P}}$ . 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 decision problem.^[3]^: 119 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. 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. 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^[4] 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.

Footnotes

^ ^a ^b Vollmer, Heribert (1999). Introduction to Circuit Complexity. Berlin: Springer. ISBN 3-540-64310-9.
^ ^a ^b Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). USA: Thomson Course Technology. ISBN 978-0-534-95097-2.
^ ^a ^b Arora, Sanjeev; Barak, Boaz (2009). Computational Complexity: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4.
^ Stipčević, Mario; Batelić, Mateja (2022). "Entropy considerations in improved circuits for a biologically-inspired random pulse computer". Scientific Reports. 12: 115. arXiv:1908.04779. doi:10.1038/s41598-021-04177-9.

[Vollmer-1] Vollmer, Heribert (1999). Introduction to Circuit Complexity. Berlin: Springer. ISBN 3-540-64310-9.

[Sipser-2] Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). USA: Thomson Course Technology. ISBN 978-0-534-95097-2.

[arorabarak-3] Arora, Sanjeev; Barak, Boaz (2009). Computational Complexity: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4.

[4] Stipčević, Mario; Batelić, Mateja (2022). "Entropy considerations in improved circuits for a biologically-inspired random pulse computer". Scientific Reports. 12: 115. arXiv:1908.04779. doi:10.1038/s41598-021-04177-9.

[1]

[2]

[3]

[4]

@@ Line 1: / Line 1: @@
-{{Short description|model of computation}}
+{{Short description|Model of computation}}
-[[File:Three_input_Boolean_circuit.jpg|thumb|right|300px|Example Boolean circuit. The <math>\wedge</math> nodes are [[AND gate]]s, the <math>\vee</math> nodes are [[OR gate]]s, and the <math>\neg</math> nodes are [[NOT gate]]s]]
+[[File:Three_input_Boolean_circuit.jpg|thumb|right|300px|Example Boolean circuit. The &and; nodes are AND gates, the &or; nodes are OR gates, and the &not; nodes are NOT gates]]
-In [[computational complexity theory]] and [[circuit complexity]], a '''Boolean circuit''' is a mathematical [[model of computation|model]] for combinational [[digital electronics|digital logic circuits]]. A [[formal language]] can be decided by a family of Boolean circuits, one circuit for each possible input length. Boolean circuits are also used as a formal model for [[combinational logic]] in digital electronics.
+In [[computational complexity theory]] and [[circuit complexity]], a '''Boolean circuit''' is a mathematical [[model of computation|model]] for [[combinational logic|combinational]] [[digital electronics|digital logic circuits]]. A [[formal language]] 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]]s they contain. For example, a circuit might contain [[binary function|binary]] AND and OR gates and [[unary operation|unary]] NOT gates, or be entirely described by binary [[NAND gate]]s. Each gate corresponds to some [[Boolean function]] that takes a fixed number of [[bit]]s as input and outputs a single bit.
+Boolean circuits are defined in terms of the [[logic gate]]s they contain. For example, a circuit might contain [[binary function|binary]] [[AND gate|AND]] and [[OR gate]]s and [[unary operation|unary]] [[NOT gate]]s, or be entirely described by binary [[NAND gate]]s. Each gate corresponds to some [[Boolean function]] that takes a fixed number of [[bit]]s as input and outputs a single bit.
 Boolean circuits provide a model for many digital components used in [[computer engineering]], including [[multiplexer]]s, [[adder (electronics)|adder]]s, and [[arithmetic logic unit]]s, but they exclude [[sequential logic]].  They are an abstraction that omits many aspects relevant to designing real digital logic circuits, such as [[metastability (electronics)|metastability]], [[fanout]], [[hazard (logic)|glitches]], [[power optimization (EDA)|power consumption]], and [[propagation delay]] variability.
 == Formal definition ==
-In giving a formal definition of Boolean circuits, [[Heribert Vollmer|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.<ref>Vollmer 1999, p. 8.</ref> The edges must also have some ordering, to distinguish between different arguments to the same Boolean function.<ref>Vollmer 1999, p. 9.</ref>
+In giving a formal definition of Boolean circuits, [[Heribert Vollmer|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.<ref name=Vollmer>{{cite book | last = Vollmer | first = Heribert | title = Introduction to Circuit Complexity | year = 1999 | publisher = Springer | location = Berlin | isbn = 3-540-64310-9 }}</ref>{{rp|8}} The edges must also have some ordering, to distinguish between different arguments to the same Boolean function.<ref name=Vollmer/>{{rp|9}}
 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.
@@ Line 17: / Line 17: @@
 == Computational complexity ==
 === Background ===
-A particular circuit acts only on inputs of fixed size. However, [[formal language]]s (the [[string (computer science)|string-based]] representations of [[decision problem]]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 <math>(C_0,C_1,C_2,...)</math>, where <math>C_n</math> has <math>n</math> input variables. A circuit family is said to decide a language <math>L</math> if, for every string <math>w</math>, <math>w</math> is in the language <math>L</math> if and only if <math>C_n(w)=1</math>, where <math>n</math> is the length of <math>w</math>. In other words, a language is the set of strings which, when applied to the circuits corresponding to their lengths, evaluate to 1.<ref>{{cite book|last=Sipser|first=Michael|authorlink=Michael Sipser|title=Introduction to the Theory of Computation|edition=2nd|year=2006|publisher=Thomson Course Technology|location=USA|isbn=978-0-534-95097-2|title-link=Introduction to the Theory of Computation|pages=354}}</ref>
+A particular circuit acts only on inputs of fixed size. However, [[formal language]]s (the [[string (computer science)|string-based]] representations of [[decision problem]]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 <math>(C_0,C_1,C_2,...)</math>, where <math>C_n</math> has <math>n</math> input variables. A circuit family is said to decide a language <math>L</math> if, for every string <math>w</math>, <math>w</math> is in the language <math>L</math> if and only if <math>C_n(w)=1</math>, where <math>n</math> is the length of <math>w</math>. In other words, a language is the set of strings which, when applied to the circuits corresponding to their lengths, evaluate to 1.<ref name=Sipser>{{cite book|last=Sipser|first=Michael|author-link=Michael Sipser|title=Introduction to the Theory of Computation|edition=2nd|year=2006|publisher=Thomson Course Technology|location=USA|isbn=978-0-534-95097-2|title-link=Introduction to the Theory of Computation}}</ref>{{rp|354}}
 === Complexity measures ===
 {{See also|Circuit complexity}}
-Several important [[Computational complexity theory|complexity measures]] can be defined on Boolean circuits, including circuit depth, circuit size, and number of alternations between AND gates and OR gates. For example, the size complexity of a Boolean circuit is the number of gates.
+Several important [[Computational complexity theory|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.
-It turns out that there is a natural connection between circuit size complexity and [[time complexity]].<ref>{{cite book|last=Sipser|first=Michael|authorlink=Michael Sipser|title=Introduction to the Theory of Computation|edition=2nd|year=2006|publisher=Thomson Course Technology|location=USA|isbn=978-0-534-95097-2|title-link=Introduction to the Theory of Computation|page=355}}</ref> Intuitively, a language with small time complexity (that is, requires relatively few sequential operations on a [[Turing machine]]), also has a small circuit complexity (that is, requires relatively few Boolean operations). Formally, it can be shown that if a language is in <math>\mathsf{TIME}(t(n))</math>, where <math>t</math> is a function <math>t:\mathbb{N} \to \mathbb{N}</math>, then it has circuit complexity <math>O(t^2(n))</math>.
+There is a natural connection between circuit size complexity and [[time complexity]].<ref name=Sipser/>{{rp|355}} Intuitively, a language with small time complexity (that is, requires relatively few sequential operations on a [[Turing machine]]), also has a small circuit complexity (that is, requires relatively few Boolean operations). Formally, it can be shown that if a language is in <math>\mathsf{TIME}(t(n))</math>, where <math>t</math> is a function <math>t:\mathbb{N} \to \mathbb{N}</math>, then it has circuit complexity <math>O(t^2(n))</math>.
 === Complexity classes ===
 {{Main article|Complexity classes#Boolean circuits}}
-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 <math>\mathsf{TIME}(t(n))</math> have circuit complexity <math>O(t^2(n))</math> that [[P]]<math>\subseteq</math>P/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. P<math>\subsetneq</math>P/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 P<math>\neq</math>NP.<ref name="arorabarak">{{cite book |last1=Arora |first1=Sanjeev |last2=Barak |first2=Boaz |title=Computational Complexity: A Modern Approach |date=2009 |publisher=Cambridge University Press |isbn=978-0-521-42426-4 |page=286}}</ref> P/poly also helps to investigate properties of the [[polynomial hierarchy]]. For example, if [[NP (complexity)|NP]] ⊆ P/poly, then PH collapses to <math>\Sigma_2^{\mathsf P}</math>. A full description of the relations between P/poly and other complexity classes is available at "[[P/poly#Importance of P/poly|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 (complexity)|advice function]].
+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 <math>\mathsf{TIME}(t(n))</math> have circuit complexity <math>O(t^2(n))</math> that [[P (complexity)|P]]<math>\subseteq</math>P/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. P<math>\subsetneq</math>P/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 P<math>\neq</math>NP.<ref name="arorabarak">{{cite book |last1=Arora |first1=Sanjeev |last2=Barak |first2=Boaz |title=Computational Complexity: A Modern Approach |date=2009 |publisher=Cambridge University Press |isbn=978-0-521-42426-4}}</ref>{{rp|286}} P/poly also helps to investigate properties of the [[polynomial hierarchy]]. For example, if [[NP (complexity)|NP]] ⊆ P/poly, then PH collapses to <math>\Sigma_2^{\mathsf P}</math>. A full description of the relations between P/poly and other complexity classes is available at "[[P/poly#Importance of P/poly|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 (complexity)|advice function]].
 Two subclasses of P/poly that have interesting properties in their own right are [[NC (complexity)|NC]] and [[AC (complexity)|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 algorithm]]s.
 === Circuit evaluation ===
-The [[Circuit Value Problem]] — the problem of computing the output of a given Boolean circuit on a given input [[binary string|string]] — is a [[P-complete]] [[decision problem]].<ref>{{cite book |last1=Arora |first1=Sanjeev |last2=Barak |first2=Boaz |title=Computational Complexity: A Modern Approach |date=2009 |publisher=Cambridge University Press |isbn=978-0-521-42426-4 |page=119}}</ref> 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.
+The [[Circuit Value Problem]] — the problem of computing the output of a given Boolean circuit on a given input [[binary string|string]] — is a [[P-complete]] [[decision problem]].<ref name="arorabarak"/>{{rp|119}} 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]]. 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. 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<ref>{{cite journal |last1=Stipčević |first1=Mario |last2=Batelić |first2=Mateja |title=Entropy considerations in improved circuits for a biologically-inspired random pulse computer |journal=Scientific Reports |volume=12 |page=115 |year=2022 |doi=10.1038/s41598-021-04177-9|doi-access=free |arxiv=1908.04779 }}</ref> 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 ==
@@ Line 38: / Line 41: @@
 * [[Logic gate]]
 * [[Boolean logic]]
+*[[Switching lemma]]
 == Footnotes ==
-{{reflist}}
+{{Reflist}}
+{{Digital electronics}}
-== References ==
+{{Authority control}}
-{{refbegin}}
-*{{cite book | last = Vollmer | first = Heribert | title = Introduction to Circuit Complexity | year = 1999 | publisher = Springer | location = Berlin | isbn = 3-540-64310-9}}
-{{refend}}
 {{DEFAULTSORT:Boolean Circuit}}

v t e Digital electronics
Components	Transistor Resistor Inductor Capacitor Printed electronics Printed circuit board Electronic circuit Flip-flop Memory cell Combinational logic Sequential logic Logic gate Boolean circuit Integrated circuit (IC) Hybrid integrated circuit (HIC) Mixed-signal integrated circuit Three-dimensional integrated circuit (3D IC) Emitter-coupled logic (ECL) Erasable programmable logic device (EPLD) Macrocell array Programmable logic array (PLA) Programmable logic device (PLD) Programmable Array Logic (PAL) Generic Array Logic (GAL) Complex programmable logic device (CPLD) Field-programmable gate array (FPGA) Field-programmable object array (FPOA) Application-specific integrated circuit (ASIC) Tensor Processing Unit (TPU)
Theory	Digital signal Boolean algebra Logic synthesis Logic in computer science Computer architecture Digital signal Digital signal processing Circuit minimization Switching circuit theory Gate equivalent
Design	Logic synthesis Place and route Placement Routing Transaction-level modeling Register-transfer level Hardware description language High-level synthesis Formal equivalence checking Synchronous logic Asynchronous logic Finite-state machine Hierarchical state machine
Applications	Computer hardware Hardware acceleration Digital audio radio Digital photography Digital telephone Digital video cinematography television Electronic literature
Design issues	Metastability Runt pulse