Information Technology Reference
In-Depth Information
( 0, 0 )
( 1, 0 )
( 0, 1 )
( 2, 0 )
( 1, 1 )
( 0, 2 )
( 3, 0 )
( 2, 1 )
( 1, 2 )
( 0, 3 )
Figure 10.16 The top portion of a decision branching program to merge two sorted lists. The
pair of integers at a vertex denotes the number of elements removed from the left and right lists
by the program before arriving at the vertex carrying the pair.
realized by a general branching program with space O (log n )+log
and time O ( n ) or a
space-timeproductthatis O ( n log n ) , much smaller than the O ( n 2 ) space-time product that
applies to the pebble game.
|A|
10.11 The Borodin-Cook Lower-Bound Method
In this section we generalize the method of Borodin and Cook [ 53 ] for deriving space-time
lower bounds for branching programs. The conditions under which lower bounds can be
derived are captured by a property of functions called ( φ , λ , μ , ν , τ ) -distinguishability, which
is stronger than the flow property used to derive lower bounds on space-time tradeoffs for
the pebble game. In fact, we show that a function that is ( 1, λ , μ , ν , τ ) -distinguishable is
( α , n , m , p ) -independent for the appropriate values of α , n , m ,and p .
DEFINITION 10.11.1 Let τ : ￿
n
m
be a nondecreasing function. A function f :
A
→F
n
(
φ , λ , μ , ν , τ
)
φ , λ , μ , ν
D⊂A
is
-distinguishable for 0
1 if there is a set
satisfying
n
|D| ≥
φ
|A|
such that for each assignment to a selection of a
λn input variables and each
assignment to a selection of b
τ ( b ) ,thenumberofinput
n -tuples consistent with the values of the a input variables that cause f to assume the given values
for the b outputvariablesisatmost
μm output variables of f , a
n−a−νb .
|A|
The meaning of this property for the function f is suggested by Fig. 10.17 .Forafraction
of φ of the input tuples ( φ = 1 is the normal case), when any a input variables and any b
output variables of f are assigned values, the maximum number of input n -tuples that cause
f to produce these output values is no more than
n−a−νb .Thispropertyisusedbelowto
derive a lower bound on the space-time product for branching programs. We use φ = 1forall
problems considered below except for the unique elements problem.
This theorem also uses a version of the pigeonhole principle. Time is subdivided into
intervals containing equal numbers of input queries. This has the effect of chopping the
|A|
 
Search WWH ::




Custom Search