Time Bounded Random Access Machines with Parallel Processing

Abstract

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