Using CSP To Improve Deterministic 3-SAT
Konstantin Kutzkov, Dominik Scheder · arXiv (Cornell University) · 2010
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).