Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines

DOI10.1051/ita/1992260403451zbMath0768.68017OpenAlexW38964248MaRDI 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

zbMATH Keywords

logarithmic space-bounded nondeterministic Turing machines

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (5)

On lower bounds for read-\(k\)-times branching programs ⋮ Communication Complexity and Lower Bounds on Multilective Computations ⋮ Separating counting communication complexity classes ⋮ Separating $\oplus L$ from $L, NL,$ co-$NL$, and $AL = P$ for oblivious Turing machines of linear access ⋮ Separating complexity classes related to bounded alternating ?-branching programs

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

This page was built for publication: Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines