In this paper, a simple technique which unifies the known approaches for proving lower bound results on the size of deterministic, nondeterministic, and randomized OBDDs and kOBDDs is described. This technique is applied to establish a generic lower bound on the size of randomized OBDDs with bounded eror for the so-called"k-stable" functions which have been studied in the literature on read-once branching programs and OBDds for a long time. It follows by our result that several standard functions are not contained in the analog of the class BPP for OBDDs. It is well-known that k-stable functions are hard for deterministic read-once branching programs. Nevertheless, there is no generic lower bound on the size of randomized read-once branching programs for these functions as for OBDDs. This is proven by presenting a randomized read-once branching prgram of polynomial size, weven with zero error, for a certain k-stable function. As a consequence, we obtain that for the analogs of these classes defined in terms of the size of read-once branchign programs.
展开▼
