Abstract:
We introduce a model of a {\em randomized branching program} in a natural way similar to the definition of a randomized circuit. We exhibit an explicit boolean function $f_{n}:\{0,1\}^{n}\to\{0,1\}$ for which we prove that: 1) $f_{n}$ can be computed by a polynomial size randomized ordered read-once branching program with a small one-sided error. 2) $f_{n}$ cannot be computed in polynomial size by any nondeterministic ordered $read$-$k$-$times$ branching program for any $k=o(n/\log n)$. The required nondeterministic size is $2^{\Omega (n/k)}$.