Abstract:
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.