The logarithmic alternation hierarchy collapses: AΣ2L = AΠ2L
- 1 March 1989
- journal article
- Published by Elsevier in Information and Computation
- Vol. 80 (3) , 269-288
- https://doi.org/10.1016/0890-5401(89)90012-6
Abstract
No abstract availableKeywords
This publication has 11 references indexed in Scilit:
- Collapsing oracle hierarchies, census functions and logarithmically many queriesPublished by Springer Nature ,2006
- Σ2 SPACE(n) is closed under complementJournal of Computer and System Sciences, 1987
- Space-bounded hierarchies and probabilistic computationsJournal of Computer and System Sciences, 1984
- The complexity of facets (and some facets of complexity)Journal 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
- A comparison of polynomial time reducibilitiesTheoretical Computer Science, 1975
- Relationships between nondeterministic and deterministic tape complexitiesJournal of Computer and System Sciences, 1970