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 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-Szelepcsenyi theorem do not hold in the range lglg 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.

Last Modified: 29 Oct 2007 13:32:02 EDT by Richard Chang