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