2. Boolean circuits 23
2.3. Basic algorithms. Depth, space and width. We challenge the
reader to study these topics by working on problems. (Solutions are also
provided, of course.) In Problems 2.9–2.16 we introduce some basic algo-
rithms which are used universally throughout this book. The algorithms
are described in terms of uniform (i.e., effectively constructed) sequences of
circuits. In this book we will be satisfied with polynomial-time uniformity;
cf. Theorem 2.3. [This property is intuitive and usually easy to check. An-
other useful notion is logarithmic-space uniformity: the circuits should be
constructed by a Turing machine with work space O(log n) (machines with
limited work space are defined below; see 2.3.3). Most of the circuits we
build satisfy this stronger condition, although the proof might not be so
2.3.1. Depth. In practice (e.g., when implementing circuits in hardware),
size is not the only circuit parameter that counts. Another important pa-
rameter is depth. Roughly, it is the time that is needed to carry out all
assignments in the circuit, if we can do more than one in parallel. In-
terestingly enough, it is also related to the space needed to perform the
computation (see Problems 2.17 and 2.18). In general, there is a trade-off
between size and depth. In our solutions we will be willing to increase the
size of a circuit a little to gain a considerable reduction of the depth (see
e.g., Problem 2.14). As a result, we come up with circuits of polynomial size
and poly-logarithmic depth. (With a certain notion of uniformity, the func-
tions computed by such circuits form the so-called class NC, an interesting
subclass of P.)
More formally, the depth of a Boolean circuit is the maximum number
of gates on any path from the input to the output. The depth is d if and
only if one can arrange the gates into d layers, so that the input bits of any
gate at layer j come from the layers 1,...,j 1. For example, the circuit in
Figure 2.1 has depth 3.
Unless stated explicitly otherwise, we assume that all gates have bounded
fan-in, i.e., the number of input bits. (This is always the case when circuits
are built over a finite basis. Unbounded fan-in can occur, for example, if
one uses OR gates with an arbitrary number of inputs.) We also assume
that the fan-out (the number of times an input or an auxiliary variable is
used) is
If it is necessary to use the variable more times, one may
insert additional “trivial gates” (identity transformations) into the circuit,
at the cost of some increase in size and depth. Note that a formula is a
circuit in which all auxiliary variables have fan-out 1, whereas the fan-out
of the input variables is unbounded.
1This restriction is needed to allow conversion of Boolean circuits into quantum circuits with-
out extra cost (see Section 7). However, it is in no way standard: in most studies in computational
complexity, unbounded fan-out is assumed.
Previous Page Next Page