Separating the Lower Levels of the Sublogarithmic Space Hierarchy
Lists
Only you see this
Abstract
For S(n)≥logn it is well known that the complexity classes NSPACE(S) are closed under complementation. Furthermore, the corresponding alternating space hierarchy collapses to the first level. Till now, it is an open problem if these results hold for space complexity bounds between loglogn and logn, too. In this paper we give some partial answer to this question. We show that for each S between loglogn and logn, Σ2 SPACE(S) and Σ3 SPACE(S) are not closed under complement. This implies the hierarchy Σ1 SPACE(S) ⊂Σ2 SPACE(S) ⊂Σ3 SPACE(S) ⊂Σ4 SPACE(S). We also compare the power of weak and strong sublogarithmic space bounded ATMs.
BibTeX
@inproceedings{liskiewicz1993separating,
author = {Maciej Liskiewicz and Rüdiger Reischuk},
title = {{Separating the Lower Levels of the Sublogarithmic Space Hierarchy}},
booktitle = {STACS},
year = {1993},
doi = {10.1007/3-540-56503-5\_4},
}Loading related content...