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

DOI10.1051/ITA/1992260403451MaRDI QIDQ4020492zbMATH OpenOpenAlexFDO

Authors Matthias Krause, Christoph Meinel, Stephan Waack

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)

Recommendations

• scientific article; zbMATH DE number 4213443
• Separating \oplus L from L, NL, co-NL, and AL = P for oblivious Turing machines of linear access
• scientific article; zbMATH DE number 4072383
• Separation of deterministic, nondeterministic and alternating complexity classes
• scientific article; zbMATH DE number 1072535

Cites work

• A complexity theory based on Boolean algebra
• scientific article; zbMATH DE number 3987266 (Why is no real title available?)
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 4051004 (Why is no real title available?)
• scientific article; zbMATH DE number 4087055 (Why is no real title available?)
• Lower bounds for depth-restricted branching programs
• Nondeterministic Space is Closed under Complementation
• On oblivious branching programs of linear length
• On uniform circuit complexity
• Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)

Cited in

(9)

• Space bounded computations: Review and new separation results
• On lower bounds for read-\(k\)-times branching programs
• scientific article; zbMATH DE number 4213443 (Why is no real title available?)
• scientific article; zbMATH DE number 4072383 (Why is no real title available?)
• Separating \oplus L from L, NL, co-NL, and AL = P for oblivious Turing machines of linear access
• Communication Complexity and Lower Bounds on Multilective Computations
• Separating complexity classes related to bounded alternating ?-branching programs
• Logspace hierarchies, polynomial time and the complexity of fairness problems concerning ω-machines
• Separating counting communication complexity classes

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4020492)