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

DOI10.1016/S0020-0190(02)00486-6MaRDI QIDQ1007589zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• A simple function that requires exponential size read-once branching programs
• A very simple function that requires exponential size read-once branching programs.
• scientific article; zbMATH DE number 1962822
• Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs
• A lower bound technique for nondeterministic graph-driven read-once-branching programs and its applications
• scientific article; zbMATH DE number 1929932
• On the complexity of randomized read-once branching programs
• Comparing the sizes of nondeterministic branching read-k-times programs
• Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication
• A lower bound for read-once-only branching programs

Cites work

• scientific article; zbMATH DE number 4204283 (Why is no real title available?)
• scientific article; zbMATH DE number 512863 (Why is no real title available?)
• scientific article; zbMATH DE number 1011685 (Why is no real title available?)
• scientific article; zbMATH DE number 1962822 (Why is no real title available?)
• scientific article; zbMATH DE number 1929932 (Why is no real title available?)
• scientific article; zbMATH DE number 2086709 (Why is no real title available?)
• scientific article; zbMATH DE number 1834649 (Why is no real title available?)
• A comparison of free BDDs and transformed BDDs
• Branching Programs and Binary Decision Diagrams
• Communication Complexity
• Efficient Boolean manipulation with OBDD's can be extended to FBDD's
• Graph driven BDDs -- a new data structure for Boolean functions
• Graph-Based Algorithms for Boolean Function Manipulation
• 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
• Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
• Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems

Cited in

(6)

• Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs
• scientific article; zbMATH DE number 1962822 (Why is no real title available?)
• A simple function that requires exponential size read-once branching programs
• A very simple function that requires exponential size read-once branching programs.
• Folklore confirmed
• Bounded semantics

This page was built for publication: A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1007589)