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