Manindra Agrawal and Thomas Thierauf
We show that the satisfiability problem for
bounded error probabilistic ordered branching programs
(BP-OBDDs for short)
If the error is very small however
if the error is bounded by the reciprocal of the width of the
then we have a polynomial-time algorithm for the satisfiability problem.