Reversal complexity has been studied as a fundamental computational resource along with time and space complexity. We revisit it by contrasting with access complexity which we introduce in this study. First, we study the structure of space bounded reversal and access complexity classes. We characterize the complexity classes L, P and PSPACE in terms of space bounded reversal and access complexity classes. We also show that the difference between polynomial space bounded reversal and access complexity is related with the L versus P problem. Moreover, we introduce a theory of memory access patterns, which is an abstracted structure of the order of memory accesses during a random access computation, and extend the notion of reversal and access complexity for general random access computational models. Then, we give probabilistic analyses of reversal and access complexity for almost all memory access patterns. In particular, we prove that almost all memory access patterns have ω(log n) reversal complexity while all languages in L are computable within O(log n) reversal complexity.

We characterize the gap between time and space complexity of functions by operators and completeness. First, we introduce a new notion of operators for function complexity classes based on recursive function theory and construct an operator which generates FPSPACE from FP. Then, we introduce new function classes composed of functions whose output lengths are bounded by the input length plus some constant. We characterize FP and FPSPACE by using these classes and operators. Finally, we define a new notion of completeness for FPSPACE and show a FPSPACE-complete function.

This paper investigates relationships among deterministic, nondeterministic, and alternating complexity classes defined in the hyperbolic space. We show that (i) every t(n)-time nondeterministic cellular automaton in the hyperbolic space (hyperbolic CA) can be simulated by an O(t4(n))-space deterministic hyperbolic CA, and (ii) every t(n)-space nondeterministic hyperbolic CA can be simulated by an O(t2(n))-time deterministic hyperbolic CA. We also show that nr+-time (non)deterministic hyperbolic CAs are strictly more powerful than nr-time (non)deterministic hyperbolic CAs for any rational constants r 1 and > 0. From the above simulation results and a known separation result, we obtain the following relationships of hyperbolic complexity classes: Ph= NPh = PSPACEh EXPTIMEh= NEXPTIMEh = EXPSPACEh , where Ch is the hyperbolic counterpart of a Euclidean complexity class C. Furthermore, we show that (i) NPh APh unless PSPACE = NEXPTIME, and (ii) APh EXPTIME h.

We study the depth of planar Boolean circuits. We show that planar Boolean circuits of depth D(n) are simulated by on-line Turing machines in space O(D(n)). From this relationship, it is shown that any planar circuit for computing integer multiplication requires linear depth. It is also shown that a planar analogue to the NC-hierarchy is properly separated.