The Sublogarithmic Space World

TitleThe Sublogarithmic Space World
Publication TypeTechnical Report
Year of Publication1993
AuthorsLiskiewicz, M., & Reischuk R.
Other Numbers836

(Pages: 42) This paper tries to fully characterize the properties and relationships of space classes defined by Turing machines that use less than logarithmic space -- may they be deterministic, nondeterministic or alternating (DTM, NTM or ATM). We provide several examples of specific languages and show that such machines are unable to accept these languages. The basic proof method is a nontrivial extension of the 1^n ? 1^(n+n!) technique to alternating TMs.

Bibliographic Notes

ICSI Technical Report TR-93-048

Abbreviated Authors

M. Liskiewicz and R. Reischuk

ICSI Publication Type

Technical Report