Geodesic
Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 2, pp. 149-162

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 have been studied intensively. In this paper the expressive power of nondeterministic read-once branching programs, more precisely the class of functions representable in polynomial size, is investigated. For that reason two restricted models of nondeterministic read-once branching programs are defined and a lower bound method is presented. Furthermore, the first exponential lower bound for integer multiplication on the size of a nondeterministic nonoblivious read-once branching program model is proven.

Classification : 68Q05, 68Q10, 68Q15, 94C10
Keywords: computational complexity, read-once branching programs, nondeterminism, integer multiplication 
@article{ITA_2001__35_2_149_0,
     author = {Bollig, Beate},
     title = {Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {149--162},
     publisher = {EDP-Sciences},
     volume = {35},
     number = {2},
     year = {2001},
     mrnumber = {1862460},
     zbl = {0992.68057},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ITA_2001__35_2_149_0/}
}
TY  - JOUR
AU  - Bollig, Beate
TI  - Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2001
SP  - 149
EP  - 162
VL  - 35
IS  - 2
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/item/ITA_2001__35_2_149_0/
LA  - en
ID  - ITA_2001__35_2_149_0
ER  - 
%0 Journal Article
%A Bollig, Beate
%T Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2001
%P 149-162
%V 35
%N 2
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/item/ITA_2001__35_2_149_0/
%G en
%F ITA_2001__35_2_149_0
Bollig, Beate. Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 2, pp. 149-162. http://geodesic.mathdoc.fr/item/ITA_2001__35_2_149_0/