期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1998
卷号：1998
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We extend the tools for proving lower bounds for randomized branching
programs by presenting a new technique for the read-once case which is
applicable to a large class of functions. This technique fills the gap
between simple methods only applicable for OBDDs and the well-known
"rectangle technique" of Borodin, Razborov and Smolensky which works
for the quite general models of nondeterministic and randomized
read-k-times branching programs, but which has the drawback that it
could only be applied to very special functions so far.
By an application of this technique, we resolve the remaining open
problems concerning the relations of the most important probabilistic
complexity classes for read-once branchings programs. We obtain that
the analogues of the classes BPP and NP for read-once branching
programs are incomparable and that RP is a proper subclass of NP.
关键词：Communication complexity, lower bounds, nondeterminism, Randomization, read-once branching program
