Circuit Complexity - Models of Computation: Exploring the Power of Computing - page 396

function at the i th gate. Note that i φ i is the number of edges directed away from gates
in the original circuit. But since each edge directed away from a gate is an edge directed into
a gate, this number is at most rC Ω ( f ) since each gate has fan-in at most r .
It follows that the smallest number of gates in a circuit with fan-out s for f satisfies the
following bound:

φ i −

C Ω ( f ) 1 + l (Ω)( r

C Ω ( f )

−

1 ) 1

C s , Ω ( f ) ≤ C Ω ( f )+ l (Ω) ≤

s − s −

1 1

i = 1

which demonstrates that circuit size with a fan-out s ≥ 2 differs from the unbounded fan-

out circuit size by at most a constant factor.

With the construction employed in Theorem 9.2.1 , an upper bound can be stated on
D s , Ω ( f ) that is proportional to the product of D Ω ( f ) and log C Ω ( f ) . (See Problem 9.12 .)
The upper bound stated above on C s , Ω ( f ) can be achieved by a circuit that also achieves an
upper bound on D s , Ω ( f ) that is proportional to D Ω ( f ) and log r s [ 138 ].

9.2.2 Effect of Basis Change on Circuit Size and Depth
We now consider the effect of a change in basis on circuit size and depth. In the next section
we examine the relationship between formula size and depth, from which we deduce the effect
of a basis change on formula size.

LEMMA 9.2.3 Given two complete bases, Ω a and Ω b ,andafunction f : B

m ,thecircuit
size and depth of f in these two bases differ by at most constant multiplicative factors.
Proof Because each basis is complete, every function in Ω a can be computed by a fixed
number of gates in Ω b , and vice versa. Given a circuit with basis Ω a , a circuit with basis
Ω b can be constructed by replacing each gate from Ω a by a fixed number of gates from
Ω b . This has the effect of increasing the circuit size by at most a constant factor. It follows
that C Ω a ( f )=Θ( C Ω b ( f )) . Since this construction also increases the depth by at most a
constant factor, it follows that D Ω a ( f )=Θ( D Ω b ( f )) .

n

→B

9.2.3 Formula Size Versus Circuit Depth
A logarithmic relationship exists between the formula size and circuit depth of a function, as
we now show. If a formula is represented by a balanced tree, this result follows from the fact
that the circuit fan-in is bounded. However, since we cannot guarantee that each formula
corresponds to a balanced tree, we must find a way to balance an unbalanced tree.
To balance a formula and provide a bound on the circuit depth of a function in terms of
formula size, we make use of the multiplexer function f ( n )

2 n + n

mux :

B →B

on three inputs

f ( 1 )

mux ( a , y 1 , y 0 ) . Here the value of a determines which of the two other values is returned.

mux ( a , y 1 , y 0 )= y 0

a = 0

f ( 1 )

y 1 a = 1

This function can be realized by

f ( 1 )

mux ( a , y 1 , y 0 )=( a

∧ y 0 ) ∨ ( a ∧ y 1 )