Derandomizing HSSW Algorithm for 3-SAT

Abstract

We present a (full) derandomization of HSSW algorithm for 3-SAT, proposed by Hofmeister, Schöning, Schuler, and Watanabe in [STACS'02]. Thereby, we obtain an O(1.3303^n)-time deterministic algorithm for 3-SAT, which is currently fastest.

11 pages

References in corpus (2)

• Using CSP To Improve Deterministic 3-SAT
• A Full Derandomization of Schoening's k-SAT Algorithm

Cited by in corpus (1)

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