|
Universität Bonn -> Institut für Informatik -> Abteilung V | ||
CS-Reports 1998 | Copyright 1998 Universität Bonn, Institut für Informatik, Abt. V | |
85194
|
On the Computation Power of Randomized Branching Programs
Marek Karpinski [Download PostScript] [Download PDF] We survey some upper and lower bounds established recently on the sizes of \emph{randomized} branching programs computing explicit boolean functions. In particular, we display boolean functions on which \emph{randomized} read-once ordered branching programs are exponentially more powerful than deterministic or nondeterministic read-$k$-times branching programs for any $k=o(n/\!\log n)$. We investigate further computational power of \emph{randomized} read-once order branching programs (OBDDs) and their basic manipulation properties for verification of boolean functions and for testing graphs of arithmetic functions. |
|
Last Change:
08/18/99 at 13:00:38
English |
Universität Bonn -> Institut für Informatik -> Abteilung V |