On Probabilistic and Symmetric Parallel Computations,
Abstract
There are many known examples of problems for which there is a probabilistic (sequential) algorithm more efficient than any known deterministic algorithm. This paper considers the question: Are parallel machines made more efficient by allowing processors to take probabilistic choices. We also consider the questions: What is the computational power of parallel machines, if we require transitions of processors to be symmetric? This is motivated by physical constraints to parallel computation such as energy consumption. Also, there appears to be some fundamental relationship between symmetrical and probabilistic computations. To partially answer these questions, we use previous studies of the computational complexity of parallel machines, studies of probabilistic computations, work on symmetric computations, and work relating probabilistic and symmetric computations. We formulate a general thesis for how both the probabilistic and symmetric types of parallel computation relate to other types of computation.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1980
- Accession Number
- ADA095657
Entities
People
- John Reif
Organizations
- Harvard University