Space bounded computations: review and new separation results
Desh Ranjan, Richard Chang, Juris Hartmanis · Theoretical Computer Science · 1991
In this paper we review the key results about space bounded complexity classes, discuss the central open problems and outline the prominent proof techniques. We show that, for a slightly modified Turing machine model, low level deterministic and nondeterministic space bounded complexity classes are different. Furthermore, for this computation model, we show that Savitch's theorem and the Immerman-Szelepcsényi theorem do not hold in the range lg lg n to lg n. We also present other changes in the computation model which bring out and clarify the importance of space constructibility. We conclude by enumerating open problems which arise out of the discussion.