Derandomizing HSSW Algorithm for 3-SAT

2011/02/18 by Makino, Kazuhisa, Tamaki, Suguru, Yamamoto, Masaki
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1102.3766

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ⁿ)-time deterministic algorithm for 3-SAT, which is currently fastest.

Related

• A Polynomial Time Algorithm for 3-SAT
• Simpler Partial Derandomization of PPSZ for k-SAT
• A randomized, efficient algorithm for 3SAT
• A Full Derandomization of Schoening's k-SAT Algorithm
• Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT