Using CSP To Improve Deterministic 3-SAT

2010/07/07 by Konstantin Kutzkov, Dominik Scheder, Kutzkov, Konstantin +1 · 3 citations
Computer Science · #Advanced Graph Theory Research #Algorithms and Data Compression #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.1007.1166

openalex publication_date 2010/07/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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ⁿ).

Cited by

• CNF Encodings of Cardinality Constraints Based on Comparator Networks
• Worst-Case Upper Bound for (1, 2)-QSAT
• New Worst-Case Upper Bound for #XSAT

Related

• From k-SAT to k-CSP: Two Generalized Algorithms
• Advancing Stochastic 3-SAT Solvers by Dissipating Oversatisfied Constraints
• Evolving difficult SAT instances thanks to local search
• SAT vs CSP: a commentary
• SAT Requires Exhaustive Search