The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\)
From MaRDI portal
Publication:1118407
DOI10.1016/0890-5401(89)90012-6zbMath0668.68055OpenAlexW1997449252MaRDI QIDQ1118407
Bernd Kirsig, Birgit Jenner, Klaus-Joern Lange
Publication date: 1989
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0890-5401(89)90012-6
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (6)
Depth-first search in directed planar graphs, revisited ⋮ Empty alternation ⋮ On truth-table reducibility to SAT ⋮ A hierarchy that does not collapse : alternations in low level space ⋮ Computing functions with parallel queries to NP ⋮ Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of facets (and some facets of complexity)
- Space-bounded hierarchies and probabilistic computations
- The complexity of combinatorial problems with succinct input representation
- \(\Sigma_ 2SPACE(n)\) is closed under complement
- A comparison of polynomial time reducibilities
- The polynomial-time hierarchy
- Relationships between nondeterministic and deterministic tape complexities
- The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
- Alternation
- Relativization of questions about log space computability
- Logspace hierarchies, polynomial time and the complexity of fairness problems concerning ω-machines
This page was built for publication: The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\)
