On Synchronous Parallel Computations with Independent Probabilistic Choice

From MaRDI portal
Publication:3347295





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.











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)