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

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

zbMATH Keywords

alternationcomplexity classeslogspaceNLlogarithmic space hierarchy

Mathematics Subject Classification ID

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}}\)