Separating the lower levels of the sublogarithmic space hierarchy. (English) Zbl 0799.68092

Enjalbert, Patrice (ed.) et al., STACS 93. 10th annual symposium on theoretical aspects of computer science, Würzburg, Germany, February 25-27, 1993. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 665, 16-27 (1993).
Summary: For \(S(n)\geq\log n\) it is well-known that the complexity classes \(\text{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 \(\log\log n\) and \(\log n\), too. In this paper, we give some partial answer to this question. We show that for each \(S\) between \(\log\log n\) and \(\log n\), \(\Sigma_ 2\text{SPACE}(S)\) and \(\Sigma_ 2\text{SPACE}(S)\) are not closed under complement. This implies the hierarchy \[ \Sigma_ 1\text{SPACE}(S)\subset \Sigma_ 2\text{SPACE}(S)\subset \Sigma_ 3\text{SPACE}(S)\subset \Sigma_ 4\text{SPACE}(S). \] We also compare the power of weak and strong sublogarithmic space bounded ATMs.
For the entire collection see [Zbl 0866.00060].


68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)