__
TR01-037 | 21st February 2001 00:00
__

#### Bounded-Width Probabilistic OBDDs and Read-Once Branching Programs are Incomparable

**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).