Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Space Bounded Computations: Review And New Separation Results

Space Bounded Computations: Review And New Separation Results

File(s)
89-1002.ps (624.54 KB)
89-1002.pdf (1.24 MB)
Permanent Link(s)
https://hdl.handle.net/1813/6802
Collections
Computer Science Technical Reports
Hartmanis, Juris
Author
Hartmanis, Juris
Ranjan, Desh
Abstract

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.

Date Issued
1989-05
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR89-1002
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance