Information Technology Reference
In-Depth Information
Thus,
T
(
2
)=
2,
C
(
2
)=
4,
T
(
3
)=
7,
C
(
3
)=
11, and
T
(
4
)=
56. From this recurrence
we conclude that
T
(
d
+
1
)
≥
T
2
(
d
)
/
2. We use this fact and the inequality
y
≥
1
/
(
1
−
1
/y
)
,
which holds for
y
≥
2, to show that
(
T
(
d
+
1
)
/T
(
d
)) +
T
(
d
)
/
2
≤
T
(
d
+
1
)
/
2. Since
T
(
d
)
≥
4for
d
≥
3, it follows that
T
(
d
)
/
2
≥
1
/
(
1
−
2
/T
(
d
))
.Replacing
T
(
d
)
/
2bythis
lower bound in the inequality
T
(
d
+
1
)
T
2
(
d
)
/
2, we achieve the desired result by simple
algebraic manipulation. We use this fact below.
Solving the equation (
2.17
)for
C
(
d
≥
−
1
)
,wehave
1
)=
T
(
d
+
1
)
(
T
(
d
)+
1
)
2
C
(
d
−
T
(
d
)
−
(2.18)
Substituting this expression into (
2.16
) yields the following recurrence:
T
(
d
+
2
)
T
(
d
+
1
)
=
T
(
d
+
1
)
T
(
d
)
+
(
T
(
d
+
1
)+
T
(
d
))
2
Since
(
T
(
d
+
1
)
/T
(
d
)) +
T
(
d
)
/
2
≤
T
(
d
+
1
)
/
2, it follows that
T
(
d
+
2
)
satisfies the
inequality
T
(
d
+
2
)
≤
T
2
(
d
+
1
)
when
d
≥
3or
T
(
d
)
≤
T
2
(
d
−
1
)
when
d
≥
5and
T
2
j
(
d
(
56
)
2
d
−
4
d
−
1
≥
4. Thus,
T
(
d
)
≤
−
j
)
for
d
−
j
≥
4or
T
(
d
)
≤
for
d
≥
4.
Combine this with the early upper bound on
N
(
d
)
for the number of tree circuits over
Ω
0
of depth
d
and we have that
N
(
d
)
c
2
d
4, where
c
=
3
((
56
)
1
/
16
)(
n
+
2
)
. (Note that
≤
for
d
≥
c
2
d
+
1
.
But if
c
2
D
0
+
1
is at most 2
2
n
(
1
−δ
)
, then a fraction of at most 2
−δ
2
n
of the Boolean functions on
n
variables have depth
D
0
or less. But this holds when
3
(
56
)
1
/
16
≤
4.) The number of such trees of depth 0 through
d
is at most
N
(
d
+
1
)
≤
D
0
=
n
−
1
−
δ
log
2
e
−
log
2
log
2
4
(
n
+
2
)=
n
−
log log
n
−
O
(
1
)
since
ln(
1
−
x
)
≤−
x
.Notethat
d
≥
4 implies that
n
≥
d
+
1.
THEOREM
2.12.2
For each
0
<δ<
1
afractionofatleast
1
−
2
−δ
2
n
of the Boolean functions
f
:
n
B
→B
have depth complexity
D
Ω
0
(
f
)
that satisfies the following bound when
n
≥
5
:
D
Ω
0
(
f
)
≥
n
−
log log
n
−
O
(
1
)
As the above two theorems demonstrate, most Boolean functions on
n
variables require
circuits whose size and depth are approximately 2
n
/n
and
n
, respectively. Fortunately, most
of the useful Boolean functions are far less complex than these bounds suggest. In fact, we
often encounter functions whose size is polynomial in
n
and whose depth is logarithmic in or
a small polynomial in the logarithm of the size of its input. Functions that are polynomial in
the logarithm of
n
are called
poly-logarithmic
.
2.13
Upper Bounds on Circuit Size
In this section we demonstrate that every Boolean function on
n
variables can be realized with
circuit size and depth that are close to the lower bounds derived in the preceding section.
We begin by stating the obvious upper bounds on size and depth and then proceed to obtain
stronger (that is, smaller) upper bounds on size through the use of refined arguments.
Search WWH ::
Custom Search