文章基本信息

标题：The Sublogarithmic Alternating Space World
本地全文：下载
作者：Maciej Liskiewicz ; Rüdiger Reischuk
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1995
卷号：1995
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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. Let llog denote the logarithmic function iterated twice, and Sigma_k-Space(S), Pi_k-Space(S) be the complexity classes defined by S-space-bounded ATMs that alternate at most k-1 times and start in an existential, resp. universal state. Our first result shows that for each k > 1 the sets Sigma_k-Space(llog) \ Pi_k-Space(o(log)) and Pi_k-Space(llog) \ Sigma_k-Space(o(log)) are both not empty. This implies that for each S between llog and o(log) the classes Sigma_1-Space(S), Sigma_2-Space(S), Sigma_3-Space(S), form an infinite hierarchy. Furthermore, this separation is extended to space classes defined by ATMs with a nonconstant alternation bound A provided that the product A * S grows sublogarithmically. These lower bounds can also be used to show that basic closure properties do not hold for such classes. We obtain that for any S between llog and o(log) and all k > 1 Sigma_k-Space(S) and Pi_k-Space(S) are not closed under complementation and concatenation. Moreover, Sigma_k-Space(S) is not closed under intersection, and Pi_k-Space(S) is not closed under union. It is also shown that ATMs recognizing bounded languages can always be guaranteed to halt. For the class of Z-bounded languages with Z less than exp S we obtain the equality co-Sigma_k-Space(S) = Pi_k-Space(S) . Finally, for sublogarithmic bounded ATMs we give a separation between the weak and the strong space measure, and prove a logarithmic lower space bound for the recognition of nonregular context-free languages.