Issue Theoret. Informatics Appl. Volume 35, Number 2, March-April 2001 Page(s) 149 - 162 DOI 10.1051/ita:2001113

DOI: 10.1051/ita:2001113


Theoret. Informatics Appl. 35, 149-162 (2001)

Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication

Beate Bollig

FB Informatik, LS2, Univ. Dortmund, 44221 Dortmund, Germany; (bollig@ls2.cs.uni-dortmund.de)

(Received April 17, 2000. Accepted March 9, 2001.)

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

AMS Subject: 68Q05, 68Q10, 68Q15, 94C10.

Key words: Computational complexity -- read-once branching programs -- nondeterminism -- integer multiplication.


© EDP Sciences 2001

What is OpenURL?