Information Technology Reference
In-Depth Information
(a) (b)
Figure 10.18
The transformation of a
T
-step branching program into a branching program
with
σ
=
(
T
+
1
)
/
(
a
+
1
)
layers in which each layer consists of a forest of trees.
query
has all of its output edges directed to a single successor vertex. Also, move all tree
outputs down to the leaves of these trees (which are also roots of trees in the next stage). Let
P
∗
be the new branching program. Since the roots of trees in each stage are vertices in the
original branching program, there are no more than 2
S
trees.
Let
x
be one of the input
n
-tuples among the fraction
φ
for which
(
φ
,
λ
,
μ
,
ν
,
τ
)
-dis-
tinguishability is defined. The path through
P
∗
defined by
x
passes through
σ
stages.
Therefore, there must be at least one stage containing a tree path that produces at least
b
=
m/σ
outputs (a
rich path
). (As shown in the last paragraph of this proof,
b
≤
μm
when
λ
≤
μ
for sufficiently large
n
.) Thus,
x
defines at least one rich path. Let
a
≤
τ
(
b
)
.
n
m
Because the function
f
:
A
→F
is
(
φ
,
λ
,
μ
,
ν
,
τ
)
-distinguishable, each rich path can be
νb
inputs. (This number is smaller if more than
b
outputs
are produced.) Since there are at most 2
S
n
−
a
−
|A|
associated with at most
a
paths through each tree,
|A|
trees and at most
there are at most 2
S
a
rich paths. Furthermore, two distinct rich paths (either the inputs
queried or outputs produced are different) are associated with disjoint sets of input
n
-tuples.
Thus, 2
S
|A|
n−a−νb
cannot be less than the number of input
n
-tuples in question,
from which the following inequality holds:
a
|A|
|A|
n
2
S
a
n−a−νb
φ
|A|
≤
|A|
|A|
We conclude that
+
1
S
≥
νb
log
2
|A|
2
log
2
φ
We rep l ace
b
=
by its lower bound
ma/
2
T
.Since
τ
(
b
)
is a nondecreasing function,
the value of
a
satisfying
a
m/σ
≤
τ
(
b
)
is not increased by replacing
b
by
ma/
2
T
.Thus,
S
≥
ν
(
ma/
2
T
)log
2
|A|
λn
.
We show there exists an integer
n
α
such that for
n>n
α
the condition
b
+log
2
φ
, subject to
a
≤
τ
(
ma/
2
T
)
and
a
≤
≤
μm
is met by the condition
λ
≤
μ
.Notethat
b
=
m/σ
is a nondecreasing function of
a
and a nonincreasing function of
T
since
σ
=
(
T
+
1
)
/
(
a
+
1
)
is a nonincreasing
Search WWH ::
Custom Search