Polynomial size \(\Omega\)-branching programs and their computational power

DOI10.1016/0890-5401(90)90046-KzbMath0705.68052MaRDI QIDQ918199

Christoph Meinel

Publication date: 1990

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

zbMATH Keywords

separationbranching programs

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

European Summer Meeting of the Association for Symbolic Logic ⋮ On the size of binary decision diagrams representing Boolean functions ⋮ Graph driven BDDs -- a new data structure for Boolean functions ⋮ Methods for proving completeness via logical reductions ⋮ Separating complexity classes related to \(\Omega\)-decision trees ⋮ Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication ⋮ Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication ⋮ A hierarchy result for read-once branching programs with restricted parity nondeterminism ⋮ Multi-head finite automata: Data-independent versus data-dependent computations

Cites Work

• On the construction of parallel computers from various basis of Boolean functions
• Relationships between nondeterministic and deterministic tape complexities
• Constant Depth Reducibility
• A complexity theory based on Boolean algebra
• Alternation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item