On Nondeterminism versus Randomness for Read-Once Branching Programs
Martin Sauerhoff · 1997
Randomized branching programs are a probabilistic model of computation defined in analogy to the well-known probabilistic Turing machines. In this paper, we present complexity theoretic results for randomized read-once branching programs. Our main result shows that nondeterminism can be more powerful than randomness for read-once branching programs. We present a function which is computable by nondeterministic read-once branching programs of polynomial size, while on the other hand randomized read-once branching programs for this function with twosided error at most 21 OE 256 have exponential size. The same function exhibits an exponential gap between the randomized read-once branching program sizes for different constant worst-case errors, which shows that there is no "probability amplification" technique for read-once branching programs which allows to decrease the error to an arbitrarily small constant by iterating probabilistic computations. Keywords: Branching programs, read-on...