ON SYNCHRONOUS PARALLEL COMPUTATIONS WITH INDEPENDENT PROBABILISTIC CHOICE.
Publication
, Journal Article
Reif, JH
Published in: SIAM Journal on Computing
January 1, 1984
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. The computational complexity of time, space, and processor bounded probabilistic parallel RAMs is characterized in terms of the computational complexity of probabilistic sequential RAMs. It is shown that parallelism uniformly speeds up time bounded probabilistic sequential RAM computations by nearly a quadratic factor. It is also shown that probabilistic choice can be eliminated from parallel computations by introducing nonuniformity.
Duke Scholars
Published In
SIAM Journal on Computing
DOI
ISSN
0097-5397
Publication Date
January 1, 1984
Volume
13
Issue
1
Start / End Page
46 / 56
Related Subject Headings
- Computation Theory & Mathematics
- 4903 Numerical and computational mathematics
- 4901 Applied mathematics
- 4613 Theory of computation
- 0802 Computation Theory and Mathematics
- 0101 Pure Mathematics
Citation
APA
Chicago
ICMJE
MLA
NLM
Reif, J. H. (1984). ON SYNCHRONOUS PARALLEL COMPUTATIONS WITH INDEPENDENT PROBABILISTIC CHOICE. SIAM Journal on Computing, 13(1), 46–56. https://doi.org/10.1137/0213004
Reif, J. H. “ON SYNCHRONOUS PARALLEL COMPUTATIONS WITH INDEPENDENT PROBABILISTIC CHOICE.” SIAM Journal on Computing 13, no. 1 (January 1, 1984): 46–56. https://doi.org/10.1137/0213004.
Reif JH. ON SYNCHRONOUS PARALLEL COMPUTATIONS WITH INDEPENDENT PROBABILISTIC CHOICE. SIAM Journal on Computing. 1984 Jan 1;13(1):46–56.
Reif, J. H. “ON SYNCHRONOUS PARALLEL COMPUTATIONS WITH INDEPENDENT PROBABILISTIC CHOICE.” SIAM Journal on Computing, vol. 13, no. 1, Jan. 1984, pp. 46–56. Scopus, doi:10.1137/0213004.
Reif JH. ON SYNCHRONOUS PARALLEL COMPUTATIONS WITH INDEPENDENT PROBABILISTIC CHOICE. SIAM Journal on Computing. 1984 Jan 1;13(1):46–56.
Published In
SIAM Journal on Computing
DOI
ISSN
0097-5397
Publication Date
January 1, 1984
Volume
13
Issue
1
Start / End Page
46 / 56
Related Subject Headings
- Computation Theory & Mathematics
- 4903 Numerical and computational mathematics
- 4901 Applied mathematics
- 4613 Theory of computation
- 0802 Computation Theory and Mathematics
- 0101 Pure Mathematics