Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR98-018 | 27th March 1998 00:00

Randomness and Nondeterminism are Incomparable for Read-Once Branching Programs


Authors: Martin Sauerhoff
Publication: 3rd April 1998 13:04
Downloads: 1139


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.


Comment #1 to TR98-018 | 16th April 1998 14:07

Comment Contact: sauerhof@ls2.cs.uni-dortmund.de Author: Martin Sauerhoff Title: Correction to "Randomness and Nondeterminism are Incomparable for Read-Once Branching Programs" Comment on: TR98-018

Comment #1
Accepted on: 16th April 1998 14:07
Downloads: 1057


The proof of Theorem 1 in the paper contains an error and the presented
technique for proving lower bounds on the size of randomized read-once
branching programs does not work.
We show that one of the functions considered in the paper, the
"addressing function" of Jukna, is computable in polynomial size by a
randomized read-once branching program with zero error.

ISSN 1433-8092 | Imprint