Information Technology Reference
In-Depth Information
well as values to each input vertex. Two different interpretations of a DAG may yield different
branching programs. Of course, a DAG is pebbled without regard to the interpretation of ver-
tices: the pebble-game lower bounds use only the fact that vertices can hold one of
|A|
values
and do not depend explicitly on the interpretation given to their operator.
LEMMA
10.9.3
Given a pebbling
P
of an interpreted directed acyclic graph
G
that uses
S
P
pebbles and
T
P
input steps to compute a function with operations over a finite set
A
,thereisa
branching program with space
S
P
log
|A|
+log(
2
T
P
)
and time
T
P
that computes the function
S
P
, simultaneous lower bounds on the space and time for
a branching program for the function imply simultaneous lower bounds on space and time in the
pebble game that differ by at most constant multiplicative factors.
computed by
G
.Thus,if
2
T
P
≤|A|
Q
P
Proof
We construct a branching program
to simulate the pebbling
of a directed acyclic
graph that uses
S
P
pebbles and
T
P
steps. (Figure
10.15
illustrates the construction of such
a branching program.) Initially the branching program has a single vertex, the root, which
is labeled with the first variable to be pebbled according to
. Advance the first pebble as
far as possible. Create a vertex in the branching program for each value of the operation
or input covered by the first pebble. Label these new vertices with the name of the second
input to be pebbled and attach an edge from the root vertex to these new vertices labeled
with the corresponding value for the first input. Advance pebbles as far as possible according
to
P
P
and create one new vertex in the branching program for each different tuple of values
u
=?
0
1
v
=?
v
=?
7
+
0
0,1
1
3
+
6
∗
w
=?
w
=?
0
1
0
1
1
2
4
5
uv
wx
x
=?
x
=?
x
=?
x
=?
0, 1
0
0, 1
0, 1
1
0
1
(a)
(b)
Figure 10.15
A general branching program (b) that simulates the pebbling of a DAG (a) in the
vertexorder1,2,4,3,5,6,7.TheDAGinputvariablesaredenoted
u
,
v
,
w
,and
x
and assume
values in
{
0, 1
}
.
+
denotes
OR
and
∗
denotes
AND
.
Search WWH ::
Custom Search