On oblivious branching programs of linear length

DOI10.1016/0890-5401(91)90039-5zbMATH Open0727.68038OpenAlexW2054843454MaRDI QIDQ804285FDOQ804285

Stephan Waack, Matthias Krause

Publication date: 1991

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(91)90039-5

Recommendations

• scientific article; zbMATH DE number 17548
• scientific article
• Separating $\oplus L$ from $L, NL,$ co-$NL$, and $AL = P$ for oblivious Turing machines of linear access
• scientific article; zbMATH DE number 4172378
• scientific article; zbMATH DE number 827986

zbMATH Keywords

decision graphsgraph accessibility problemsword problem of the free group

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Relationships between nondeterministic and deterministic tape complexities
• Word Problems Solvable in Logspace
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the complexity of branching programs and decision trees for clique functions
• Title not available (Why is that?)
• Das Identitätsproblem für Gruppen mit einer definierenden Relation
• Title not available (Why is that?)
• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• Lower bounds for depth-restricted branching programs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Lower bounds on the complexity of real-time branching programs

Cited In (10)

• Title not available (Why is that?)
• Title not available (Why is that?)
• On the parallel complexity of linear groups
• Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance
• On approximation by \(^{\oplus}\)-OBDDs
• Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
• Tight Bounds on Oblivious Chaining
• On the descriptive and algorithmic power of parity ordered binary decision diagrams
• On relations between counting communication complexity classes
• Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs

This page was built for publication: On oblivious branching programs of linear length

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