# Boolean circuit

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

How to Cite This Entry:
Boolean circuit. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Boolean_circuit&oldid=50686
This article was adapted from an original article by J. KrajÃ­Äek (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article