×

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)

Citations:

Zbl 0616.00013