On Synchronous Parallel Computations with Independent Probabilistic Choice (Q3347295)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3890730
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On Synchronous Parallel Computations with Independent Probabilistic Choice |
scientific article; zbMATH DE number 3890730 |
Statements
On Synchronous Parallel Computations with Independent Probabilistic Choice (English)
0 references
1984
0 references
probabilistic computation
0 references
randomized algorithm
0 references
parallel speedup
0 references
parallel RAM
0 references
probabilistic algorithms
0 references
probabilistic choice
0 references
synchronous parallel machines
0 references
probabilistic RAM
0 references
perfect matching
0 references
0.8162094950675964
0 references
0.7915211319923401
0 references
0.7859205007553101
0 references
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.
0 references