期刊名称:Electronic Colloquium on Computational Complexity
印刷版ISSN:1433-8092
出版年度:1997
卷号:1997
出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要: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.