Simulation of parallell random access machines by circuits. (English) Zbl 0533.68048

Stockmeyer, Larry; Vishkin, Uzi

SIAM. J. Comput. 13, 409-422 (1984).

The authors provide nontrivial bounds on the time required by a parallel random-access machine to solve certain problems when the machine model allows simultaneous reading from and writing to a common memory. For instance, it is shown that parity, integer multiplication, graph transitive closure, and integer sorting cannot be computed in constant time by such a machine with a polynomial number of processors. In order to provide such bounds, a relationship is established between the parallel machine model and combinational logic circuits in terms of complexity measures. This relationship characterizes the computational power of the parallel machine model.

Reviewer: M.Dal Cin

MSC:

68Q05	Models of computation (Turing machines, etc.) (MSC2010)
68Q25	Analysis of algorithms and problem complexity
94C10	Switching theory, application of Boolean algebra; Boolean functions (MSC2010)

Keywords:

synchronous parallelism; parallel time complexity; circuit complexity; alternating Turing machines; parallel RAM; combinational circuits; complexity measures; computational power