Information Technology Reference
In-Depth Information
Since at least
c
4
2
k
pebbles reside continuously on both
H
1
(
k
)
during
[
t
d
,
t
e
]
and on
H
2
(
k
)
during
[
t
f
,
t
g
]
and
[
t
f
,
t
g
]
⊆
[
t
d
,
t
e
]
, it follows that
c
4
2
k
+
c
4
2
k
=
c
4
2
k
+
1
reside
continuously on
H
(
k
+
1
)
during
[
t
f
,
t
g
]
.
We are now ready to show the existence of a graph on
n
vertices that requires
ω
(
n/
log
n
)
minimal space.
THEOREM
10.8.1
For integers
n ≥
1
there exists a graph
G
(
n
)
in
G
(
n
,
d
)
that requires mini-
mum space
S
min
(
G
(
n
))
≥
c
5
n/
log
n
for some constant
c
5
>
0
.
2
8
,let
k
be the largest integer such that
n
(
k
)
Proof
For
n
≥
≤
n
;thatis,
n
(
k
)
≤
n<
n
(
k
+
1
)
.Constructthegraph
G
(
n
)
by adding
n
n
(
k
)
vertices and no edges to the graph
H
(
k
)
. An optimal pebbling strategy for
G
(
n
)
pebbles the added vertices one at a time using
one pebble, after which
H
(
k
)
is pebbled. From Lemma
10.8.3
it follows that pebbling
H
(
k
)
requires at least
c
4
2
k
pebbles, since at least this many must reside on the graph at one
time. Since
n
(
k
+
1
)
−
≤
4
n
(
k
)
for
k
≥
8and
c
≥
2, it follows that
n/
4
≤
n
(
k
)
≤
n
.This
implies that 2
k
k
(
c
+
2
)
2
k
(log
2
n
)(
c
+
2
)
2
k
.
≤
n
and
k
≤
log
2
n
and that
n/
4
≤
≤
From this we have 2
k
c
5
n/
log
2
n
,where
c
5
=
1
/
(
4
c
+
8
)
. The conclusion follows by
observing that at least
(
c
4
c
5
)
n/
log
2
n
pebbles are needed to pebble
G
(
n
)
.
≥
10.9 Branching Programs
The general branching program is a serial computational model that permits data-dependent
computation, unlike the pebble game. A branching program is a directed graph consisting of
a single starting vertex and in which vertices are labeled with predicates. Each vertex has one
outgoing edge for each value of its predicate. (See, for example, Figs.
10.11
and
10.12
.) Time
in this model is the number of queries performed, and computations other than queries are
not counted. The space used by a branching program is the base-2 logarithm of the number
of vertices in its graph. Lower bounds on space and input time obtained with the branching
program apply to within constant multiplicative factors to the pebble game and the RAM
model. (See Section
10.9.1
.)
As noted in Section
10.1.1
, since the branching program reads inputs in a less constrained
manner than the straight-line program, it may be possible to solve some problems with branch-
ing programs using less space or time than in the pebble game. As a consequence, space-time
lower bounds for branching programs may be smaller than for the pebble game. Thus, if a
problem is going to be solved with straight-line programs, such as an algebraic circuit, it is bet-
ter to use lower bounds derived with the pebble game unless the branching program gives the
same lower bounds. In particular, branching programs give smaller space-time lower bounds
for integer multiplication and shifting (see Section
10.13.2
) than does the pebble game.
We examine two kinds of branching programs in this section, general branching programs
and decision branching programs.
DEFINITION
10.9.1
A
multigraph
is a graph that may have more than one edge between two
vertices. A
directed multigraph
is a multigraph in which each edge has a direction. A
directed
acyclic multigraph
(DAM) is a multigraph with no directed cycles. A
rooted directed acyclic
multigraph
is a multigraph with a
root vertex
, a vertex with no edges directed into it, and is such
that every vertex can be reached via some path from the root. A
sink vertex
has no edges directed
away from it.
Search WWH ::
Custom Search