Information Technology Reference
In-Depth Information
space and circuit depth stated in Theorem
8.13.3
.StockmeyerandVishkin[
317
]showhow
to simulate efficiently the PRAM with circuits and vice versa. (See also [
161
].) The class
NC
was defined by Cook [
76
]. Theorem
8.15.2
is due to Pippenger [
249
]. The class
P/poly
and
Theorem
8.15.2
are due to Karp and Lipton [
160
].
A large variety of parallel computational models have been developed. (See van Embde
Boas [
350
] and Greenlaw, Hoover, and Ruzzo [
120
].) The PRAM was introduced by Fortune
and Wyllie [
103
]andGoldschlager[
118
,
119
].
Several problems on the efficient simulation of RAMs are from Papadimitriou [
235
].
Search WWH ::
Custom Search