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