In this paper, we explore possibilities and difficulties to prove super-quadratic formula size lower bounds from the following aspects. First, we consider recursive Boolean functions and prove their general formula size upper bounds. We also discuss recursive Boolean functions based on exact 2-bit functions. We show that their formula complexity are at least Ω(n2). Hence they can be candidate Boolean functions to prove super-quadratic formula size lower bounds. Next, we consider the reason of the difficulty of resolving the formula complexity of the majority function in contrast with the parity function. In particular, we discuss the structure of an optimal protocol partition for the Karchmer-Wigderson communication game.

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.

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.