Randomized Algorithms for 3-SAT

摘要

In [S1] Schoening 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.334~n). In this paper we present randomized algorithms and show that one of them has 0(1.3302~n) expected running time, improving Schoning's algorithm. (Note. At this point, the fastest randomized algorithm for 3-SAT is the one given by Iwama and Tamaki [IT] that runs in O(1.324~n).)