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

Branching programs are a well-established computation and representation model for boolean functions, especially read-once branching programs (BP1s) have been studied intensively. Recently two restricted nondeterministic (parity) BP1 models, called well-structured nondeterministic (parity) graph-driven BP1s and 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 shown that the complexity of the consistency test is a difference between the two nondeterministic (parity) graph-driven models. Moreover, a new lower bound technique for nondeterministic graph-driven BP1s is presented which is applied in order to answer in the affirmative the open question whether the model of nondeterministic graph-driven BP1s is a proper restriction of nondeterministic BP1s (with respect to polynomial size). Furthermore, a function f in n(2) variables is exhibited such that both the function f and its negation -f can be computed by Sigma(p)(3)-circuits, f and -f have simple nondeterministic BP1s of small size but f requires nondeterministic graph-driven BP1s of size 2(Omega(n)). This answers an open question stated by Jukna, Razborov, Savick, and Wegener (1999).