On Synchronous Parallel Computations with Independent Probabilistic Choice
Sequential probabilistic machines, having the capability of randomly choosing a move at some points of an otherwise deterministic computation, have been introduced by Rabin in 1974. Such a capability leads to considerable improvement to the computational complexity of many difficult problems. In this paper, the use of probabilistic choice in synchronous parallel machines is investigated, together with its effects on the complexity of some combinatorial problems. The basic model of computation is the probabilistic RAM, that is a Random Access Machine (RAM) in which from every configuration I a set NEXT(I) of configurations can be derived. Each I'\(\in\) NEXT(I) can be chosen with equal probability, independently of previous choices. An input string \(\omega\) is accepted by M iff the probability of generating, by random next moves as defined above and starting with input \(\omega\), an accepting computation sequence is greater than 1/2. A probabilistic parallel RAM is a probabilistic RAM with a fork operation which allows the original RAM to create a new clone RAM sharing the same memory. All the RAMs created by fork operate synchronously and their probabilistic choices are independent. A first set of results is obtained by parallelizing known probabilistic sequential algorithms. In particular, an O(log n)\({}^ 2\) time algorithm for testing if a graph of n vertices has a perfect matching and an O(log n) time algorithm for testing the product of \(n\times n\) matrices are given. A greater theoretical interest have the simulation theorems of sect. 4 and sect. 5, which relate the computational complexities of probabilistic sequential and probabilistic parallel computations on RAMs. In particular, Th.5.1 shows that parallelism uniformly speeds up time bounded probabilistic RAM computation by nearly a quadratic factor. Finally, it is shown that probabilistic choice can be eliminated by parallel computations by introducing non uniformity, with some increase of time and processor bounds.
- Depth-first search is inherently sequential
- The probabilistic method yields deterministic parallel algorithms
- Simulating probabilistic by deterministic algebraic computation trees
- P-RAM vs. RP-RAM
- Randomized Gandy-Păun-Rozenberg machines
- scientific article; zbMATH DE number 4201596 (Why is no real title available?)
- scientific article; zbMATH DE number 3936481 (Why is no real title available?)
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- scientific article; zbMATH DE number 4057020 (Why is no real title available?)
- scientific article; zbMATH DE number 4062587 (Why is no real title available?)
- scientific article; zbMATH DE number 1262835 (Why is no real title available?)
- SEARCHING ALGORITHMS IMPLEMENTED ON PROBABILISTIC SYSTOLIC ARRAYS
- Optimal parallel algorithms on planar graphs
This page was built for publication: On Synchronous Parallel Computations with Independent Probabilistic Choice
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3347295)