Separating ⊕L from L, NL, co-NL and AL (=P) for Oblivious turing machines of linear access time
- 1 December 2005
- book chapter
- Published by Springer Nature
- p. 385-391
- https://doi.org/10.1007/bfb0029633
Abstract
No abstract availableKeywords
This publication has 12 references indexed in Scilit:
- The power of polynomial size Ω-branching programsPublished by Springer Nature ,2006
- On the power of parity polynomial timePublished by Springer Nature ,2005
- Two remarks on the power of countingPublished by Springer Nature ,2005
- Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machinesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Separating completely complexity classes related to polynomial size Ω-Decision treesPublished by Springer Nature ,1989
- On the complexity of branching programs and decision trees for clique functionsJournal of the ACM, 1988
- Nondeterministic space is closed under complementationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Meanders, Ramsey theory and lower bounds for branching programsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- On uniform circuit complexityJournal of Computer and System Sciences, 1981
- The recognition problem for the set of perfect squaresPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1966