On the power of probabilistic choice in synchronous parallel computations
Publication
, Conference
Reif, JH
Published in: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
January 1, 1982
This paper introduces probabilistic choice to synchronous parallel machine models; in particular parallel RAMs. The power of probabilistic choice in parallel computations is illustrated by parallelizing some known probabilistic sequential algorithms. We characterize the computational complexity of time, space, and processor bounded probabilistic prallel RAMs in terms of the computational complexity of probabilistic sequential RAMs. We show that parallelism uniformly speeds up time bounded probabilistic sequential RAM computations by nearly a quadratic factor. We also show that probabilistic choice can be eliminated from parallel computations by introducing nonuniformity.
Duke Scholars
Published In
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
DOI
EISSN
1611-3349
ISSN
0302-9743
Publication Date
January 1, 1982
Volume
140 LNCS
Start / End Page
442 / 450
Related Subject Headings
- Artificial Intelligence & Image Processing
- 46 Information and computing sciences
Citation
APA
Chicago
ICMJE
MLA
NLM
Reif, J. H. (1982). On the power of probabilistic choice in synchronous parallel computations. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 140 LNCS, pp. 442–450). https://doi.org/10.1007/BFb0012790
Reif, J. H. “On the power of probabilistic choice in synchronous parallel computations.” In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 140 LNCS:442–50, 1982. https://doi.org/10.1007/BFb0012790.
Reif JH. On the power of probabilistic choice in synchronous parallel computations. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1982. p. 442–50.
Reif, J. H. “On the power of probabilistic choice in synchronous parallel computations.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 140 LNCS, 1982, pp. 442–50. Scopus, doi:10.1007/BFb0012790.
Reif JH. On the power of probabilistic choice in synchronous parallel computations. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1982. p. 442–450.
Published In
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
DOI
EISSN
1611-3349
ISSN
0302-9743
Publication Date
January 1, 1982
Volume
140 LNCS
Start / End Page
442 / 450
Related Subject Headings
- Artificial Intelligence & Image Processing
- 46 Information and computing sciences