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

\(P\)-complete \(GEN\) problembranching programsoracles

Mathematics Subject Classification ID

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

Review text

The authors investigate the space complexity of the \(P\)- complete \(GEN\) problem by means of so-called oracle branching programs. \(GEN\) consists of determining membership in a subalgebra of a general (not necessarily associative) binary algebra (input as a multiplication table). natural subclasses of \(P\) can be expressed as natural subproblems for \(GEN\). Finally, the authors prove optimal lower bounds on the size of oracle branching programs for \(GEN\) with certain natural oracles.

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

• A taxonomy of problems with fast parallel algorithms
• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• 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 ¹
• 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?)
• 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)

• COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE
• 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?)
• On the complexity of some problems on groups input as multiplication tables
• Count-free Weisfeiler-Leman and group isomorphism
• On the parallel complexity of group isomorphism via Weisfeiler-Leman
• On the constant-depth circuit complexity of generating quasigroups
• Constant depth circuit complexity for generating quasigroups
• Incremental branching programs

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)