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

easy.]

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

bounded.1

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.