Oracle branching programs and Logspace versus P^*

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

Authors David A. Mix Barrington, Pierre McKenzie

Publication date 28 June 1992

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

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

(7)

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

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)