Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR01-037 | 21st February 2001 00:00

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


Authors: Rustam Mubarakzjanov
Publication: 14th May 2001 18:24
Downloads: 3177


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

ISSN 1433-8092 | Imprint