A Full Derandomization of Schoning's k-SAT Algorithm

摘要

Schoning [12] presents a simple randomized algorithm for k-SAT with running time a_k~n · poly(n) for a_k = 2(k - 1)/k. We give a deterministic version of this algorithm running in time a_k~(n+o(n)).