Agrawal, M. ; Thierauf, T. (1998) The satisfiability problem for probabilistic ordered branching programs Proceedings of Thirteenth Annual IEEE Conference on Computational Complexity . pp. 81-90. ISSN 1093-0159
Full text not available from this repository.
Official URL: http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnum...
Related URL: http://dx.doi.org/10.1109/CCC.1998.694593
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.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to IEEE. |
| ID Code: | 95345 |
| Deposited On: | 08 Nov 2012 10:56 |
| Last Modified: | 18 Nov 2022 05:49 |
Repository Staff Only: item control page
