Agrawal, M. ; Thierauf, T. (2001) The satisfiability problem for probabilistic ordered branching programs Theory of Computing Systems, 34 (5). pp. 471-487. ISSN 1432-4350
![[img]](https://repository.ias.ac.in/style/images/fileicons/application_pdf.png)
|
PDF
- Publisher Version
182kB |
Official URL: http://www.springerlink.com/content/tb95wndx1p8v4u...
Related URL: http://dx.doi.org/10.1007/s00224-001-1011-9
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 Springer-Verlag. |
| ID Code: | 20250 |
| Deposited On: | 20 Nov 2010 14:47 |
| Last Modified: | 17 May 2016 04:37 |
Repository Staff Only: item control page
