Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10332592 | Journal of Algorithms | 2005 | 5 Pages |
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
Rainer Schuler,