Space–Time Tradeoffs - Models of Computation: Exploring the Power of Computing - page 464

31

15 30

7 14 29 25

3 6 10 13 18 28 21 24

9 1 2
Figure 10.2 A complete balanced binary tree T ( 4 ) of depth 4 on 16 inputs. At least five
pebbles are needed to pebble it.

12458 16 17 26 27 19 20 22 23

The binary tree of Fig. 10.2 can be pebbled with five pebbles by pebbling the vertices in
the order shown. Five pebbles are needed at the time when vertex 27 is pebbled. After one
pebble is moved to vertex 30, the two outputs of the FFT of Fig. 10.1 to which vertices 15 and
30 are attached can be pebbled. This tree-pebbling strategy can be repeated on all remaining
outputs. It is a general strategy for pebbling complete balanced binary trees.
This pebbling strategy, explained in detail in the next section, demonstrates that an FFT
graph on n = 2 k inputs can be pebbled with no more pebbles than are needed to pebble the
trees with n leaves contained within it, namely, k + 1. In the next section we show that this
is the minimum number of pebbles needed to pebble a complete balanced binary tree on 2 k
leaves. This FFT pebbling strategy for the graph in Fig. 10.1 pebbles each vertex on the third
and fourth levels once, each vertex on the second level twice, and each vertex on the first level
four times. It is clear that inputs must be repebbled if the minimum number of pebbles is used.
This is an example of space-time tradeoff. We shall derive a lower bound on the exchange of
space for time for this problem.
In the next section we also examine the minimum space required to pebble graphs. In the
subsequent section we describe a graph that exhibits an extreme tradeoff. This graph requires
a pebbling time exponential in the size of the graph when the minimum number of pebbles is
used but can be pebbled with one move per vertex if one more pebble is available.
After studying extreme tradeoffs we define a flow property of functions that, if satisfied,
implies a lower bound on the product ( S + 1 ) T (or a related expression) involving the space S
and time T needed to compute such functions. This test is used to show that many standard
algorithms are optimal with respect to their use of space and time.

10.2 Space Lower Bounds
In this section we derive lower bounds on the minimum space S min ( G ) needed to pebble a
graph G for balanced binary trees, pyramids, and FFT graphs, a representative set of graphs.