The Sublogarithmic Space World
Title | The Sublogarithmic Space World |
Publication Type | Technical Report |
Year of Publication | 1993 |
Authors | Liskiewicz, M., & Reischuk R. |
Other Numbers | 836 |
Abstract | (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. |
URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1993/tr-93-048.pdf |
Bibliographic Notes | ICSI Technical Report TR-93-048 |
Abbreviated Authors | M. Liskiewicz and R. Reischuk |
ICSI Publication Type | Technical Report |