Information Technology Reference
In-Depth Information
[
78
], who showed that the minimum space for the pyramid graph is at least
N/
2
−
1. Meyer
+
2 and established in
general that any graph with minimum space
n
in the black-white game has minimum space at
most
(
n
2
n/
2
auf der Heide [
222
] proved that this minimum space is at most
n
)
/
2
+
1 in the standard game. The latter result is the pebbling analog of Savitch's
theorem (Theorem
8.5.5
).
Loui [
206
]andMeyeraufderHeide[
222
] have shown that the minimum space with the
black-white game is at least one half that for the standard pebble game for balanced trees, a
result extended by Lengauer and Tarjan [
196
] to all trees and then by Klawe [167]. Wilber
[
363
] has exhibited an infinite family of graphs for which the black-white minimum space is
smaller than the minimum space with the standard game by more than a constant factor.
All of the pebble games mentioned above are one-person games; that is, one person plays
the game. A two-person game introduced by Venkateswaran and Tompa [
352
] models parallel
complexity classes. Savage and Vitter [
296
] have also introduced a model of parallel pebbling.
Branching programs have been known as binary decision diagrams for at least 30 years
[
15
], although their importance to CAD was recognized only in the last 10 or 12 years. (See
[
60
]). Branching programs were proposed as a vehicle for studying space-time problems by
Pippenger and first studied by Tompa [
331
], who cites Pippenger for Lemma
10.9.2
. Borodin,
Fischer, Kirkpatrick, Lynch, and Tompa [
55
] derived a lower bound of
ST
=Ω(
n
2
)
to
sort
n
items with decision branching programs. Borodin and Cook [
53
] formulated the same
problem in terms of the general branching programs of Section
10.9
and developed the general
framework used in Theorem
10.11.1
.
Ye s ha [
370
] developed lower bounds on the space-time product with branching prob-
lems for the discrete Fourier transform (see Theorem
10.13.7
) and matrix multiplication over
restricted domains. Abrahamson [
6
](seealso[
4
]) derived the lower bound on
ST
2
in The-
orem
10.13.4
, thereby improving upon the matrix multiplication bound of Yesha. He also
extended the Borodin-Cook model to probabilistic branching programs (see Problem
10.37
)
and derived the lower bound on
ST
for convolution (Theorem
10.13.1
), integer multiplica-
tion (Theorem
10.13.2
), matrix-vector multiplication (Theorem
10.13.3
), and matrix inver-
sion (Theorem
10.13.6
). He also developed a lower bound of
Ω(
n
3
)
on
ST
to compute the
product
PAQ
of three
n
−
n
matrices, where
P
and
Q
are permutation matrices. Abrahamson
has also studied Boolean matrix multiplication in the general branching program model [
5
].
Beame [34] has obtained the result of Theorem
10.13.8
showing that the unique elements
problem requires that
ST
=Ω(
n
2
)
for general branching programs, which implies the lower
bound on sorting stated in Theorem
10.13.9
.
In the comparison-based branching program model, Borodin, Fic
h, Me
yer auf der Heide,
×
Upfal, and Wigderson [
54
]derivethelowerbound
ST
=Ω(
n
3
/
2
√
log
n
)
for the element-
distinctness problem on
n
inputs. For the same computational model, Yao [
369
] improved
this to
ST
=Ω(
n
2
−
(
n
)
)
,where
(
n
)
is a decreasing function of
n
.
Search WWH ::
Custom Search