The Satisfiability Problem for Probabilistic Ordered Branching Programs

Manindra Agrawal and Thomas Thierauf

We show that the satisfiability problem for
bounded error probabilistic ordered branching programs (BP-OBDDs for short)
is NP-complete. If the error is very small however
(more precisely, if the error is bounded by the reciprocal of the width of the branching program),
then we have a polynomial-time algorithm for the satisfiability problem.