Improved Randomized Algorithms for 3-SAT

摘要

This pager gives a new randomized algorithm which solves 3-SAT in time O(1.32113~n). The previous best bound is O(1.32216~n) due to Rolf (J. SAT, 2006). The new algorithm uses the same approach as Iwama and Tamaki (SODA 2004), but exploits the non-uniform initial assignment due to Hofmeister et al. (STACS 2002) against the Schoning's local search (FOCS 1999).