Inductive Counting Below LOGSPACE

Abstract We apply the inductive counting technique to nondeterministic branching programs and prove that complementation on this model can be done without increasing the width of the branching programs too much. This shows that for an arbitrary space bound s(n), the class of languages accepted by nonuniform nondeterministic O(s(n)) space bounded Turing machines is closed under complementation. As a consequence we obtain for arbitrary space bounds s(n) that the alternation hierarchy of nonuniform O(s(n)) space bounded Turing machines collapses to its first level. This improves the previously known result of Immerman [6] and Szelepcsényi [12] to space bounds of order o (log n ) in the nonuniform setting. This reveals a strong difference to the relations between the corresponding uniform complexity classes, since very recently it has been proved that in the uniform case the alternating space hierarchy does not collapse for sublogarithmic space bounds [3, 5, 9].

Authors

• Carsten Damm
• Markus Holzer 0001

Keywords

No keywords are indexed for this paper.