
Summary: 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 non deterministic 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.
Switching theory, application of Boolean algebra; Boolean functions, Complexity classes (hierarchies, relations among complexity classes, etc.), Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.), Models of computation (Turing machines, etc.), Boolean functions, branching programs
Switching theory, application of Boolean algebra; Boolean functions, Complexity classes (hierarchies, relations among complexity classes, etc.), Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.), Models of computation (Turing machines, etc.), Boolean functions, branching programs
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 8 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
