Time Bounded Random Access Machines with Parallel Processing
Walter J. Savitch, Michael J. Stimson · Journal of the ACM · 1979
The RAM model of Cook and Reckhow ~s extended to allow parallel recursive calls and the elementary theory of such machines is developed The uniform cost criterion is used The results include proofs of (!) the eqmvalence of nondetermmtsUc and determm~sttc polynomml Ume for such parallel machines and (2) the eqmvalence of polynomml tmae on such parallel machines and polynomml space on ordinary nonparallel RAM's Also included are results showing that parallelism appears to be stnctly more powerful than nondetermmlsm rg~,t WOgDS ANt~ Pm~AsEs parallelism, nondetermm~sm, random access machine, tune, storage CR CATEGORIES 5 23, 5.25, 5 26 IntroductionA machine model called a parallel random access machine (PRAM) is introduced.The model is obtained by extending the RAM model of Cook and Reckhow [3] to allow parallel recursive calls.These PRAM's are then used to develop a theory for the time complexity of parallel algorithms.In this paper the uniform cost criterion [3] is used; that is, in computing running times, we charge a constant amount of time for each memory access.The only arithmetic operations allowed m the model are addition and subtraction.This paper is organized as follows.In Sections 2 and 3 the PRAM model is formally defined and a high level programming language for PRAM's is discussed.In Section 4 it is shown that deterministic and nondeterministic polynomial time are equivalent for PRAM's.The proof is based on the well-known observation that nondeterminism can be viewed as a special form of parallehsm, and so nondeterminism can be simulated by parallelism.Since a nondetermlnistic parallel machine may have many processors making simultaneous, independent nondetermimstic moves, the simulation is, however, more complicated than that of simulating a nondeterministic serial machine by a deterministic parallel machine.Section 4 also includes results showing that parallelism appears to be more powerful than nondeterminism.More specifically, it is shown that, provided they are Permission to copy wRhout fee all or part of this material is granted provided that the copies are not made or d,stnbuted for direct commercial advantage, the ACM copyright notice and the title of the pubhcatlon and ~ts date appear, and notice ~s given that copymg ~s by permtss~on of the AssooaUon for Computing Machinery To copy otherwise, or to repubhsh, requires a fee and/or specific permtsslon Most of these results were presented m [12] and [13] This research was supported, m part, by the National Soence Foundation under Grant MCS-74-02338.