The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\) (Q1118407)

It is shown that the second level of the logarithmic space hierarchy is closed under complementation, i.e., this hierarchy ``collapses'' to its second level. The result is proved by considering the Hausdorff closure of NL, and also the Boolean NL and NP hierarchy. A more recent result by Immerman shows that the results reported in the present paper are not the strongest possible ones: Actually, NL is closed under complementation, i.e. the logarithmic alternation hierarchy collapses to its first level.