RAIRO-Theor. Inf. Appl.
Volume 37, Number 1, January/March 2003
|Page(s)||51 - 66|
|Published online||15 November 2003|
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
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.