Information Technology Reference
In-Depth Information
10.40 Complete the proof of Theorem
10.13.4
by showing that two
n
n
matrices can
be multiplied with a hybrid algorithm that combines table lookup with the standard
matrix multiplication algorithm on
k
×
×
k
blocks to achieve space and time satisfying
ST
2
=
O
(
n
3
log
|R|
)
10.41 Show that the RAM program described in Fig.
10.22
can be converted to a branching
program of space
O
(
S
)
and time
O
(
T
)
.
Chapter Notes
The first formal study of space-time tradeoffs was made by Cobham [
73
]. He considered
computations on one-tape Turing machines using as a space measure the logarithm of the
number of configurations, and obtained quadratic lower bounds on the space-time product to
recognize strings representing palindromes and perfect squares.
The pebble-game model was implicitly used by Paterson and Hewitt [
239
]tostudypro-
gram schemas, uninterpreted graphs representing programs. They derived the space lower
bound of Lemma
10.2.1
, thereby demonstrating that recursive programs are more power-
ful than nonrecursive ones. Cook [
75
,
79
] asked how much space (how many pebbles) was
needed to execute a program schema with
n
vertices and obtained the result for pyramids of
Lemma
10.2.2
, showing that the minimum space is at least
Ω(
√
n
)
for some schemas. The
minimum-space question was answered by Hopcroft, Paul, and Valiant [
140
], who proved
Theorem
10.7.1
, and Paul, Tarjan, and Celoni [
246
], who obtained Theorem
10.8.1
.The
pebble model first formally appeared in [
140
]. Gilbert, Lengauer, and Tarjan [
115
]andLoui
[
205
] have shown that the languages associated with minimal pebblings of DAGs (described
at the end of Section
10.2
)are
PSPACE
-complete.
In addition to studying the minimum space needed for a computation, researchers also
examined tradeoffs between space and time. Paterson and Hewitt [
239
]studiedtheconversion
of a linear recursive program schema into a non-recursive one and demonstrated that the time
needed satisfies
T
=Ω(
n
1
+
1
/
(
S−
1
)
)
for
S
≥
2. (See Chandra [
66
] and Swamy and Savage
[
321
]) for more details on this problem.)
A number of other authors have identified graphs exhibiting non-trivial exchanges of space
for time. Pippenger [
254
] gave a graph on
n
vertices for which
T
=Ω(
n
log log
n
)
when
S
=
O
(
n/
log
n
)
,andSavageandSwamy[
293
] demonstrated that the FFT graph requires
S
and
T
satisfying
ST
=Θ(
n
2
)
. (This is the first tradeoff result for a natural algorithm. Their
upperboundisgiveninTheorem
10.5.5
.) Later Tompa [
333
] and Reischuk [279] exhibited
graphs requiring
T
=Ω(
n
log
n
)
and
T
=Ω(
n
log
t
n
)
for any integer
t
, respectively, when
S
=Θ(
n/
log
n
)
.
Paul and Tarjan [
245
], Lingas [201], and van Emde Boas and van Leeuwen [
349
]gave
graphs with
T
increasing from
O
(
n
)
to
T
=
2
Ω(
n
1
/
2
)
,
T
=
2
Ω(
n
1
/
3
)
,and
T
=
2
Ω(
n
1
/
4
log
n
)
,
respectively, when
S
drops by a constant amount from
S
=
O
(
n
1
/
2
)
,
S
=
O
(
n
1
/
3
)
and
S
=
O
(
n
1
/
4
)
, respectively. Theorem
10.3.1
is from [
349
], as is Problem
10.14
.Ca -
son and Savage [
64
] took a different tack and exhibited graphs for which
T
is superlinear,
namely,
T
=
2
Ω(log
n
log log
n
)
≤
O
(
n
1
/
2
/
log
n
)
. References to the worst-case exchange of space for time are given in Sec-
tion
10.6
.
over a range of values of
S
,namely,
Ω(log
n
)
≤
S
Search WWH ::
Custom Search