Skip to main content

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