Information Technology Reference
In-Depth Information
Let
G<
2
n
(
1
−
)
/n
−
2
n
2
.Then
x
=
a
(
G
+
2
n
2
)
≤
a
2
n
(
1
−
)
/n
≤
x
0
/
log
2
x
0
for
x
0
=
a
2
n
(
1
−
/
2
)
when
n
≥
2
[(
1
−
)
/
]log
2
[(
3
e
)
2
(
1
−
/
2
)]
,ascanbeshown
(
x
x
)
1
/a
2
x
0
=
2
2
n
(
1
−/
2
)
.
directly. It follows that
M
(
G
)
≤
≤
n
over the basis
Ω
0
require circuits with
adepthlinearin
n
, we use a similar argument. We first show that for every circuit there is a
tree circuit
(a circuit in which either zero or one edge is directed away from each gate) that
computes the same function and has the same depth. Thus when searching for small-depth
circuits it suffices to look only at tree circuits. We then obtain an upper bound on the number
of tree circuits of depth
d
or less and show that unless
d
is linear in
n
, most Boolean functions
on
n
variables cannot be realized with this depth.
To show that most Boolean functions
f
:
B
→B
LEMMA
2.12.1
Given a circuit for a function
f
:
B
n
m
, a tree circuit can be constructed of
→B
the same depth that computes
f
.
Proof
Convert a circuit to a tree circuit without changing its depth as follows: find a vertex
v
with out-degree 2 or more at maximal distance from an output vertex. Attach a copy of the
tree subcircuit with output vertex
v
to each of the edges directed away from
v
. This reduces
by 1 the number of vertices with out-degree greater than 1 but doesn't change the depth or
function computed. Repeat this process on the new circuit until no vertices of outdegree
greater than 1 remain.
We count the number of tree circuits of depth
d
as follows. First, we determine
T
(
d
)
,the
number of binary, unlabeled, and unoriented trees of depth
d
. (The root has two descendants
as does every other vertex except for leaves which have none. No vertex carries a label and we
count as one tree those trees that differ only by the exchange of the two subtrees at a vertex.)
We then multiply
T
(
d
)
by the number of ways to label the internal vertices with one of at
most three gates and the leaves by at most one of
n
variables or constants to obtain an upper
bound on
N
(
d
)
, the number of distinct tree circuits of depth
d
.Sinceatreeofdepth
d
has at
most 2
d
T
(
d
)
3
2
d
(
n
+
2
)
2
d
.
1 internal vertices and 2
d
−
leaves (see Problem
2.3
),
N
(
d
)
≤
LEMMA
2.12.2
When
d ≥
4
the number
T
(
d
)
of depth-
d
unlabeled, unoriented binary trees
satisfies
T
(
d
)
(
56
)
2
d
−
4
.
Proof
There is one binary tree of depth 0, a tree containing a single vertex, and one of
depth 1. Let
C
(
d
)
be the number of unlabeled, unoriented binary trees of depth
d
or less,
including depth 0. Thus,
C
(
0
)=
1,
T
(
1
)=
1, and
C
(
1
)=
2. This recurrence for
C
(
d
)
follows immediately for
d
≤
≥
1:
C
(
d
)=
C
(
d
−
1
)+
T
(
d
)
(2.16)
We now enumerate the unoriented, unlabeled binary trees of depth
d
+
1. Without loss of
generality, let the left subtree of the root have depth
d
.Thereare
T
(
d
)
such subtrees. The
right subtree can either be of depth
d
−
1 or less (there are
C
(
d
−
1
)
such trees) or of depth
d
. In the first case there are
T
(
d
)
C
(
d
1
)
/
2
pairs of different subtrees (orientation is not counted) and
T
(
d
)
pairs of identical subtrees.
It follows that
−
1
)
trees. In the second, there are
T
(
d
)(
T
(
d
)
−
T
(
d
+
1
)=
T
(
d
)
C
(
d
−
1
)+
T
(
d
)(
T
(
d
)
−
1
)
/
2
+
T
(
d
)
(2.17)
Search WWH ::
Custom Search