Separating the eraser turing machine classes Le, NLe, co-NLe and Pe
- 23 November 2005
- book chapter
- Published by Springer Nature
- p. 405-413
- https://doi.org/10.1007/bfb0017163
Abstract
No abstract availableKeywords
This publication has 9 references indexed in Scilit:
- The power of polynomial size Ω-branching programsPublished by Springer Nature ,2006
- Nondeterministic space is closed under complementationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Exponential lower bounds for real-time branching programsPublished by Springer Nature ,1987
- 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
- Lower bounds on monotone complexity of the logical permanentMathematical Notes, 1985
- Separating the polynomial-time hierarchy by oraclesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- A time-space tradeoff for sorting on a general sequential model of computationPublished by Association for Computing Machinery (ACM) ,1980
- Some connections between nonuniform and uniform complexity classesPublished by Association for Computing Machinery (ACM) ,1980