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