Abstract:
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, it is interesting to study this problem in a restricted setting. For this reason we deal in this work with probabilistic OBDDs whose width is bounded. We prove in this work that probabilistic OBDDs of width bounded by a constant can be more powerful than even non-deterministic read-once branching programs. To do it we present a probabilistic OBDD of constant width computing the known function PERM. We prove for several known functions that they cannot be computed by probabilistic OBDDs of constant width. To show it we present a new method allowing to obtain lower bound Omega(n) on the width of corresponding OBDDs (n is the number of variables).