A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs

DOI10.1016/S0020-0190(02)00486-6zbMath1173.68527OpenAlexW2026323912MaRDI QIDQ1007589

Beate Bollig

Publication date: 23 March 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(02)00486-6

zbMATH Keywords

computational complexitylower boundsnondeterminismread-once branching programsdepth-restricted circuits

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Bounded semantics

Cites Work

• Graph driven BDDs -- a new data structure for Boolean functions
• Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
• On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
• Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication
• Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems
• Graph-Based Algorithms for Boolean Function Manipulation
• Efficient Boolean manipulation with OBDD's can be extended to FBDD's
• Branching Programs and Binary Decision Diagrams
• Communication Complexity
• A comparison of free BDDs and transformed BDDs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item