The Satisfiability Problem for Probabilistic Ordered Branching Programs
Manindra Agrawal, Thomas Thierauf · Theory of Computing Systems · 2001
We show that the satisfiability problem for bounded error probabilistic ordered branching programs 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.