Sublogarithmic \(\Sigma_ 2\)-space is not closed under complement and other separation results. (English) Zbl 0804.68047

An alternating Turing machine is a two tape non-deterministic Turing machine having a two-way, read-only input tape and a semi-infinite work tape, but whose states have one of two labels – existential or universal – attached. The tree of possible computations of such a machine on a given input assigns to each of its nodes the attributes of accept or reject inductively, as follows.
(i) Each leaf node is an accept node if it corresponds to an accepting configuration in the usual sense.
(ii) Each universal node, all of whose children are accept nodes, is an accept node.
(iii) Each existential node, at least one of whose children is an accept node, is an accept node.
(iv) All other nodes are reject nodes.
An input string is accepted by an alternating Turing machine if the root node of the tree of computations is an accept node. An alternating Turing machine is \(s(n)\) space bounded if on all computations with inputs of length \(n\), no more than \(s(n)\) squares on the work tape are used. The class \(\Sigma_ k\)-SPACE \((s(n))\) is the class of all languages accepted by alternating Turing machines which are \(O(s(n))\) space bounded, which have less than \(k\) alternations between universal and existential states on any accepting computation path, and which have the root state labelled existential. The class \(\Pi_ k\)-SPACE \((s(n))\) is defined similarly, except that the root state is labelled universal. Earlier work cited in this paper established that this alternating space hierarchy collapses for functions \(s(n)>\log (n)\).
The present paper establishes separation results for the case when the function \(s(n)\) is between \(\log(n)\) and \(\log\log(n)\), i.e., \(\log\log(n)\leq s(n)\) and \(\sup_{n\to\infty} s(n)/\log(n)= 0\). Specifically, for such \(s(n)\), \[ \Sigma_ 2\text{-SPACE} (s(n))- \Pi_ 2\text{-SPACE} (s(n))\neq\emptyset \] and \[ \Pi_ 2\text{-SPACE} (s(n))- \Sigma_ 2 \text{-SPACE} (s(n))\neq \emptyset. \] As a corollary one gets \[ \Sigma_ 1\text{-SPACE} (s(n))\subset \Sigma_ 2\text{-SPACE} (s(n))\subset \Sigma_ 3\text{-SPACE} (s(n)) \] and \[ \Pi_ 1\text{- SPACE} (s(n))\subset \Pi_ 2\text{-SPACE} (s(n))\subset \Pi_ 3\text{- SPACE} (s(n)), \] where the inclusions are strict. The arguments involve careful analysis of the computations of alternating Turing machines.
Reviewer: W.Nico (Hayward)


68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
03D15 Complexity of computation (including implicit computational complexity)
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
Full Text: DOI EuDML


[1] 1. P. van EMDE BOAS, Machine models and simulations, I.T.L.I. Prepublication Series for Computation and Complexity Theory, CT-89-02, to appear in: J. van Leeuwen (ed): Handbook of Theoretical Computer Science, North-Holland. Zbl0900.68265 MR1127167 · Zbl 0900.68265
[2] 2. A. K. CHANDRA, D. KOZEN, L. J. STOCKMEYER, Alternation, J. Assoc. Comput. Mach., 1981, 28, pp. 114-133. Zbl0473.68043 MR603186 · Zbl 0473.68043 · doi:10.1145/322234.322243
[3] 3. A. K. CHANDRA and L. J. STOCKMEYER, Alternation, Proc. of 17th I.E.E.E.-F.O.C.S., 1976, pp. 98-108. MR520888
[4] 4. J. H. CHANG, O. H. IBARRA, B. RAVIKUMAR, and L. BERMAN, Some observations concerning alternating Turing machines using small space, Inform. Process. Lett., 1987, 25, pp. 1-9 (Erratum: 27 (1988), 53). Zbl0635.68040 MR896396 · Zbl 0635.68040 · doi:10.1016/0020-0190(87)90085-8
[5] 5. A. R. FREEDMAN and R. E. LADNER, Space bounds for processing counterless inputs, J. Comput. Syst. Sciences, 1975, 11, pp. 118-128. Zbl0307.68036 MR398161 · Zbl 0307.68036 · doi:10.1016/S0022-0000(75)80052-3
[6] 6. V. GEFFERT, Nondeterministic computations in sublogarithmic space and space constructibility, S.I.A.M. J. Comput., 1991, 20, No. 3, pp. 484-498. Zbl0762.68022 MR1094527 · Zbl 0762.68022 · doi:10.1137/0220031
[7] 7. N. IMMERMAN, Nondeterministic space is closed under complement, S.I.A.M. J. Comput., 1988, 17, pp. 935-938. Zbl0668.68056 MR961049 · Zbl 0668.68056 · doi:10.1137/0217058
[8] 8. B. JENNER, B. KIRSIG, and K. LANGE, The logarithmic alternation hierarchy collapses: A\sum L2 = A\pi L2, Information and Computation, 1989, 80, pp. 269-288. Zbl0668.68055 MR984485 · Zbl 0668.68055 · doi:10.1016/0890-5401(89)90012-6
[9] 9. D. KOZEN, On parallelism in Turing machines, 17th I.E.E.E.-F.O.C.S., 1976, pp. 89-97. MR464696
[10] 10. D. RANJAN, R. CHANG, and J. HARTMANIS, Space bounded computations: Review and new separation results, Theoret. Comp. Sci., 1991, 80, pp. 289-302. Zbl0745.68051 MR1117067 · Zbl 0745.68051 · doi:10.1016/0304-3975(91)90391-E
[11] 11. U. SCHONING and K. WAGNER, Collapsing oracle hierarchies, census functions, and logarithmically many queries, Proc. of STACS’88, Springer-Verlag, LNCS 294, 1988, pp. 91-97. Zbl0648.68065 MR935790 · Zbl 0648.68065
[12] 12. J. SEIFERAS, A note on notions of tape constructibility, Technical Report CSD-TR-187, Pennsylvania State University, 1976.
[13] 13. M. SIPSER, Halting space bounded computations, Theoret. Comp. Sci., 1980, 10, pp. 335-338. Zbl0423.68011 MR559693 · Zbl 0423.68011 · doi:10.1016/0304-3975(80)90053-5
[14] 14. R. E. STEARNS, J. HARTMANIS, and P. M. LEWIS II, Hierarchies of memory limited computations, In 1965 I.E.E.E. Conference Record on Switching Circuit Theory and Logical Design, 1965, pp. 179-190. Zbl0229.02033 · Zbl 0229.02033
[15] 15. R. SZELEPCSÉNYI, The method of forced enumeration for nondeterministic automata, Acta Informatica, 1988, 26, pp. 279-284. Zbl0638.68046 MR975334 · Zbl 0638.68046 · doi:10.1007/BF00299636
[16] 16. A. SZEPIETOWSKI, Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space, Information Processing Letters, 1989, 33, pp. 73-78. Zbl0684.68062 MR1031596 · Zbl 0684.68062 · doi:10.1016/0020-0190(89)90158-0
[17] 17. S. TODA, \sum 2-SPACE(n) is closed under complement, J. Comput. Syst. Sciences, 1987, 35, pp. 145-152. Zbl0654.68053 MR910209 · Zbl 0654.68053 · doi:10.1016/0022-0000(87)90009-2
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.