Information Technology Reference
In-Depth Information
residing under the pebble(s) currently on the DAG. (In the example of Fig.
10.15
,after
placing a pebble on the second vertex we advance a pebble to the third vertex and remove
all other pebbles. Thus, only two vertices are added to the branching program at this step.)
Label the new vertices with the third input to be pebbled. Now repeat the above process
by advancing pebbles as far as possible (in the example, pebbles now reside on the third and
fourth vertices), add one new vertex for each tuple of pebbles on the DAG (four vertices are
added), and connect edges from the previous to the current set of new vertices that conform
to the values assumed at the vertices of the DAG. This process is repeated until all inputs
have been pebbled.
Since the values of operations are always determined by the values under at most
S
P
pebbles, the number of new vertices added in
Q
with the pebbling of each new input vertex
S
P
.Since
T
P
in
G
is most
|A|
input vertices of
G
are pebbled, it follows that
Q
has at most
S
P
+
1
S
P
vertices, from which the conclusion follows.
T
P
|A|
≤
2
T
P
|A|
A branching program can also simulate a computation by a general model of computation,
such as the RAM discussed in Section
3.4
, as we now show. Let the RAM have
Mb
-bit words
of memory and a finite number of
b
-bit words in its CPU. Consider any program for such a
machine. Its
state
is determined by the values in its registers and memory locations. Thus the
RAM has at most
O
(
2
Mb
)
states. Let the
space used by a RAM
be the base-2 logarithm of
the number of its states. Let the RAM execute
T
RAM
steps to read its inputs. We simulate
this computation in the same fashion as with the pebble game. After reading an input variable,
the branching program enters one of at most
O
(
2
Mb
)
vertices corresponding to states of the
RAM. Since the RAM reads inputs on
T
RAM
steps, the branching program also takes
T
RAM
stepsandhasatmost
O
(
T
RAM
2
Mb
)
vertices or uses space of at most
O
(
Mb
+log
T
RAM
)
.
As long as
Mb
is larger than some multiple of
log
T
RAM
, simultaneous lower bounds on the
time to read inputs and space of a branching program for a function computed by the RAM
serve as lower bounds on the same quantities on the RAM. The following lemma summarizes
this discussion.
LEMMA
10.9.4
Given a RAM program that uses space
S
RAM
and
T
RAM
input steps to compute
f
:
m
there is a branching program with space
O
(
S
RAM
+log(
2
T
RAM
))
and time
T
RAM
that computes
f
.Thus,if
2
T
RAM
≤
n
A
→A
2
S
RAM
, simultaneous lower bounds on the space and
time for a branching program for the function imply simultaneous lower bounds on the space and
time on the RAM that differ by at most constant multiplicative factors.
10.10 Straight-Line Versus Branching Programs
In this section we show that some problems can use space and time more efficiently with
branching programs than they can with the pebble game. We demonstrate this for the cyclic
shifting function
f
(
n
)
cyclic
n
introduced in Section
2.5.2
and the merging
problem introduced in Section
6.8
. However, for all of the other problems studied in this
chapter the lower bounds obtained with these two models are the same up to constant mul-
tiplicative factors, except for integer multiplication, where the branching program bound is
smaller by a factor of
log
2
n
.
It is important to note, however, that the superiority of branching programs arises from
the assumption that inputs can be read in a data-dependent fashion, an assumption that is
n
+
log
n
:
B
→B
Search WWH ::
Custom Search