Restricted branching programs are considered by the investigation of relationships between complexity classes of Boolean functions. Read-once ordered branching programs (or OBDDs) form the most restricted class of this computation model. Since the problem of proving exponential lower bounds on the complexity for general probabilistic OBDDs is open so far, ... more >>>

Ordered binary decision diagrams (OBDDs) are well established tools to represent Boolean functions. There are a lot of results concerning different types of generalizations of OBDDs. The same time, the power of the most general form of OBDD, namely probabilistic (without bounded error) OBDDs, is not studied enough. In order ... more >>>

We prove that the error-free (Las Vegas) randomized OBDDs are computationally equivalent to the deterministic OBDDs. In contrast, it is known the same is not true for the Las Vegas read-once branching programs. more >>>