scientific article; zbMATH DE number 4024792
From MaRDI portal
Publication:3766852
[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})\).
Recommendations
- [[:Publication:1118407|The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^Template:\mathcal L=A\Pi_ 2^Template:\mathcal L\)]]
- scientific article; zbMATH DE number 45125
- scientific article; zbMATH DE number 3999297
- A hierarchy that does not collapse : alternations in low level space
- Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
Cited in
(5)- [[:Publication:1118407|The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^Template:\mathcal L=A\Pi_ 2^Template:\mathcal L\)]]
- Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata
- scientific article; zbMATH DE number 1775408 (Why is no real title available?)
- scientific article; zbMATH DE number 3999297 (Why is no real title available?)
- Regular expressions with backreferences and lookaheads capture NLOG
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3766852)