Information Technology Reference
In-Depth Information
Combining this result with Lemma 9.2.3 , we obtain a relationship between the formula
sizes of a function over two different complete bases.
THEOREM 9.2.3 Let Ω a and Ω b be two complete bases with fan-in r a and r b , respectively. There
is a constant α such that the formula size of a function f :
n
B
→B
with respect to these bases
satisfies the following relationship:
[ L Ω b ( f )] α
Proof Let D Ω a ( f ) and D Ω b ( f ) be the depth of f over the bases Ω a and Ω b , respectively.
From Theorem 9.2.2 , log r a L Ω a ( f )
L Ω a ( f )
d b )log r b L Ω b ( f ) .
From Lemma 9.2.3 we know there is a constant d a , b such that if a function f :
D Ω a ( f ) and D Ω b ( f )
n
→B
has depth D Ω b ( f ) over the basis Ω b , then it has depth D Ω a ( f ) over the basis Ω a ,where
B
D Ω a ( f )
d a , b D Ω b ( f )
The constant d a , b
is the depth of the largest-depth basis element of Ω b when realized by a
circuit over Ω a .
Combining these facts, we have that
( r a ) D Ω a ( f )
( r a ) d a , b D Ω b ( f )
L Ω a ( f )
( r a ) d a , b d b )log r b L Ω b ( f )
L Ω b ( f ) d a , b d b )(log r b r a )
Here we have used the identity x log y z = z log y x .
This result can be extended to the monotone basis. (See Problem 9.14 .) We now derive a
relationship between circuit size and depth.
9.3 Lower-Bound Methods for General Circuits
In Chapter 2 upper bounds were derived for a variety of functions, including logical, arith-
metic, shifting, and symmetric functions as well as encoder, decoder, multiplexer, and demul-
tiplexer functions. We also established lower bounds on size and depth of the most complex
Boolean functions on n variables. In this section we present techniques for deriving lower
bounds on circuit size and depth for particular functions when realized by general logic circuits.
9.3.1 Simple Lower Bounds
Afunction f :
n
on n variables is dependent on its i th variable , x i ,ifthereexist
values c 1 , c 2 , ... , c i− 1 , c i + 1 , ... , c n such that
B
→B
f ( c 1 , c 2 , ... , c i− 1 ,0, c i + 1 , ... , c n )
= f ( c 1 , c 2 , ... , c i− 1 ,1, c i + 1 , ... , c n )
This simple property leads to lower bounds on circuit size and depth that result from the
connectivity that a circuit must have to compute a function depending on each of its variables.
Search WWH ::




Custom Search