Title :
The satisfiability problem for probabilistic ordered branching programs
Author :
Agrawal, Manindra ; Thierauf, Thomas
Author_Institution :
Dept. of Comput. Sci., Indian Inst. of Technol., Kanpur, India
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
Keywords :
computability; computational complexity; NP-complete; polynomial-time algorithm; probabilistic ordered branching programs; satisfiability problem; Binary decision diagrams; Boolean functions; Circuits; Computational modeling; Computer errors; Computer science; Data structures; Testing; Turing machines;
Conference_Titel :
Computational Complexity, 1998. Proceedings. Thirteenth Annual IEEE Conference on
Conference_Location :
Buffalo, NY
Print_ISBN :
0-8186-8395-3
DOI :
10.1109/CCC.1998.694593
