Information Technology Reference
In-Depth Information
As this pebbling strategy demonstrates, to pebble an output vertex, all
k
pebbles must
move to the bottom of the bipartite graph, thereby removing all pebbles from other vertices
of
H
k
.Let
M
(
k
)
be the number of pebble placements to pebble
H
k
with
k
pebbles. It
follows that to pebble each of the
(
k
+
1
)
outputs of
H
k
with
k
pebbles, we must pebble
each output of
H
k−
1
with
k
−
1 pebbles. Thus,
M
(
k
)
≥
(
k
+
1
)
×
M
(
k
−
1
)
≥
(
k
+
1
)
k
(
k
−
1
)
···
3
·
1
=(
k
+
1
)!
/
2
which provides the desired lower bound.
Let the graph
H
k
have
N
(
k
)
vertices. Then
N
(
1
)=
2,
N
(
2
)=
12 and
N
(
k
)=
N
(
k
−
1
)+
4
k
+
3for
k
≥
3. A straightforward proof by induction shows that
N
(
k
)=
2
k
2
+
5
k
−
6 (see Problem
10.13
).
To s h ow t h a t
M
(
k
)
(
k
+
1
)!
/
2isexponentialin
N
(
k
)=
2
k
2
+
5
k
≥
−
6, note that
1, which is at least
(
p/
2
)
(
p/
2
)
since each of the first
p/
2 terms is at
p
!=
p
·
(
p
−
1
)
·
...
·
3
·
2
·
.
5
[(
k
+
1
)
/
2
]
(
k
+
1
)
/
2
Also, it is easy to see that
N
(
k
)
3
(
k
+
1
)
2
least
p/
2. Thus,
M
(
k
)
≥
≤
1. Since this implies
N
(
k
)
/
3
for
k
≥
≤
(
k
+
1
)
,wehavethat
.
5
(
N
(
k
)
/
3
)
/
2
(
√
N
(
k
)
/
3
)
/
2
M
(
k
)
≥
which is exponential in
N
(
k
)
.
of graphs with fan-in
2 can be obtained by replacing the tree on the left in
H
k
with the pyramid graph of Fig.
10.3
and replacing the bipartite graph on the top with a new graph (see Problem
10.14
). This new
graph exhibits an exponential jump in the time to pebble the graph but at a value of space that
is the fourth root of the number of vertices in
G
k
.
Many vertices in the graph
H
k
have a fan-in
k
. A new family
{
G
k
}
10.4 Grigoriev's Lower-Bound Method
In this section we present a method for developing lower bounds on the exchange of space for
time in the pebble game. These lower bounds are typically of the form
(
S
+
1
)
T
=Ω(
n
2
)
,
where
S
,
T
,and
n
are the space, time, and the size of the input to the problem, and are similar
in spirit to those of Theorem
3.6.1
. Because they assume a less general model of computation
(the pebble game instead of the RAM), lower bounds are easier to derive.
The lower bounds use as a measure the maximum amount of information that can flow
from a subset of the inputs to a subset of the outputs, and are much easier to derive than are
lower bounds on circuit size for the circuit model. Although the results are stated for straight-
line computations, they apply to all “input-output-oblivious” computations by finite-state ma-
chines: computations in which inputs are read and outputs produced at times independent of
the values of the input variables. (See Problem
10.20
.)
10.4.1 Flow Properties of Functions
We start by defining a flow property of functions. (See Fig.
10.5
.) A function
f
:
m
has a large information flow from input variables in
X
1
to output variables in
Y
1
if there are
values for input variables in
X
0
=
X
n
A
→A
−
X
1
such that many different values can be assumed by
Search WWH ::
Custom Search