The satisfiability problem for probabilistic ordered branching programs

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:08 Nov 2012 10:56

Repository Staff Only: item control page