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, L(n)-SPACE ⊆ //L(n)2-TIME T(n)-TIME ⊆ //log T(n)-SPACE //L(n)-SPACE ⊆ exp L(n)-TIME //T(n)-TIME ⊆ T(n)2-SPACE thus · · //EXPTIME = EXPSPACE //PSPACE = EXPTIME //PTIME = PSPACE //LOGSPACE = PTIME ? = LOGSPACE That is, the deterministic hierarchy LOGSPACE ⊆ PTIME ⊆ PSPACE ⊆ EXPTIME ⊆ ... 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 Saviten's result NONDET-L(n)-SPACE ⊆ L(n)2-SPACE is given. Parallel finite automata are defined, and it is shown that, although they accept only regular sets, in general 22k states are necessary and sufficient to simulate a k-state parallel finite automaton deterministically.