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

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


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)
Full Text: DOI