Parallel computation for well-endowed rings and space-bounded probabilistic machines. (English) Zbl 0598.68043

Borodin, A.; Cook, S.; Pippenger, N.

Inf. Control 58, 113-136 (1983).

We show that a probabilistic Turing acceptor or transducer running within space bound S can be simulated by a time \(S^ 2\) parallel machine and therefore by a space \(S^ 2\) deterministic machine. (Previous simulations ran in space \(S^ 6)\). In order to achieve these simulations, known algorithms are extended for the computation of determinants in small arithmetic parallel time to computations having small Boolean parallel time, and this development is applied to computing the completion of stochastic matrices. The method introduces a generalization of the ring of integers, called well-endowed rings. Such rings possess a very efficient parallel implementation of the basic ring operations \((+,-,\times)\).

MSC:

68Q05	Models of computation (Turing machines, etc.) (MSC2010)
68Q25	Analysis of algorithms and problem complexity
16W99	Associative rings and algebras with additional structure
03D10	Turing machines and related notions
03D15	Complexity of computation (including implicit computational complexity)
15B51	Stochastic matrices

Keywords:

probabilistic Turing acceptor; parallel machine; deterministic machine; simulations; completion of stochastic matrices