Information Technology Reference
In-Depth Information
By Lemma
9.2.1
,since
T
j
has
n
j
leaves, the number of vertices with fan-in of 2 or more
(combiners) is at most
n
j
−
1
)
edges. Since
T
j
may have one controller at the output and at most one per edge,
T
j
has at most 2
n
j
−
1. Also, by Lemma
9.2.1
,
T
j
has at most 2
(
n
j
−
1
controllers.
The number of functions computed by a combiner is at most one of 2
d−
2
since at most
d
X
j
. At most four functions are
computed by a controller since there are at most four functions on one variable. It follows
that the tree
T
j
associated with the input variables in
X
j
containing
n
j
leaves computes
r
X
j
different functions where
r
X
j
satisfies the following upper bound. This bound is the
product of the number of ways that each of the controllers and combiners can compute
functions.
−
2 of its inputs are determined by variables in
X
−
2
(
d−
2
)(
n
j
−
1
)
4
(
2
n
j
−
1
)
2
(
d
+
2
)
n
j
r
X
j
(
f
)
≤
≤
log
2
r
X
j
(
f
)
.Since
L
Ω
(
f
)=
i
=
1
n
j
, the theorem holds for
c
Ω
=
Thus,
(
d
+
2
)
n
j
≥
1
/
(
d
+
2
)
.
Applying Neciporuk's lower bound to the indirect storage access function yields the fol-
lowing result, which demonstrates that the upper bound given in Lemma
9.4.1
for the indirect
storage access function is tight.
LEMMA
9.4.2
Let
2
l
=
n
and
k
=
log
2
(
n/l
)
.Theformulasizeof
f
(
k
,
l
)
k
+
lK
+
L
:
B
→B
ISA
satisfies the following bound:
ISA
=Ω
n
2
L
Ω
f
(
k
,
l
)
log
2
n
Proof
Let
p
=
K
=
2
k
and let
X
j
contain
x
j
.If
X
j
contains other variables, these are
assigned fixed values, which cannot increase
r
X
j
(
f
)
.For0
=
j
.
f
has at least 2
L
restrictions since for each of the 2
L
assignments to
(
y
L−
1
,
...
,
y
0
)
the
restriction of
f
is distinct; that is, if two different such
L
-tuples are supplied as input, they
can be distinguished by some assignment to
x
j
.Thus
r
X
j
(
f
)
≤
j
≤
K
−
1, set
|
a
|
2
L
. Hence, the formula
≥
,
L
Ω
f
(
k
,
l
)
ISA
size of
f
(
k
,
l
)
ISA
c
Ω
KL
, which is proportional to
n
2
/
log
n
.
≥
9.4.2 The Krapchenko Lower Bound
Krapchenko's lower bound applies to the standard basis
Ω
0
or any complete subset, namely
{∧
¬}
{∨
¬}
. It provides a lower bound on formula size that can be slightly larger than
that given by Neciporuk's method.
We apply Krapchenko's method to the parity function
f
(
n
)
,
and
,
,where
f
(
n
)
n
:
B
→B
(
x
1
,
x
2
,
⊕
⊕
...
,
x
n
)=
x
1
⊕
x
n
, to show that its formula size is quadratic in
n
. Since the parity
function on two variables can be expressed by the formula
x
2
⊕···⊕
f
(
2
)
⊕
(
x
1
,
x
2
)=(
x
1
∧
x
2
)
∨
(
x
1
∧
x
2
)
it is straightforward to show that the formula size of
f
(
n
)
⊕
is at most quadratic in
n
.(See
Problem
9.26
.)
Search WWH ::
Custom Search