Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR97-030 | 25th August 1997 00:00

On Nondeterminism versus Randomness for Read-Once Branching Programs


Authors: Martin Sauerhoff
Publication: 26th August 1997 14:36
Downloads: 1128


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 two-sided error at most 21/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

ISSN 1433-8092 | Imprint