Information Technology Reference
In-Depth Information
function of
a
and a nondecreasing function of
T
.Thu ,
b
is largest when
T
=
n
and
a
=
λn
. It follows that
b
is largest when
σ
=
(
n
+
1
)
/
(
λn
+
1
)
≤
1
/λ
.If
n>
(
1
/λ
−
2
)
/
(
1
−
λ
(
1
/λ
−
1
))
,then
(
n
+
1
)
/
(
λn
+
1
)
>
1
/λ
−
1, which implies that
(
n
+
1
)
/
(
λn
+
1
)
=
1
/λ
. In other words, when
n>
(
1
/λ
−
2
)
/
(
1
−
λ
(
1
/λ
−
1
))
,
b
assumes a value of at most
m/
1
/λ
≤
λm
.
COROLLARY
10.11.1
Let
f
:
A
n
m
be
(
φ
,
λ
,
μ
,
ν
,
τ
)
-distinguishable for
λ
→F
≤
μ
and
τ
(
b
)=
n
. Then the space
S
and time
T
required by any normal-form branching program
P
that
computes
f
must satisfy
mnλν
2
ST
≥
log
2
|A|
+log
2
φ
when
T
1
))
.
Proof
The result follows from the observation that the maximum value of
a
in Theo-
rem
10.11.1
is
λn
.
≥
n
and
n>
(
1
/λ
−
2
)
/
(
1
−
λ
(
1
/λ
−
The connection between
(
α
,
n
,
m
,
p
)
-independence and
(
1,
λ
,
μ
,
ν
,
τ
)
-distinguishability
is given below.
LEMMA
10.11.1
If
f
:
A
m
is
(
1,
λ
,
μ
,
ν
,
τ
)
-distinguishable, it is
(
1
/ν
,
n
,
m
,
p
)
-
independent for
p
=min(
λn
,
τ
(
μm
)) +
μm
.
Proof
Consider sets of
a
input and
b
output variables to
f
such that
a
n
→F
≤
τ
(
b
)
,
a
≤
λn
,and
τ
∗
,where
τ
∗
=min(
λn
,
τ
(
μm
))
since
τ
(
x
)
is nondecreasing
in
x
. For any particular assignment to the
a
inputs, the input
n
-tuples that agree with this
assignment but lead to different values for the
b
outputs must be disjoint, as suggested in
Fig.
10.19
. We show that for some assignment of values to the
a
inputs, the number of
values assumed by the
b
outputsismorethan
b
≤
μm
,orequivalently
a
≤
|A|
b/α−
1
for
α
=
1
/ν
. Suppose not. Then
|A|
n−a−νb
|A|
νb−
1
input tuples for each assignment to the
a
inputs, or a
there are at most
n
input tuples, we have a contradiction.
Therefore,
f
is
(
1
/ν
,
n
,
m
,
p
)
-independent for
p
=
τ
∗
+
μm
.
n−
|A|
1
input tuples. Since
f
has
|A|
total of at most
The following lemma makes it easier to derive space-time lower bounds for branching
programs. It uses the notions of subfunction (see Definition
2.4.2
) and reduction (see Defini-
tion
2.4.1
).
021
312
223
414
124
Figure 10.19
On the left are the points in the domain of
f
that map to individual output
b
-tuples when the values of
a
input variables are fixed.
Search WWH ::
Custom Search