Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs

FB Informatik, LS2, University Dortmund, 44221 Dortmund, Germany; bollig@ls2.cs.uni-dortmund.de.  Supported in part by DFG We 1066/9.

Received: May 2002
Accepted: January 2003

Abstract

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