AN INSIGHT ON PRAM COMPUTATIONAL BOUNDS

We make two contributions to the theory of PRAM computation, focusing on the problem of computing the Boolean OR (to which most basic proble ms can be reconducted). First we critically discuss the ideal PRAM mod el generally adopted to prove parallel time bounds, and introduce the natural definition of simple PRAM. We prove that log(2) n steps are ne eded to compute the OR of n bits in the CREW variant of this model, an d that this bound is tight. This implies that some acclaimed ''surpris ing'' results in PRAM theory depend strictly on the properties of the model, and not on the computed function. As a second contribution we s how how to simplify the most advanced known lower bound proof for comp uting the OR. The new proof scheme does not introduce new results, but is aimed to enhancing the comprehension of this difficult subject We also justify a ''full information'' functioning, generally adopted wit hout discussion. (C) 1997 Elsevier Science B.V.