Using CSP To Improve Deterministic 3-SAT

Abstract

We show how one can use certain deterministic algorithms for higher-value constraint satisfaction problems (CSPs) to speed up deterministic local search for 3-SAT. This way, we improve the deterministic worst-case running time for 3-SAT to O(1.439^n).

corrected typos, extended the introduction and added a notation section to make paper self-contained

References in corpus (1)

• Using a Skewed Hamming Distance to Speed Up Deterministic Local Search

Cited by in corpus (5)

• A Full Derandomization of Schoening's k-SAT Algorithm
• Derandomizing HSSW Algorithm for 3-SAT
• New Worst-Case Upper Bound for X3SAT
• Worst-Case Upper Bound for (1, 2)-QSAT
• New Worst-Case Upper Bound for #XSAT