期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1997
卷号：1997
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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
computations.
