The authors consider the complexity of computing certain functions in the PRAM (parallel random access machine) model of parallel computing with CREW (concurrent-read-exclusive-write) operation. A PRAM consists of an infinite number of (synchronous) sequential processors having access to a common shared memory. A single memory cell can store an arbitrarily large integer. A function f ( x 1 ,..., x n ) on n inputs is computed by storing x 1 ,..., x n in the first n cells of memory, and the output is printed in the first cell of memory. A Boolean function is called critical if some input exists such that changing any bit of this input changes the output. For example, f ( x 1 ,..., x n ) = x 1 ∨ ... ∨ x n is critical. Cook et al. showed that to compute any critical Boolean function on a CREW PRAM requires at least 0.44 log2 n steps [1]. They also showed that a critical function that can be computed in 0.64 log2n steps exists. Their lower-bound argument is based on a careful analysis of the required communication between processors, so it applies to sequential processors that have infinite computing power. The authors raise the lower bound to 0.5 log2 n and reduce the upper bound to approximately 0.57 log2 n. (The constant is log 2 + &sqrt;2 ( 2 ).)
The new idea of the paper is to show that for computing any Boolean function, a minimal running time PRAM exists that is of a special form, which the authors call predictable. This requires that it be persistent, that is, if any processor changes state at a given time due to change of an input bit, then its state is changed at all subsequent times, and also that processors and memory interact only in certain specified ways. The authors then are able to strengthen the communication lower bound argument of Cook et al.
