Complexity Classes - Models of Computation: Exploring the Power of Computing - page 376

Problem 8.33 .) Invoking this procedure to write a program for the above problem, we see
that an O ( r 2 ( n )) -depth circuit recognizing L can be written by an O ( r 2 ( n )) -time DTM.

8.14 The Parallel Random-Access Machine Model
ThePRAMmodel,introducedinSection 7.9 , is an abstraction of realistic parallel models that
is sufficiently rich to permit the study of parallel complexity classes. (See Fig. 7.21 , repeated as
Fig. 8.21 .) The PRAM consists of a set of RAM processors with a bounded number of memory
locations and a common memory. The words of the common memory are allowed to be of
unlimited size, but the instructions that the RAM processors can apply to them are restricted.
These processors can perform addition, subtraction, vector comparison operations, conditional
branching, and shifts by fixed amounts. We also allow load and store instructions for moving
words between registers, local memories, and the common memory. These instructions are
sufficiently rich to compute all computable functions.
In the next section we show that the CREW (concurrent read/exclusive write) PRAM that
runs in polynomial time and the log-space uniform circuits characterize the same complexity
classes. We then go on to explore the parallel complexity thesis, which states that sequential
space and parallel time are polynomially related.

8.14.1 Equivalence of the CREW PRAM and Circuits
Because a parallel machine with p processors can provide a speedup of at most a factor of p over
a comparable serial machine (see Theorem 7.4.1 ), problems that are computationally infeasi-
ble on serial machines are computationally infeasible on parallel machines with a reasonable
number of processors. For this reason the study of parallelism is usually limited to feasible
problems, that is, problems that can be solved in serial polynomial time (the class P ). We limit
our attention to such problems here.

Common Memory

RAM RAM RAM

P 1 P 2 P p

Figure 8.21 The PRAM consists of synchronous RAMs accessing a common memory.