On Parallelism in Turing Machines

Abstract

A model of parallel computation based on a generalization of nondeterminism in Turing machines is introduced. Complexity classes //T(n)-TIME, //L(n)-SPACE, //LOGSPACE, //PTIME, etc. are defined for these machines in a way analogous to T(n)-TIME, L(n)-SPACE, LOGSPACE, PTIME, etc. for deterministic machines. It is shown that, given appropriate honesty conditions, 217z L(n)-SPACE $\subseteq$ //L$(n)^{2}$-TIME T(n)-TIME $\subseteq$ //log T(n)-SPACE //L(n)-SPACE $\subseteq$ exp L(n)-TIME //T(n)-TIME $\subseteq$ T$(n)^{2}$-SPACE thus //EXPTIME = EXPSPACE //PSPACE = EXPTIME //PTIME = PSPACE //LOGSPACE = PTIME ? = LOGSPACE That is, the deterministic hierarchy LOGSPACE $\subseteq$ PTIME $\subseteq$ PSPACE $\subseteq$ EXPTIME $\subseteq \ldots$ shifts by exactly one level when parallelism is introduced. We give a natural characterization of the polynomial time hierarchy of Stockmeyer and Meyer in terms of parallel machines. Analogous space hierarchies are defined and explored, and a generalization of Savitch's result NONDET-L(n)-SPACE $\subseteq$ L$(n)^{2}$-SPACE is given. Parallel finite automata are defined, and it is shown that, although they accept only regular sets, in general, $2^{2^{k}}$ states are necessary and sufficient to simulate a k-state parallel finite automaton deterministically.