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 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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references