Tape Reversal and Parallel Time

Candidate: Chen,Jianer

Abstract

Recent research has shown an intimate relationship between reversal complexity on multitape Turing machines and parallel computation time. In this dissertation, we systematically study the structural properties of these two important complexity measures and the relationship between them. We develop some basic techniques necessary for establishing analogues of well-known theorems on space and time complexity. We give a linear simulation of deterministic space by deterministic reversal on multitape Turing machines and the first known tape reduction theorem for reversal complexity. As applications of the tape reduction theorem, we prove a hierarchy theorem and show the existence of complete languages for reversal complexity. The relationship between reversal and tape is also discussed. We show that with respect to reversal complexity there is an intrinsic difference between 1-tape and 2-tape Turing machines. More precisely, we show that in deterministic case, 2-tape Turing machines can simulate k-tape Turing machines with only a polynomial (quadratic) increase of reversals while 1-tape Turing machines do not have such a property if $P \not= PSPACE;$ in nondeterministic case, reversal complexity is too powerful to be a complexity measure on 2-tape Turing machines but on 1-tape Turing machines it is a reasonable complexity measure which is linearly related to the space complexity. For parallel computation, we introduce the concepts of deterministic, nondeterministic and oracle circuits in a very natural way. Based on our model of oracle circuits, we build up a log-depth hierarchy in parallel computation, and show that our hierarchy corresponds exactly to the well-known NC hierarchy. From this point of view, some structural properties of the NC hierarchy are discussed. Log-depth many-one reducibility and log-depth Turing reducibility are discussed. Several new complete languages for the class of deterministic log-space languages are presented. Finally, we give the detail proofs of the polynomial relationship between reversal complexity on multitape Turing machines and parallel time complexity on uniform circuits. (Some of these proofs have been outlined by Pippenger.)