On the Power of Probabilistic Choice in Synchronous Parallel Computations

Abstract

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 O(log n) time algorithms for connectivity and recognizing bipartite graphs and O(log n) squared time algorithms for testing if a graph has a perfect matching, testing in time O(n) irreducibility of polynomials over finite fields. We characterize the computational complexity of time, space, and processor bounded 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. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1981
Accession Number
ADA109047

Entities

People

  • John Reif

Organizations

  • Harvard University

Tags

Communities of Interest

  • Air Platforms
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Automata
  • Coding
  • Computational Complexity
  • Computations
  • Computer Science
  • Computers
  • Decoding
  • Military Research
  • New York
  • Parallel Computing
  • Parallel Processing
  • Polynomials
  • Probability
  • Simulations
  • Time Intervals
  • Universities

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Graph Algorithms and Convex Optimization.

Technology Areas

  • Space