Information Technology Reference
In-Depth Information
which has degree
√
n
+
n
−|
T
|
.Thu ,aterm
cy
i
1
y
i
2
···
y
i
t
of degree
t
≥
n/
2can
be replaced by a term of degree
√
n
+
n
t
. It follows that the number of polynomials
(and functions) representing functio
ns
whose values coincide with
f
(
n
)
⊕
−
on
U
is the number
of polynomials of degree at most
√
n
+
n/
2. Since there are
j
ways to choose a term
containing
j
variables of
Y
,thereareatmost
N
ways to choose polynomials representing
functions
g
:
U
→{−
}
,where
N
satisfies the following bound:
1, 0, 1
√
n
+(
n/
2
)
n
j
N
≤
j
=
0
2
n
<
(
49
/
50
)
2
n
.(See
Problem
9.7
.) Since each of the
N
terms can be included in a polynomial with coefficient
−
For sufficiently large
n
, the bound to
N
is approximately 0
.
9772
·
1, 0, or 1, there are at most 3
N
distinct polynomials and corresponding functions
g
:
U
→{−
1, 0, 1
}
, which is the desired conclusion.
We summarize these two results in Theorem
9.7.4
.
THEOREM
9.7.4
Every circuit of depth
d
for the parity function
f
(
n
)
has a size exceeding
2
n
1
/
2
d
/
2
/
50
⊕
for sufficiently large
n
.
Proof
Let
U
be the set of
n
-tuples on which
f
(
n
)
and its approximation
f
differ. From
⊕
is at most size
(
C
)
2
n−k
.Nowlet
k
=
n
1
/
2
d
/
2. From Lemma
9.7.7
these
two functions must differ on at least
|
U
|
Lemma
9.7.6
,
50
2
n
input
n
-tuples. Thus, size
(
C
)
2
n−k
50
2
n
from
1
≥
1
which the conclusion follows.
.......................................
Problems
MATHEMATICAL PRELIMINARIES
9.1 Show that the following identity holds for integers
r
and
L
:
L
r
+
1
+
rL
r
+
1
=
L
9.2 Show that a rooted tree of maximal fan-in
r
containing
k
internal vertices has at most
k
(
r
−
1
)+
1 leaves and that a rooted tree with
l
leaves and fan-in
r
has at most
l
−
1
1
)
edges.
9.3 For positive integers
n
1
,
n
2
,
a
1
,and
a
2
, show that the following identity holds:
vertices with fan-in 2 or more and at most 2
(
l
−
n
1
a
1
+
n
2
(
n
1
+
n
2
)
2
(
a
1
+
a
2
)
a
2
≥
9.4 The
external path length
e
(
T
,
L
)
of a binary tree
T
with
L
leaves is the sum of the
lengths of the paths from the root to the leaves. Show that
e
(
T
,
L
)
≥
L
log
2
L
−
2
log
2
L
+
L
.
Search WWH ::
Custom Search