Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication
FB Informatik, LS2, Univ. Dortmund,
44221 Dortmund, Germany; (firstname.lastname@example.org)
Accepted: 9 March 2001
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.
Mathematics Subject Classification: 68Q05 / 68Q10 / 68Q15 / 94C10
Key words: Computational complexity / read-once branching programs / nondeterminism / integer multiplication.
© EDP Sciences, 2001