A Probabilistic 3—SAT Algorithm Further Improved
説明
In [Sch99], Schoning proposed a simple yet efficient randomized algorithm for solving the k-SAT problem. In the case of 3-SAT, the algorithm has an expected running time of poly(n) ? (4/3)n = O(1.3334n) when given a formula F on n variables. This was the up to now best running time known for an algorithm solving 3-SAT. Here, we describe an algorithm which improves upon this time bound by combining an improved version of the above randomized algorithm with other randomized algorithms. Our new expected time bound for 3-SAT is O(1.3302n).
