Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
From MaRDI portal
Publication:4020492
DOI10.1051/ita/1992260403451zbMath0768.68017MaRDI QIDQ4020492
Matthias Krause, Stephan Waack, Christoph Meinel
Publication date: 16 January 1993
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/92422
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Communication Complexity and Lower Bounds on Multilective Computations, Separating complexity classes related to bounded alternating ?-branching programs, Separating counting communication complexity classes, On lower bounds for read-\(k\)-times branching programs, Separating $\oplus L$ from $L, NL,$ co-$NL$, and $AL = P$ for oblivious Turing machines of linear access
Cites Work
- On oblivious branching programs of linear length
- On uniform circuit complexity
- Lower bounds for depth-restricted branching programs
- Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
- A complexity theory based on Boolean algebra
- Nondeterministic Space is Closed under Complementation
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item