The alternation hierarchy for sublogarithmic space is infinite (Q1312177): Difference between revisions

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.