Issue Theoret. Informatics Appl. Volume 37, Number 1, January-March 2003 Page(s) 51 - 66 DOI 10.1051/ita:2003010

Theoret. Informatics Appl. 37, 51-66 (2003)
DOI: 10.1051/ita:2003010

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

Beate Bollig

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

Mathematics Subject Classification. 68Q05, 68Q15, 94C10.

Key words: Computational complexity -- read-once branching programs -- nondeterminism -- lower bounds.


© EDP Sciences 2003

What is OpenURL?