Oracle branching programs and Logspace versus P^*

DOI10.1016/0890-5401(91)90017-VzbMATH Open0744.68107MaRDI QIDQ1183604FDOQ1183604

Pierre McKenzie, David A. Mix Barrington

Publication date: 28 June 1992

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

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

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)

Cites Work

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

Cited In (7)

• Title not available (Why is that?)
• Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle
• Title not available (Why is that?)
• COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE
• On the complexity of some problems on groups input as multiplication tables
• Incremental branching programs
• 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)