ECCC-Report TR01-037https://eccc.weizmann.ac.il/report/2001/037Comments and Revisions published for TR01-037en-usMon, 14 May 2001 18:24:57 +0300
Paper TR01-037
| Bounded-Width Probabilistic OBDDs and Read-Once Branching Programs are Incomparable |
Rustam Mubarakzjanov
https://eccc.weizmann.ac.il/report/2001/037Restricted 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).
Mon, 14 May 2001 18:24:57 +0300https://eccc.weizmann.ac.il/report/2001/037