×

The alternation hierarchy for sublogarithmic space is infinite. (English) Zbl 0796.68099

The alternation hierarchy for Turing machines with a space bound between loglog and log is infinite. That applies to all common concepts, especially a) to two-way machines with weak space-bounds, b) to two-way machines with strong space-bounds, and c) to one-way machines with weak space-bounds. In all of these cases the \(\Sigma_ k\)- and \(\Pi_ k\)- classes are not comparable for \(k\geq 2\). Furthermore, the \(\Sigma_ k\)- classes are not closed under intersection and the \(\Pi_ k\)-classes are not closed under union. Thus these classes are not closed under complementation. The hierarchy results also apply to classes determined by an alternation depth which is a function depending on the input rather than on a constant.

MSC:

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

References:

[1] L. Babai andS. Moran, Arthur-Merlin games: a randomized proof-system, and a hierarchy of complexity classes.J. Comput. System. Sci. 36 (1988), 254-276. · Zbl 0652.03029 · doi:10.1016/0022-0000(88)90028-1
[2] J. L. Balcázar, J. Díaz andJ. Gabarró,Structural Complexity I. Springer-Verlag, Berlin, Heidelberg, New York, London, Paris, Tokyo, 1988. · Zbl 0638.68040
[3] E. Börger,Computability, Complexity, Logic. North-Holland, Amsterdam, New York, Oxford, Tokyo, 1989.
[4] B. von Braunmühl, Alternationshierarchien von Turingmaschinen mit kleinem Speicher. Informatik Berichte 83, Institut für Informatik, Universität Bonn, 1991.
[5] J. H. Chang, O. H. Ibarra, B. Ravikumar, andL. Berman Some observations concerning Turing machines using small space.Inform. Process. Lett. 25 (1987), 1-9. Erratum,Inform. Process. Lett. 25 (1988) 53. · Zbl 0635.68040 · doi:10.1016/0020-0190(87)90085-8
[6] P. van Emde Boas, Machine models and simulations. InHandbook of Theoretical Computer Science, Volume A, Algorithms and Complexity ed.J. van Leeuwen, 1-66. Elsevier, Amsterdam, New York, Oxford, Tokyo, 1990. · Zbl 0900.68265
[7] R. Freivalds, On time complexity of deterministic and nondeterministic Turing machines.Latvijski Mathemati?eskij Eshegodnik 23 (1979), 158-165. In Russian. · Zbl 0462.68028
[8] M. R. Garey andD. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Fransisco, 1979. · Zbl 0411.68039
[9] V. Geffert, Nondeterministic computations in sublogarithmic space and space constructibility. InProc. 17 ICALP, Lecture Notes in Computer Science 443, 1990 111-124. · Zbl 0765.68035
[10] V. Geffert, Tally versions of the Savitch and the Immerman-Szelepcsényi theorems for sublogarithmic space.SIAM J. Comput. 22 (1993), 102-113. · Zbl 0766.68039 · doi:10.1137/0222009
[11] L. A. Hemachandra, The strong exponential hierarchy collapses. InProc. Nineteenth Ann. ACM Symp. Theor. Comput, 1987, 110-122.
[12] N. Immerman, NSPACE is closed under complement.SIAM J. Comput. 17 (1988), 935-938. · Zbl 0668.68056 · doi:10.1137/0217058
[13] A. Ito, K. Inoue, andI. Takanami, A note on alternating Turing machines using small space.The Transactions of the IEICE E 70 no. 10 (1987), 990-996.
[14] K. Iwama, ASPACE(o(log log)) is regular. Research report KSU/ICS Kyoto Sangyo University, Kyoto, 603, Japan, 1986. See alsoSIAM J. Comput 22 (1993), 136-146. · Zbl 0767.68039
[15] M. Kutylowski, M. Li?kiewicz, andK. Lory?, Reversal complexity classes for alternating Turing machines.SIAM J. Comput. 19 (1990), 207-221. · Zbl 0692.68035 · doi:10.1137/0219014
[16] P. M. Lewis, R. E. Stearns, and J. Hartmanis, Memory bounds for recognition of context-free and context-sensitive languages. InIEEE. Conf. Switch. Circuit Theory and Logic Design, 1965, 191-202. · Zbl 0272.68054
[17] M. Li?kiewicz and R. Reischuk, Separating the lower levels of the sublogarithmic space hierarchy. InProc. 10.STACS, Lecture Notes in Computer Science 665, 1993a, 16-28. · Zbl 0799.68092
[18] M. Li?kiewicz and R. Reischuk, The sublogarithmic space hierarchy is infinite. Technical report, Institut für theoretische Informatik, TH Darmstadt, 1993b.
[19] M. Li?kiewicz, K. Lory?, andM. Piotrów On reversal bounded alternating Turing machines.Theoret. Comput. Sci. 54 (1987), 331-339. · Zbl 0643.68065 · doi:10.1016/0304-3975(87)90138-1
[20] W. J. Paul,Komplexitätstheorie. Teubner Studienbücher, Informatik, Stuttgart, 1978.
[21] U. Schöning and K. W. Wagner, Collapsing oracle hierarchies, census functions and logarithmically many queries. InProc. 5th. STACS 88, Lecture Notes in Computer Science 294, 1988, 91-97. · Zbl 0648.68065
[22] M. Sipser, Halting bounded computations.,Theoret. Comput. Sci. 10 (1980), 335-338. · Zbl 0423.68011 · doi:10.1016/0304-3975(80)90053-5
[23] M. Sipser, Borel sets and circuit complexity. InProc. Fifteenth Ann. ACM Symp. Theor. Comput., 1983, 330-335.
[24] R. Szelepcsényi, The method of forced enumeration for nondeterministic automata.Acta Infor. 26 (1988), 279-284. · Zbl 0638.68046 · doi:10.1007/BF00299636
[25] K. W. Wagner, The alternation hierarchy for sublogarithmic space: an exciting race to STACS’93 (Editorial note). InProc. 10 STACS, Lecture Notes in Computer Science 665, 1993, 2-4. · Zbl 0797.68062
[26] K. Wagner andG. Wechsung,Computational Complexity. D. Reidel Publishing Company, Dordrecht, Boston, Lancaster, Tokyo, 1986.
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.