On synchronous parallel computations with independent probabilistic choice.

*(English)*Zbl 0558.68038Sequential 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.

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.

Reviewer: G.Mauri

##### MSC:

68Q25 | Analysis of algorithms and problem complexity |

68W99 | Algorithms in computer science |

68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |

68R10 | Graph theory (including graph drawing) in computer science |