Space Bounded Computations: Review And New Separation Results
In this paper, we review the key results about space bounded complexity classes, discuss the central open problems and outline the relevant proof techniques. We show that, for a slightly modified Turing machine model, the low level deterministic and nondeterministic space bounded complexity classes are different. Furthermore, for this computation model, we show that Savitch and Immerman-Szelepcsenyi theorems do not hold in the range lg lg $n$ to lg $n$. We also discuss some other computation models to bring out and clarify the importance of space constructability and establish some results about these models. We conclude by enumerating a few open problems which arise out of the discussion.