Some Observations about Relativizations of Space Bounded Computations

• Authors: J. Hartmanis, R. Chang, J. Kadin and S. Mitchell.
• Cite as: In Current Trends in Theoretical Computer Science, G. Rozenberg and A. Salomaa, editors, pp. 423-433, World Scientific, 1993.
• Previous incarnations:
  • In Bulletin of the European Association for Theoretical Computer Science, 35:82--92, June 1988.
  • Technical Report 88-912, Department of Computer Science, Cornell University, May 1988.
• Most readable version: book version.
• Status: complete.
• Online: book version available as a PDF file (with embedded Type 1 fonts): l-book.pdf.

Abstract:

In this column we explore what relativization says about space bounded computations and what recent results about space bounded computations say about relativization.