Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR97-060 | 2nd December 1997 00:00

The Satisfiability Problem for Probabilistic Ordered Branching Programs

RSS-Feed




TR97-060
Authors: Manindra Agrawal, Thomas Thierauf
Publication: 26th December 1997 18:25
Downloads: 1024
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint