The logarithmic alternation hierarchy collapses: $$A\Sigma _2^\mathcal{L} = A\Pi _2^\mathcal{L}$$
- 1 January 1987
- book chapter
- Published by Springer Nature
- p. 531-541
- https://doi.org/10.1007/3-540-18088-5_46
Abstract
No abstract availableKeywords
This publication has 13 references indexed in Scilit:
- Two characterizations of the logarithmic alternation hierarchyPublished by Springer Nature ,2005
- Separation with the Ruzzo, Simon, and Tompa relativization implies Dspace(log n) ≠ Nspace(log n)Information Processing Letters, 1987
- The complexity of combinatorial problems with succinct input representationActa Informatica, 1986
- Space-bounded hierarchies and probabilistic computationsJournal of Computer and System Sciences, 1984
- AlternationJournal of the ACM, 1981
- The monotone and planar circuit value problems are log space complete for PACM SIGACT News, 1977
- Relativization of questions about log space computabilityTheory of Computing Systems, 1976
- The polynomial-time hierarchyTheoretical Computer Science, 1976
- The equivalence problem for regular expressions with squaring requires exponential spacePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1972
- Relationships between nondeterministic and deterministic tape complexitiesJournal of Computer and System Sciences, 1970