Displaying similar documents to “Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication”

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

Beate Bollig (2003)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

Branching programs are a well-established computation model for boolean functions, especially read-once branching programs (BP1s) have been studied intensively. Recently two restricted nondeterministic (parity) BP1 models, called nondeterministic (parity) graph-driven BP1s and well-structured nondeterministic (parity) graph-driven BP1s, have been investigated. The consistency test for a BP-model M is the test whether a given BP is really a BP of model M . Here it is proved that the consistency...

Characterizing the complexity of boolean functions represented by well-structured graph-driven parity-FBDDs

Henrik Brosenne, Matthias Homeister, Stephan Waack (2002)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We investigate well-structured graph-driven parity-FBDDs, which strictly generalize the two well-known models parity OBDDs and well-structured graph-driven FBDDs. The first main result is a characterization of the complexity of Boolean functions represented by well-structured graph-driven parity-FBDDs in terms of invariants of the function represented and the graph-ordering used. As a consequence, we derive a lower bound criterion and prove an exponential lower bound for certain linear...

Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication

Beate Bollig (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Branching programs are a well established computation model for Boolean functions, especially read-once branching programs have been studied intensively. In this paper the expressive power of nondeterministic read-once branching programs, more precisely the class of functions representable in polynomial size, is investigated. For that reason two restricted models of nondeterministic read-once branching programs are defined and a lower bound method is presented. Furthermore, the...