Oracle branching programs and Logspace versus \(P^*\)

DOI10.1016/0890-5401(91)90017-VzbMath0744.68107MaRDI QIDQ1183604

Pierre McKenzie, David A. Mix Barrington

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)

Related Items (5)

Incremental branching programs ⋮ COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE ⋮ On the complexity of some problems on groups input as multiplication tables ⋮ Unnamed Item ⋮ Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle

Cites Work

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

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