Space Bounded Computations: Review and New Separation Results

• Authors: D. Ranjan, R. Chang and J. Hartmanis.
• Cite as: Theoretical Computer Science, 80(2):289-302, 1991.
• Previous incarnations:
  • D. Ranjan and J. Hartmanis. "Space Bounded Computations: Review and New Separation Results," in Proceedings of Mathematical Foundations of Computer Science 1989, Springer-Verlag Lecture Notes in Computer Science #379, 49-66, 1989.
  • D. Ranjan and J. Hartmanis. "Space Bounded Computations: Review and New Separation Results," Technical Report TR-1002, Department of Computer Science, Cornell University, April 1989.
• Most readable version: journal version.
• Status: complete.
• Online: final journal submission available as a PDF file (with embedded Type 1 fonts): loglog.pdf.

Abstract:

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.