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 problems can be reconducted). First we critically discuss the ideal PRAM model generally adopted to prove parallel time bounds, and introduce the natural definition of simple PRAM. We prove that log(base 2) n steps are needed to compute the OR of n bits in the CREW variant of this model, and that this bound is tight. This implies that some acclaimed "surprising" results in PRAM theory depend strictly on the properties of the model, and not on the computed function. As a second contribution we show how to simplify the most advanced known lower bound proof for computing 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 without discussion.