On the power of probabilistic choice in synchronous parallel computations

Conference Paper

© by Springer-Verlag Berlin Heidelberg 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.

Full Text

Duke Authors

Cited Authors

  • Reif, JH

Published Date

  • January 1, 1982

Published In

Volume / Issue

  • 140 LNCS /

Start / End Page

  • 442 - 450

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 13 (ISBN-13)

  • 9783540115762

Digital Object Identifier (DOI)

  • 10.1007/BFb0012790

Citation Source

  • Scopus