Complexity theoretical results on nondeterministic graph-driven read-once branching programs

DOI10.1007/3-540-36494-3_27MaRDI QIDQ4418658zbMATH OpenFDO

Authors Beate Bollig

Publication date 11 August 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2607/26070295.htm

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs
• A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs
• A lower bound technique for nondeterministic graph-driven read-once-branching programs and its applications
• On the hierarchy of nondeterministic branching k-programs
• A lower bound technique for nondeterministic graph-driven read-once-branching programs and its applications

Cited in

(6)

• A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs
• A lower bound technique for nondeterministic graph-driven read-once-branching programs and its applications
• 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
• Mathematical Foundations of Computer Science 2003
• The optimal read-once branching program complexity for the direct storage access function

This page was built for publication: Complexity theoretical results on 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 Q4418658)