Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space. (English) Zbl 0684.68062

From the author’s introduction: “It is shown that, for any unbounded fully space constructible function S(n), if \(S(n)=o(\log n)\), then \[ \Pi_ 2-SPACE(S(n))-NSPACE(o(\log n))\neq \emptyset. \] This means that if \(L(n)=o(\log n)\) and L(n)\(\geq S(n)\) for some unbounded fully space constructible S(n), then \(\Pi_ 2\)-SPACE(L(n)) properly contains NSPACE(L(n)), hence the L(n) space-bounded alternating hierarchy does not collapse to the \(\Sigma_ 1\) level. Taking these facts into consideration, a natural question arises: whether for such functions L(n) the inequality \[ \Pi_ 2-SPACE(L(n))\neq NSPACE(L(n)) \] entails that NSPACE(L(n)) is not closed under complement or that \[ DSPACE(L(n))\neq NSPACE(L(n)). \] We discuss this problem and, although we do not give the complete answer, prove some weaker result, viz. that strongly L(n) space- bounded nondeterministic Turing machines are not closed under the so- called independent (from the starting configuration) complement. More precisely, there is a strongly L(n) space-bounded nondeterministic Turing machine M (even with a single-letter input alphabet) such that there is no strongly L(n) space-bounded nondeterministic Turing machine \(M'\) with the property that M started on any input x in any L(\(| x|)\) space-bounded configuration c accepts if and only if \(M'\) started on x in c does not accept. Furthermore, since strongly L(n) space-bounded deterministic Turing machines with a single-letter input alphabet are closed under independent complement, it is shown that there exists an L(n) space-bounded nondeterministic Turing machine (even with a single- letter input alphabet) which cannot be simulated in a similar strong way by any L(n) space-bounded deterministic Turing machine.”


68Q25 Analysis of algorithms and problem complexity
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
03D15 Complexity of computation (including implicit computational complexity)
Full Text: DOI


[1] Alberts, M., Space complexity of alternating Turing machines, (Budach, L., Fundamentals of Computing Theory, FCT’85 Conf., 199 (1985), Springer: Springer Berlin), 1-7, Lecture Notes in Computer Science · Zbl 0574.68040
[2] Chandra, A. K.; Kozen, D. C.; Stockmeyer, L. J., Alternation, J. ACM, 28, 114-133 (1981) · Zbl 0473.68043
[3] Chang, J. H.; Ibarra, O. H.; Ravikumar, B.; Berman, L., Some observations concerning alternating Turing machines using small space, Inform. Process. Lett.. Inform. Process. Lett., Erratum, 27, 53-9 (1988) · Zbl 0635.68041
[4] Freedman, A. R.; Ladner, R. E., Space bounds for processing contentless inputs, J. Comput. System Sci., 11, 118-128 (1975) · Zbl 0307.68036
[5] Freivalds, R., On the worktime of deterministic and nondeterministic Turing machines, Latvijskij Matematiceskij Eshegodnik, 23, 158-165 (1979), (in Russian) · Zbl 0462.68028
[6] Hartmanis, J.; Berman, L., On tape bounds for single-letter alphabet language processing, Theoret. Comput. Sci., 3, 213-224 (1976) · Zbl 0351.68014
[7] Immerman, N., Nondeterministic space is closed under complement, SIAM J. Comput., 17, 935-938 (1988) · Zbl 0668.68056
[8] Kannan, R., Alternation and the power of nondeterminism, Proc. 15th STOC, 344-346 (1983)
[9] Lewis, P. M.; Stearns, R. E.; Hartmanis, J., Memory bounds for the recognition of context-free and context-sensitive languages, IEEE Conf. Rec. on Switching Circuit Theory and Logical Design, 191-202 (1965) · Zbl 0272.68054
[10] Narkiewicz, W., Number Theory (1983), World Scientific: World Scientific Singapore, (translated by S. Kanemitsu) · Zbl 0528.10001
[11] Siper, M., Halting space-bounded computations, Theoret. Comput. Sci., 10, 335-338 (1980) · Zbl 0423.68011
[12] Stearns, R. E.; Hartmanis, J.; Lewis, P. M., Hierarchies of memory limited computations, IEEE Conf. Rec. on Switching Circuit Theory and Logical Design, 179-190 (1965) · Zbl 0229.02033
[13] Szelepcsényi, R., The method of forced enumeration for nondeterministic automata, Acta Informat., 26, 279-284 (1988) · Zbl 0638.68046
[14] Szepietowski, A., Remarks on languages acceptable in log log \(n\) space, Inform. Process. Lett., 27, 201-203 (1988) · Zbl 0652.68055
[15] Szepietowski, A., If deterministic and nondeterministic space complexities are equal for log log \(n\) then they are also equal for log \(n\), (Monien, B.; Cori, R., Proc. 6th Annual Symposium on Theoretical Aspects of Computer Science, STACS ’89, 349 (1989), Springer: Springer Berlin), 251-255, Paderborn, FRG, Lecture Notes in Computer Science · Zbl 0701.68033
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.