Article ID Journal Published Year Pages File Type
10332592 Journal of Algorithms 2005 5 Pages PDF
Abstract
We consider the satisfiability problem on Boolean formulas in conjunctive normal form. We show that a satisfying assignment of a formula can be found in polynomial time with a success probability of 2−n(1−1/(1+logm)), where n and m are the number of variables and the number of clauses of the formula, respectively. If the number of clauses of the formulas is bounded by nc for some constant c, this gives an expected run time of O(p(n)·2n(1−1/(1+clogn))) for a polynomial p.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,