期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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, i.e., 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.
