Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs
FB Informatik, LS2, University Dortmund,
44221 Dortmund, Germany; email@example.com.
Supported in part by DFG We 1066/9.
Accepted: January 2003
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 test is co-NP-complete for nondeterministic (parity) graph-driven BP1s. Moreover, a lower bound technique for nondeterministic graph-driven BP1s is presented. The method generalizes a technique for the well-structured model and 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).
Mathematics Subject Classification: 68Q05 / 68Q15 / 94C10
Key words: Computational complexity / read-once branching programs / nondeterminism / lower bounds.
© EDP Sciences, 2003