The Satisfiability Problem for Probabilistic Ordered Branching Programs |
| |
| Authors: | M. Agrawal T. Thierauf |
| |
| Affiliation: | (1) Department of Computer Science, Indian Institute of Technology, Kanpur 208016, India , DE |
| |
| 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. Received March 17, 2001, and in final form July 19, 2001. Online publication October 30, 2001. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
