## The logarithmic alternation hierarchy collapses: $$A\Sigma_ 2^{\mathfrak L}=A\Pi_ 2^{\mathfrak L}$$.(English)Zbl 0629.68051

Automata, languages and programming, Proc. 14th Int. Colloq., Karlsruhe/FRG 1987, Lect. Notes Comput. Sci. 267, 531-541 (1987).
[For the entire collection see Zbl 0616.00013.]
We show that $$A\Sigma_ 2^{{\mathfrak L}}$$ coincides with $$A\Pi_ 2^{{\mathfrak L}}$$. Essentially this is done by Hausdorff reducing the $$A\Sigma_ 2^{{\mathfrak L}}$$-complete set $$(GAP\not\subset Co$$- GAP)$${}^{(\exists)}$$ to the question whether of two vectors A and B of n components, A contains more “solvable” components, i.e. components which are contained in GAP, than B. Moreover, we show $$A\Sigma_ 2^{{\mathfrak L}}={\mathfrak L}_{hd}({\mathfrak NL})$$.

### MSC:

 68Q25 Analysis of algorithms and problem complexity 03D15 Complexity of computation (including implicit computational complexity)

Zbl 0616.00013