Oracle branching programs and Logspace versus P^*

DOI10.1016/0890-5401(91)90017-VMaRDI QIDQ1183604zbMATH OpenFDO

Authors David A. Mix Barrington, Pierre McKenzie

Publication date 28 June 1992

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

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

zbMATH Keywords

branching programsoracles\(P\)-complete \(GEN\) problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 17817
• scientific article; zbMATH DE number 17548
• Polynomial size \(\Omega\)-branching programs and their computational power
• Incremental branching programs
• scientific article; zbMATH DE number 4051004

Cites work

• scientific article; zbMATH DE number 4087055 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3555903 (Why is no real title available?)
• scientific article; zbMATH DE number 4117877 (Why is no real title available?)
• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• A taxonomy of problems with fast parallel algorithms
• An observation on time-storage trade off
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Complete problems for deterministic polynomial time
• Finite monoids and the fine structure of NC ¹
• New problems complete for nondeterministic log space
• Nondeterministic Space is Closed under Complementation
• On Relating Time and Space to Size and Depth
• Problems complete for deterministic logarithmic space
• Relationships between nondeterministic and deterministic tape complexities
• Space-bounded reducibility among combinatorial problems
• The complexity of parallel search
• Towards a complexity theory of synchronous parallel computation

Cited in

(10)

• scientific article; zbMATH DE number 17817 (Why is no real title available?)
• Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle
• scientific article; zbMATH DE number 7250165 (Why is no real title available?)
• Constant depth circuit complexity for generating quasigroups
• COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE
• On the complexity of some problems on groups input as multiplication tables
• On the parallel complexity of group isomorphism via Weisfeiler-Leman
• Incremental branching programs
• On the constant-depth circuit complexity of generating quasigroups
• Count-free Weisfeiler-Leman and group isomorphism

This page was built for publication: Oracle branching programs and Logspace versus \(P^*\)

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