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

The measure d (Ω) of a basis Ω defined below is used to obtain bounds on the circuit depth of
a function in terms of its formula size.

DEFINITION 9.2.1 Given a basis Ω of fan-in r , the constant d (Ω) is defined as follows:
d (Ω) = D Ω f ( 1 )

mux + 1 / log r r + 1
r

Over the standard basis Ω 0 , d (Ω 0 )= 3 . 419.
We now de r i ve a separator theorem for trees . This is a theorem stating that a tree can
be decomposed into two trees of about the same size by removing one edge. We begin by
establishing a property about trees that implies the separator theorem.

LEMMA 9.2.4 Let T be a tree with n internal (non-leaf ) vertices. If the fan-in of every vertex of
T is at most r ,thenforany k , 1 n , T has a vertex v such that the subtree T v rooted at v

has at least k leaves but each of its children T v 1 , T v 2 , ... , T v p , p

≤ k ≤

r ,hasfewerthan k leaves.
Proof Ifthepropertyholdsattheroot,theresultfollows.Ifnot,movetosomesubtreeof
T that has at least k leaves and apply the test recursively. Because a leaf vertex has one leaf
vertex in its subtree, this process terminates on some vertex v at which the property holds.
If it terminates on a leaf vertex, each of its children is an empty tree.

≤

COROLLARY 9.2.1 Let T be a tree of fan-in r with n leaves. Then T has a subtree T v rooted at
avertex v such that T v has at least n/ ( r + 1 ) leaves but at most rn/ ( r + 1 ) .

Proof Let v be the vertex of Lemma 9.2.4 and let k =

n/ ( r + 1 )

.Since T v has at most

r subtrees each containing no more than n/ ( r + 1 ) − ≤ n/ ( r + 1 ) leaves, the result

1

follows.

We now apply this decomposition of trees to develop bounds on formula size.

THEOREM 9.2.2 Let Ω be a complete basis of fan-in r . Any function f : B

n

→B with formula

size L Ω ( f ) ≥ 2 has circuit depth D Ω ( f ) satisfying the following bounds:

d (Ω) log r L Ω ( f )
Proof The lower bound follows because a rooted tree of fan-in r with depth d has at most
r d leaves. Since L Ω ( f ) leaves are needed to compute f with a tree circuit over Ω , the result
follows directly.
The derivation of the upper bound is by induction on formula size. We first establish
the basis for induction: that D Ω ( f )

log r L Ω ( f ) ≤ D Ω ( f ) ≤

d (Ω) log r L Ω ( f ) for L Ω ( f )= 2. To show this,
observe that any function f with L Ω ( f )= 2 depends on at most two variables. There are 16
functions on two variables (which includes the functions on one variable), of which 10 have
the property that both variables affect the output. Each of these 10 functions can be realized
from a circuit for f ( 1 )

≤

mux by adding at most one NOT gate on one input and one NOT on
the output. (See Problem 9.13 .) But, as seen from the discussion preceding Theorem 9.2.1 ,
every complete basis contains a non-monotone function all but one of whose inputs can be
fixed so that the functions computes the NOT of its one remaining input. Thus, a circuit

with depth D Ω f ( 1 ) mux + 2 suffices to realize a function with L Ω ( f )= 2.