[30] A parallel random access machine (PRAM), also called a ‘concurrent-read and concurrent-write priority PRAM,’ consists of a finite number of processors, each with an infinite local memory and infinite computing power, indexed as P(1), P(2), P(3),..., and an infinite number of shared memory cells c(i), i = 1, 2,..., each capable of holding any integer. Initially, the input is contained in the first n memory cells. The number of processors is polynomial in n. Each step of the computation consists of all processors in parallel executing three phases as follows. Each processor (i) reads from a shared memory cell; (ii) performs any deterministic computation; and (iii) may attempt writing into some shared memory cell.

At each step, every processor is in some state. The actions and the next state of each processor at each step depend on the current state and the value read. In case of a write conflict, that is, more than one processor tries to write to the same memory cell, the processor with the minimum index succeeds in writing. By the end of computing, the shared memory contains the output. Prove that adding (or multiplying) n integers, each

≥ n bits for a fixed  > 0, requires Ω(log n) parallel steps on a PRAM.

Comments. Hint: Cut a random string x into segments x1,...,xn, the segments being used as inputs for the processors. Define an input to be ‘not useful’ if it does not ‘influence’ the final output of the sum (in some precise way). Then show that there is an input xi that is not useful; hence we can compress x using the rest of the inputs and the output. Source: Independently proved by P. Beame [Inform. Comput., 76(1988), 13–28] without using Kolmogorov complexity and by M. Li and Y. Yesha [J. Assoc. Comp. Mach., 36:3(1989), 671–680]. Slightly weaker versions of Exercise 6.10.20 were proved by F. Meyer auf der Heide and A. Wigderson [SIAM J. Comput., 16(1987), 100–107] using a Ramsey theorem, by A. Israeli and S. Moran [private communication, 1985], and by I. Parberry [Ph.D. thesis, 1984, Warwick University]. In the last three proofs, one needs to assume that the integers have arbitrarily

(or exponentially) many bits.