Voir la notice de l'article provenant de la source Numdam
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 is the test whether a given BP is really a BP of model . 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).
@article{ITA_2003__37_1_51_0,
author = {Bollig, Beate},
title = {Complexity theoretical results on nondeterministic graph-driven read-once branching programs},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {51--66},
publisher = {EDP-Sciences},
volume = {37},
number = {1},
year = {2003},
doi = {10.1051/ita:2003010},
mrnumber = {1991751},
zbl = {1084.68049},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2003010/}
}
TY - JOUR AU - Bollig, Beate TI - Complexity theoretical results on nondeterministic graph-driven read-once branching programs JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2003 SP - 51 EP - 66 VL - 37 IS - 1 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita:2003010/ DO - 10.1051/ita:2003010 LA - en ID - ITA_2003__37_1_51_0 ER -
%0 Journal Article %A Bollig, Beate %T Complexity theoretical results on nondeterministic graph-driven read-once branching programs %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2003 %P 51-66 %V 37 %N 1 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita:2003010/ %R 10.1051/ita:2003010 %G en %F ITA_2003__37_1_51_0
Bollig, Beate. Complexity theoretical results on nondeterministic graph-driven read-once branching programs. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 37 (2003) no. 1, pp. 51-66. doi: 10.1051/ita:2003010
Cité par Sources :