Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR00-085 | 19th September 2000 00:00

Probabilistic OBDDs: on Bound of Width versus Bound of Error


Authors: Rustam Mubarakzjanov
Publication: 13th November 2000 15:49
Downloads: 2715


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 to compare probabilistic
OBDDs with other kinds of branching programs, we consider such OBDDs
bounding their width by a constant. We
show this computation model can be more powerful than
polynomial size non-deterministic, probabilistic with bounded error
OBDDs and non-deterministic read-once branching programs. We discuss also
the possibilities to find functions being hard for probabilistic OBDDs
with constant width.

ISSN 1433-8092 | Imprint