Quantcast

Parallel random access machines with powerful instruction sets

Research paper by Walter J. Savitch

Indexed on: 01 Dec '81Published on: 01 Dec '81Published in: Theory of Computing Systems



Abstract

A random access machine model that has capabilities for parallel processing and string manipulation is introduced. It is shown that NP is equal to the class of sets accepted by this model in nondeterministic timeO(logn), that PSPACE is equal to the class of sets accepted by this model in deterministic polynomial time and thatP is equal to the class of sets accepted by a restricted version of this model inO(logn) space. These results generalize to arbitrary time and storage bounds.