Space Bounded Computations: Review And New Separation Results
Hartmanis, Juris; Ranjan, Desh
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.
computer science; technical report
Previously Published As