Alternation for two-way machines with sublogarithmic space. (English) Zbl 0797.68056

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, 5-15 (1993).
In structural complexity theory many hierarchies have been considered but only seldom results have about their extension been found. Of course some negative results are well known. E.g. all oracle hierarchies and, therefore, all alternation hierarchies related to space-bounded machines collapse, provided that we consider strong space complexity and space- bounds in \(\Omega(\log)\) [N. Immermann, SIAM J. Comput. 17, No. 5, 935-938 (1988; Zbl 0668.68056); R. Szelepcsenyi, Acta Inf. 26, No. 3, 279-284 (1988; Zbl 0649.68055)]. The strong exponential time hierarchy SEH collapses in \(\text{P}^{\text{NE}}\) [L. A. Hemachandra, J. Comput. Syst. Sci. 39, No. 3, 299-322 (1989; Zbl 0693.03022); U. Schöning and K. W. Wagner, Lect. Notes Comput. Sci. 294, 91-97 (1988; Zbl 0648.68065)] and so does the hierarchy \(\text{IP}(k)\) \((k\in\mathbb{N})\) of interactive proof systems [L. Babai and Sh. Moran, J. Comput. Syst. Sci. 36, No. 2, 254-276 (1988; Zbl 0652.03029)].
Positive answers are even more rare, although some interrelations between hierarchies have been detected. A separation has been achieved for the circuit classes \(AC^ 0\) and \(AC^ 1\), whereas within \(AC^ 0\) there is a proper hierarchy related to circuit depth. This corresponds to the hierarchy of logarithmic time-bounded alternating Turing machines with random access input tape. The nondeterministic space hierarchy of Turing machines leads to a proper alternation hierarchy which is related to reversal-bounded one-tape Turing machines without input tape.
Although we know that the alternation hierarchies for Turing machines with space-bound log or greater collapse, the question remains whether a hierarchy for space-bounds less than log exists. For one-way Turing machines with an arbitrary space-bound in \(o(\log)\) an infinite alternation hierarchy has been established.
This paper deals with the corresponding issue concerning two-way Turing machines. We show that the alternation hierarchy for two-way Turing machines with a space-bound in \(o(\log)\) does not collapse below level five.
For the entire collection see [Zbl 0866.00060].


68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
03D10 Turing machines and related notions