Using CSP To Improve Deterministic 3-SAT
classification
💻 cs.DS
keywords
deterministicimprovealgorithmscertainconstraintcspshigher-valuelocal
read the original 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).
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.