DocumentCode
2142643
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
fYear
1998
fDate
15-18 Jun 1998
Firstpage
81
Lastpage
90
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Computational Complexity, 1998. Proceedings. Thirteenth Annual IEEE Conference on
Conference_Location
Buffalo, NY
ISSN
1093-0159
Print_ISBN
0-8186-8395-3
Type
conf
DOI
10.1109/CCC.1998.694593
Filename
694593
Link To Document