Separating the eraser Turing machine classes Le, NLe, co-NLe and Pe
- 2 September 1991
- journal article
- Published by Elsevier in Theoretical Computer Science
- Vol. 86 (2) , 267-275
- https://doi.org/10.1016/0304-3975(91)90021-s
Abstract
No abstract availableKeywords
This publication has 9 references indexed in Scilit:
- The power of polynomial size Ω-branching programsPublished by Springer Nature ,2006
- The Complexity of Boolean FunctionsPublished by Springer Nature ,2005
- Nondeterministic Space is Closed under ComplementationSIAM Journal on Computing, 1988
- Lower bounds on the complexity of real-time branching programsRAIRO - Theoretical Informatics and Applications, 1988
- Two lower bounds for branching programsPublished by Association for Computing Machinery (ACM) ,1986
- Bounded-width polynomial-size branching programs recognize exactly those languages in NC1Published by Association for Computing Machinery (ACM) ,1986
- Separating the polynomial-time hierarchy by oraclesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- A complexity theory based on Boolean algebraPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1981
- AlternationJournal of the ACM, 1981