Stockmeyer, Larry; Vishkin, Uzi Simulation of parallell random access machines by circuits. (English) Zbl 0533.68048 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 Cited in 2 ReviewsCited in 52 Documents 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 PDF BibTeX XML Cite \textit{L. Stockmeyer} and \textit{U. Vishkin}, SIAM J. Comput. 13, 409--422 (1984; Zbl 0533.68048) Full Text: DOI OpenURL