ECCC-Report TR97-060https://eccc.weizmann.ac.il/report/1997/060Comments and Revisions published for TR97-060en-usFri, 26 Dec 1997 18:25:23 +0200
Paper TR97-060
| The Satisfiability Problem for Probabilistic Ordered Branching Programs |
Manindra Agrawal,
Thomas Thierauf
https://eccc.weizmann.ac.il/report/1997/060We 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.
Fri, 26 Dec 1997 18:25:23 +0200https://eccc.weizmann.ac.il/report/1997/060