The satisfiability problem for probabilistic ordered branching programs

Authors
Agrawal, M Thierauf, T
Citation
M. Agrawal et T. Thierauf, The satisfiability problem for probabilistic ordered branching programs, THEOR C SYS, 34(5), 2001, pp. 471-487
Citations number
22
Categorie Soggetti
Computer Science & Engineering
Journal title
THEORY OF COMPUTING SYSTEMS
ISSN journal
14324350 → ACNP
Volume
34
Issue
5
Year of publication
2001
Pages
471 - 487
Database
ISI
SICI code
1432-4350(200109/10)34:5<471:TSPFPO>2.0.ZU;2-O
Abstract
We show that the satisfiability problem for bounded-error probabilistic ord ered 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 s atisfiability problem.