A Full Derandomization of Schoening's k-SAT Algorithm

Abstract

Schoening in 1999 presented a simple randomized algorithm for k-SAT with running time O(a^n * poly(n)) for a = 2(k-1)/k. We give a deterministic version of this algorithm running in time O((a+epsilon)^n * poly(n)), where epsilon > 0 can be made arbitrarily small.

11 pages

References in corpus (1)

• Using CSP To Improve Deterministic 3-SAT

Cited by in corpus (2)

• 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
• Derandomizing HSSW Algorithm for 3-SAT