Namespaces
Variants
Actions

Difference between revisions of "Boolean circuit"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (Automatically changed introduction)
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
An <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b1203701.png" />-ary Boolean function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b1203702.png" /> is a function from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b1203703.png" /> with values in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b1203704.png" />. The values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b1203705.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b1203706.png" /> are called Boolean values, or bits, or truth values if they are identified with false and true (cf. also [[Boolean function|Boolean function]]). Elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b1203707.png" /> are Boolean strings of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b1203708.png" /> (or bit strings). <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b1203709.png" /> is the set of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037010.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037011.png" />-ary Boolean functions.
+
<!--This article has been texified automatically. Since there was no Nroff source code for this article,
 +
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 +
was used.
 +
If the TeX and formula formatting is correct and if all png images have been replaced by TeX code, please remove this message and the {{TEX|semi-auto}} category.
  
A basis of connectives is any non-empty set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037012.png" /> of Boolean functions, not necessarily of the same arity. An <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037014.png" />-formula for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037015.png" /> is a formula built from Boolean variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037016.png" /> using connectives from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037017.png" />. A basis <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037018.png" /> is complete if all Boolean functions are definable by an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037019.png" />-formula. Examples of complete bases are: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037020.png" />, the set of all binary Boolean functions, or the DeMorgan basis <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037021.png" />.
+
Out of 90 formulas, 87 were replaced by TEX code.-->
  
A more general way to define (equivalently, compute) Boolean functions is by circuits (straight line programs) that are simplified mathematical models of integrated circuits. A Boolean circuit over a basis <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037022.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037023.png" /> is a sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037024.png" /> of functions from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037025.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037026.png" /> and such that any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037027.png" /> is either one of the projections <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037028.png" /> or is equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037029.png" />, for some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037030.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037031.png" />. Drawing directed edges from all such <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037032.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037033.png" />, and labelling <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037034.png" /> by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037035.png" />, defines a labelled directed acyclic graph (cf. also [[Graph, oriented|Graph, oriented]]). The size of the circuit is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037036.png" />. The maximum length of a path from a vertex corresponding to one of the inputs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037037.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037038.png" /> is the depth of the circuit. Note that formulas are circuits whose graphs are trees.
+
{{TEX|semi-auto}}{{TEX|part}}
 +
An $n$-ary Boolean function $f ( x _ { 1 } , \ldots , x _ { n } )$ is a function from $\{ 0,1 \} ^ { n }$ with values in $\{ 0,1 \}$. The values $0$, $1$ are called Boolean values, or bits, or truth values if they are identified with false and true (cf. also [[Boolean function|Boolean function]]). Elements of $\{ 0,1 \} ^ { n }$ are Boolean strings of length $n$ (or bit strings). $B _ { n }$ is the set of all $2 ^ { 2 ^ { n } }$ $n$-ary Boolean functions.
  
There are three basic ways to measure the complexity of a Boolean function, given a basis <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037039.png" />:
+
A basis of connectives is any non-empty set $\Omega$ of Boolean functions, not necessarily of the same arity. An $\Omega$-formula for $f ( x _ { 1 } , \ldots , x _ { n } )$ is a formula built from Boolean variables $x _ { 1 } , \ldots , x _ { n }$ using connectives from $\Omega$. A basis $\Omega$ is complete if all Boolean functions are definable by an $\Omega$-formula. Examples of complete bases are: $B _ { 2 }$, the set of all binary Boolean functions, or the DeMorgan basis $\{ 0,1 , \neg , \vee , \wedge \}$.
  
the minimum size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037040.png" /> of an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037041.png" />-formula defining <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037042.png" />,
+
A more general way to define (equivalently, compute) Boolean functions is by circuits (straight line programs) that are simplified mathematical models of integrated circuits. A Boolean circuit over a basis $\Omega$ for $f \in B _ { n }$ is a sequence $g _ { 1 } , \ldots , g _ { k }$ of functions from $B _ { n }$ such that $g _ { k } = f$ and such that any $g_i$ is either one of the projections $x _ { 1 } , \ldots , x _ { n }$ or is equal to $h ( g _ { j _ { 1 } } , \dots , g _ { j _ { r } } )$, for some $h \in \Omega$ and $j_1 , \ldots , j _ { r } &lt; i$. Drawing directed edges from all such $j _ { 1 } , \dots , j _ { r }$ to $i$, and labelling $i$ by $h$, defines a labelled directed acyclic graph (cf. also [[Graph, oriented|Graph, oriented]]). The size of the circuit is $k$. The maximum length of a path from a vertex corresponding to one of the inputs $x _ { 1 } , \ldots , x _ { n }$ to $g_{k}$ is the depth of the circuit. Note that formulas are circuits whose graphs are trees.
  
the minimum size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037043.png" /> of a circuit over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037044.png" /> defining <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037045.png" />, and
+
There are three basic ways to measure the complexity of a Boolean function, given a basis $\Omega$:
  
the minimum depth <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037046.png" /> of a circuit over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037047.png" /> defining <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037048.png" />. For two complete bases <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037049.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037050.png" />, the measures <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037051.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037052.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037053.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037054.png" /> are proportional to each other, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037055.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037056.png" /> are polynomially related. A relation exists between the formula size and the circuit depth (see [[#References|[a13]]]): <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037057.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037058.png" /> are proportional to each other, provided <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037059.png" /> is finite.
+
the minimum size $L _ { \Omega } ( f )$ of an $\Omega$-formula defining $f$,
  
By estimating the number of circuits of a bounded size, C.E. Shannon [[#References|[a11]]] proved (cf. [[#References|[a14]]] for an optimal computation) that for almost-all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037060.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037061.png" />. On the other hand,
+
the minimum size $C _ { \Omega } ( f )$ of a circuit over $\Omega$ defining $f$, and
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037062.png" /></td> </tr></table>
+
the minimum depth $D _ { \Omega } ( f )$ of a circuit over $\Omega$ defining $f$. For two complete bases $\Omega$, $\Omega ^ { \prime }$, the measures $C _ { \Omega } ( f )$, $C _ { \Omega ^ { \prime } } ( f )$ and $D _ { \Omega } ( f )$, $D _ { \Omega ^ { \prime } } ( f )$ are proportional to each other, and $L _ { \Omega } ( f )$, $L _ { \Omega ^ { \prime } } ( f )$ are polynomially related. A relation exists between the formula size and the circuit depth (see [[#References|[a13]]]): $\operatorname { log } ( L _ { \Omega } ( f ) )$ and $D _ { \Omega } ( f )$ are proportional to each other, provided $\Omega$ is finite.
  
for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037063.png" />, see [[#References|[a8]]].
+
By estimating the number of circuits of a bounded size, C.E. Shannon [[#References|[a11]]] proved (cf. [[#References|[a14]]] for an optimal computation) that for almost-all $f \in B _ { n }$, $C _ { B _ { 2 } } ( f ) \geq 2 ^ { n } / n$. On the other hand,
  
For a [[Formal language|formal language]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037064.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037065.png" /> be the characteristic function of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037066.png" />. The main open problem in Boolean complexity theory (cf. [[#References|[a4]]]) is whether there is a language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037067.png" /> accepted by a non-deterministic polynomial-time Turing machine (cf. also [[Turing machine|Turing machine]]) such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037068.png" /> is not bounded by any polynomial in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037069.png" />. The importance of this question stems from the fact that the affirmative answer implies that the computational complexity classes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037071.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037073.png" /> are different, as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037074.png" /> is bounded by a polynomial for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037075.png" /> decidable in polynomial time (cf. [[#References|[a10]]] and also [[NP|<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037076.png" />]]).
+
\begin{equation*} C _ { B _ { 2 } } ( f ) \leq \frac { 2 ^ { n } } { n } ( 1 + o ( 1 ) ), \end{equation*}
  
No super-linear lower bounds on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037077.png" /> are known for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037078.png" />. However, if additional restrictions are put on the circuits, then strong lower bounds are known. Most notable are two results: any circuit of depth <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037079.png" /> over a DeMorgan-like basis <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037080.png" />, allowing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037081.png" /> of unbounded arity, computing the parity function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037082.png" /> must have size at least <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037083.png" /> (see [[#References|[a1]]], [[#References|[a5]]], [[#References|[a15]]], [[#References|[a6]]]), and any circuit in the monotone basis <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037084.png" /> computing whether or not a graph on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037085.png" /> vertices contains a clique of size at least <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037086.png" /> must have size at least <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037087.png" /> (see [[#References|[a9]]], [[#References|[a3]]]).
+
for all $f \in B _ { n }$, see [[#References|[a8]]].
  
Interesting upper bounds are also known: a DeMorgan circuit of size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037088.png" /> for multiplication of two <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037089.png" />-bit long numbers, [[#References|[a12]]] (it is still open (1998) if there are linear size circuits), and a monotone DeMorgan sorting network of simultaneous size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037090.png" /> and depth <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037091.png" />, see [[#References|[a2]]].
+
For a [[Formal language|formal language]] $L \subseteq \{ 0,1 \}^*$, let $L_{n}$ be the characteristic function of $L \cap \{ 0,1 \} ^ { n }$. The main open problem in Boolean complexity theory (cf. [[#References|[a4]]]) is whether there is a language $L$ accepted by a non-deterministic polynomial-time Turing machine (cf. also [[Turing machine|Turing machine]]) such that $C _ { \Omega } ( L _ { n } )$ is not bounded by any polynomial in $n$. The importance of this question stems from the fact that the affirmative answer implies that the computational complexity classes $\mathcal{P}$ and $\cal N P$ are different, as $C _ { B _ { 2 } } ( L _ { n } )$ is bounded by a polynomial for any $L$ decidable in polynomial time (cf. [[#References|[a10]]] and also [[NP|$\cal N P$]]).
 +
 
 +
No super-linear lower bounds on $C _ { B _ { 2 } } ( L _ { n } )$ are known for any $L \in \mathcal{N} \mathcal{P}$. However, if additional restrictions are put on the circuits, then strong lower bounds are known. Most notable are two results: any circuit of depth $d \geq 2$ over a DeMorgan-like basis $\{ 0,1 , \neg , \vee , \wedge \}$, allowing $\vee , \wedge$ of unbounded arity, computing the parity function $\oplus _ { n }$ must have size at least $\operatorname { exp } ( \Omega ( n ^ { 1 / d - 1 } ) )$ (see [[#References|[a1]]], [[#References|[a5]]], [[#References|[a15]]], [[#References|[a6]]]), and any circuit in the monotone basis $\{ 0,1 , \vee , \wedge \}$ computing whether or not a graph on $n$ vertices contains a clique of size at least $k \leq n ^ { 1 / 4 }$ must have size at least $n ^ { \Omega ( \sqrt { k } ) }$ (see [[#References|[a9]]], [[#References|[a3]]]).
 +
 
 +
Interesting upper bounds are also known: a DeMorgan circuit of size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037088.png"/> for multiplication of two $n$-bit long numbers, [[#References|[a12]]] (it is still open (1998) if there are linear size circuits), and a monotone DeMorgan sorting network of simultaneous size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037090.png"/> and depth $O( \operatorname { log } n )$, see [[#References|[a2]]].
  
 
Various parts of computational complexity (cf. also [[Complexity theory|Complexity theory]]) are directly related to lower-bound problems for Boolean functions; for example, communication complexity, cf. [[#References|[a7]]].
 
Various parts of computational complexity (cf. also [[Complexity theory|Complexity theory]]) are directly related to lower-bound problems for Boolean functions; for example, communication complexity, cf. [[#References|[a7]]].
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  M. Ajtai,  "<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037092.png" /> - formulae on finite structures"  ''Ann. Pure Appl. Logic'' , '''24'''  (1983)  pp. 1–48</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  M. Ajtai,  J. Komlós,  E. Szemerédi,  "An <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037093.png" /> sorting network"  ''Combinatorica'' , '''3'''  (1983)  pp. 1–19</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  N. Alon,  R. Boppana,  "The monotone circuit complexity of Boolean functions"  ''Combinatorica'' , '''7''' :  1  (1987)  pp. 1–22</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  R. Boppana,  M. Sipser,  "Complexity of finite functions"  J. van Leeuwen (ed.) , ''Handbook of Theoretical Computer Science'' , '''A'''  (1990)  pp. 758–804; Chap.14</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  M. Furst,  J.B. Saxe,  M. Sipser,  "Parity, circuits and the polynomial-time hierarchy"  ''Math. Systems Theory'' , '''17'''  (1984)  pp. 13–27</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  J. Hastad,  "Almost optimal lower bounds for small depth circuits"  S. Micali (ed.) , ''Randomness and Computation'' , ''Adv. Comput. Res.'' , '''5''' , JAI Press  (1989)  pp. 143–170</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  E. Kushilevitz,  N. Nisan,  "Communication complexity" , Cambridge Univ. Press  (1996)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  O.B. Lupanov,  "A method of circuit synthesis"  ''Izv. V.U.Z. (Radiofizika)'' , '''1''' :  1  (1958)  pp. 120–140  (In Russian)</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  A.A. Razborov,  "Lower bounds on the monotone complexity of some Boolean functions"  ''Soviet Math. Dokl.'' , '''31'''  (1985)  pp. 354–357</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  J.E. Savage,  "Computational work and time on finite machines"  ''J. ACM'' , '''19''' :  4  (1972)  pp. 660–674</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  C.E. Shannon,  "The synthesis of two-terminal switching circuits"  ''Bell Systems Techn. J.'' , '''28''' :  1  (1949)  pp. 59–98</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top">  A. Schonhage,  V. Strassen,  "Schnelle Multiplikation grosser Zahlen"  ''Computing'' , '''7'''  (1971)  pp. 281–292</TD></TR><TR><TD valign="top">[a13]</TD> <TD valign="top">  P.M. Spira,  "On time-hardware complexity of tradeoffs for Boolean functions" , ''Proc. 4th Hawaii Symp. System Sciences'' , North Hollywood&amp;Western Periodicals  (1971)  pp. 525–527</TD></TR><TR><TD valign="top">[a14]</TD> <TD valign="top">  I. Wegener,  "The complexity of Boolean functions" , Wiley&amp;Teubner  (1987)</TD></TR><TR><TD valign="top">[a15]</TD> <TD valign="top">  Y. Yao,  "Separating the polynomial-time hierarchy by oracles" , ''Proc. 26th Ann. IEEE Symp. Found. Comput. Sci.''  (1985)  pp. 1–10</TD></TR></table>
+
<table><tr><td valign="top">[a1]</td> <td valign="top">  M. Ajtai,  "$\sum _ { 1 } ^ { 1 }$ - formulae on finite structures"  ''Ann. Pure Appl. Logic'' , '''24'''  (1983)  pp. 1–48</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  M. Ajtai,  J. Komlós,  E. Szemerédi,  "An <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b120/b120370/b12037093.png"/> sorting network"  ''Combinatorica'' , '''3'''  (1983)  pp. 1–19</td></tr><tr><td valign="top">[a3]</td> <td valign="top">  N. Alon,  R. Boppana,  "The monotone circuit complexity of Boolean functions"  ''Combinatorica'' , '''7''' :  1  (1987)  pp. 1–22</td></tr><tr><td valign="top">[a4]</td> <td valign="top">  R. Boppana,  M. Sipser,  "Complexity of finite functions"  J. van Leeuwen (ed.) , ''Handbook of Theoretical Computer Science'' , '''A'''  (1990)  pp. 758–804; Chap.14</td></tr><tr><td valign="top">[a5]</td> <td valign="top">  M. Furst,  J.B. Saxe,  M. Sipser,  "Parity, circuits and the polynomial-time hierarchy"  ''Math. Systems Theory'' , '''17'''  (1984)  pp. 13–27</td></tr><tr><td valign="top">[a6]</td> <td valign="top">  J. Hastad,  "Almost optimal lower bounds for small depth circuits"  S. Micali (ed.) , ''Randomness and Computation'' , ''Adv. Comput. Res.'' , '''5''' , JAI Press  (1989)  pp. 143–170</td></tr><tr><td valign="top">[a7]</td> <td valign="top">  E. Kushilevitz,  N. Nisan,  "Communication complexity" , Cambridge Univ. Press  (1996)</td></tr><tr><td valign="top">[a8]</td> <td valign="top">  O.B. Lupanov,  "A method of circuit synthesis"  ''Izv. V.U.Z. (Radiofizika)'' , '''1''' :  1  (1958)  pp. 120–140  (In Russian)</td></tr><tr><td valign="top">[a9]</td> <td valign="top">  A.A. Razborov,  "Lower bounds on the monotone complexity of some Boolean functions"  ''Soviet Math. Dokl.'' , '''31'''  (1985)  pp. 354–357</td></tr><tr><td valign="top">[a10]</td> <td valign="top">  J.E. Savage,  "Computational work and time on finite machines"  ''J. ACM'' , '''19''' :  4  (1972)  pp. 660–674</td></tr><tr><td valign="top">[a11]</td> <td valign="top">  C.E. Shannon,  "The synthesis of two-terminal switching circuits"  ''Bell Systems Techn. J.'' , '''28''' :  1  (1949)  pp. 59–98</td></tr><tr><td valign="top">[a12]</td> <td valign="top">  A. Schonhage,  V. Strassen,  "Schnelle Multiplikation grosser Zahlen"  ''Computing'' , '''7'''  (1971)  pp. 281–292</td></tr><tr><td valign="top">[a13]</td> <td valign="top">  P.M. Spira,  "On time-hardware complexity of tradeoffs for Boolean functions" , ''Proc. 4th Hawaii Symp. System Sciences'' , North Hollywood&amp;Western Periodicals  (1971)  pp. 525–527</td></tr><tr><td valign="top">[a14]</td> <td valign="top">  I. Wegener,  "The complexity of Boolean functions" , Wiley&amp;Teubner  (1987)</td></tr><tr><td valign="top">[a15]</td> <td valign="top">  Y. Yao,  "Separating the polynomial-time hierarchy by oracles" , ''Proc. 26th Ann. IEEE Symp. Found. Comput. Sci.''  (1985)  pp. 1–10</td></tr></table>

Latest revision as of 17:44, 1 July 2020

An $n$-ary Boolean function $f ( x _ { 1 } , \ldots , x _ { n } )$ is a function from $\{ 0,1 \} ^ { n }$ with values in $\{ 0,1 \}$. The values $0$, $1$ are called Boolean values, or bits, or truth values if they are identified with false and true (cf. also Boolean function). Elements of $\{ 0,1 \} ^ { n }$ are Boolean strings of length $n$ (or bit strings). $B _ { n }$ is the set of all $2 ^ { 2 ^ { n } }$ $n$-ary Boolean functions.

A basis of connectives is any non-empty set $\Omega$ of Boolean functions, not necessarily of the same arity. An $\Omega$-formula for $f ( x _ { 1 } , \ldots , x _ { n } )$ is a formula built from Boolean variables $x _ { 1 } , \ldots , x _ { n }$ using connectives from $\Omega$. A basis $\Omega$ is complete if all Boolean functions are definable by an $\Omega$-formula. Examples of complete bases are: $B _ { 2 }$, the set of all binary Boolean functions, or the DeMorgan basis $\{ 0,1 , \neg , \vee , \wedge \}$.

A more general way to define (equivalently, compute) Boolean functions is by circuits (straight line programs) that are simplified mathematical models of integrated circuits. A Boolean circuit over a basis $\Omega$ for $f \in B _ { n }$ is a sequence $g _ { 1 } , \ldots , g _ { k }$ of functions from $B _ { n }$ such that $g _ { k } = f$ and such that any $g_i$ is either one of the projections $x _ { 1 } , \ldots , x _ { n }$ or is equal to $h ( g _ { j _ { 1 } } , \dots , g _ { j _ { r } } )$, for some $h \in \Omega$ and $j_1 , \ldots , j _ { r } < i$. Drawing directed edges from all such $j _ { 1 } , \dots , j _ { r }$ to $i$, and labelling $i$ by $h$, defines a labelled directed acyclic graph (cf. also Graph, oriented). The size of the circuit is $k$. The maximum length of a path from a vertex corresponding to one of the inputs $x _ { 1 } , \ldots , x _ { n }$ to $g_{k}$ is the depth of the circuit. Note that formulas are circuits whose graphs are trees.

There are three basic ways to measure the complexity of a Boolean function, given a basis $\Omega$:

the minimum size $L _ { \Omega } ( f )$ of an $\Omega$-formula defining $f$,

the minimum size $C _ { \Omega } ( f )$ of a circuit over $\Omega$ defining $f$, and

the minimum depth $D _ { \Omega } ( f )$ of a circuit over $\Omega$ defining $f$. For two complete bases $\Omega$, $\Omega ^ { \prime }$, the measures $C _ { \Omega } ( f )$, $C _ { \Omega ^ { \prime } } ( f )$ and $D _ { \Omega } ( f )$, $D _ { \Omega ^ { \prime } } ( f )$ are proportional to each other, and $L _ { \Omega } ( f )$, $L _ { \Omega ^ { \prime } } ( f )$ are polynomially related. A relation exists between the formula size and the circuit depth (see [a13]): $\operatorname { log } ( L _ { \Omega } ( f ) )$ and $D _ { \Omega } ( f )$ are proportional to each other, provided $\Omega$ is finite.

By estimating the number of circuits of a bounded size, C.E. Shannon [a11] proved (cf. [a14] for an optimal computation) that for almost-all $f \in B _ { n }$, $C _ { B _ { 2 } } ( f ) \geq 2 ^ { n } / n$. On the other hand,

\begin{equation*} C _ { B _ { 2 } } ( f ) \leq \frac { 2 ^ { n } } { n } ( 1 + o ( 1 ) ), \end{equation*}

for all $f \in B _ { n }$, see [a8].

For a formal language $L \subseteq \{ 0,1 \}^*$, let $L_{n}$ be the characteristic function of $L \cap \{ 0,1 \} ^ { n }$. The main open problem in Boolean complexity theory (cf. [a4]) is whether there is a language $L$ accepted by a non-deterministic polynomial-time Turing machine (cf. also Turing machine) such that $C _ { \Omega } ( L _ { n } )$ is not bounded by any polynomial in $n$. The importance of this question stems from the fact that the affirmative answer implies that the computational complexity classes $\mathcal{P}$ and $\cal N P$ are different, as $C _ { B _ { 2 } } ( L _ { n } )$ is bounded by a polynomial for any $L$ decidable in polynomial time (cf. [a10] and also $\cal N P$).

No super-linear lower bounds on $C _ { B _ { 2 } } ( L _ { n } )$ are known for any $L \in \mathcal{N} \mathcal{P}$. However, if additional restrictions are put on the circuits, then strong lower bounds are known. Most notable are two results: any circuit of depth $d \geq 2$ over a DeMorgan-like basis $\{ 0,1 , \neg , \vee , \wedge \}$, allowing $\vee , \wedge$ of unbounded arity, computing the parity function $\oplus _ { n }$ must have size at least $\operatorname { exp } ( \Omega ( n ^ { 1 / d - 1 } ) )$ (see [a1], [a5], [a15], [a6]), and any circuit in the monotone basis $\{ 0,1 , \vee , \wedge \}$ computing whether or not a graph on $n$ vertices contains a clique of size at least $k \leq n ^ { 1 / 4 }$ must have size at least $n ^ { \Omega ( \sqrt { k } ) }$ (see [a9], [a3]).

Interesting upper bounds are also known: a DeMorgan circuit of size for multiplication of two $n$-bit long numbers, [a12] (it is still open (1998) if there are linear size circuits), and a monotone DeMorgan sorting network of simultaneous size and depth $O( \operatorname { log } n )$, see [a2].

Various parts of computational complexity (cf. also Complexity theory) are directly related to lower-bound problems for Boolean functions; for example, communication complexity, cf. [a7].

References

[a1] M. Ajtai, "$\sum _ { 1 } ^ { 1 }$ - formulae on finite structures" Ann. Pure Appl. Logic , 24 (1983) pp. 1–48
[a2] M. Ajtai, J. Komlós, E. Szemerédi, "An sorting network" Combinatorica , 3 (1983) pp. 1–19
[a3] N. Alon, R. Boppana, "The monotone circuit complexity of Boolean functions" Combinatorica , 7 : 1 (1987) pp. 1–22
[a4] R. Boppana, M. Sipser, "Complexity of finite functions" J. van Leeuwen (ed.) , Handbook of Theoretical Computer Science , A (1990) pp. 758–804; Chap.14
[a5] M. Furst, J.B. Saxe, M. Sipser, "Parity, circuits and the polynomial-time hierarchy" Math. Systems Theory , 17 (1984) pp. 13–27
[a6] J. Hastad, "Almost optimal lower bounds for small depth circuits" S. Micali (ed.) , Randomness and Computation , Adv. Comput. Res. , 5 , JAI Press (1989) pp. 143–170
[a7] E. Kushilevitz, N. Nisan, "Communication complexity" , Cambridge Univ. Press (1996)
[a8] O.B. Lupanov, "A method of circuit synthesis" Izv. V.U.Z. (Radiofizika) , 1 : 1 (1958) pp. 120–140 (In Russian)
[a9] A.A. Razborov, "Lower bounds on the monotone complexity of some Boolean functions" Soviet Math. Dokl. , 31 (1985) pp. 354–357
[a10] J.E. Savage, "Computational work and time on finite machines" J. ACM , 19 : 4 (1972) pp. 660–674
[a11] C.E. Shannon, "The synthesis of two-terminal switching circuits" Bell Systems Techn. J. , 28 : 1 (1949) pp. 59–98
[a12] A. Schonhage, V. Strassen, "Schnelle Multiplikation grosser Zahlen" Computing , 7 (1971) pp. 281–292
[a13] P.M. Spira, "On time-hardware complexity of tradeoffs for Boolean functions" , Proc. 4th Hawaii Symp. System Sciences , North Hollywood&Western Periodicals (1971) pp. 525–527
[a14] I. Wegener, "The complexity of Boolean functions" , Wiley&Teubner (1987)
[a15] Y. Yao, "Separating the polynomial-time hierarchy by oracles" , Proc. 26th Ann. IEEE Symp. Found. Comput. Sci. (1985) pp. 1–10
How to Cite This Entry:
Boolean circuit. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Boolean_circuit&oldid=11501
This article was adapted from an original article by J. Krajíček (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article