Deterministic algorithm improves 3-SAT problem solving speed

Improved Deterministic Algorithms for $k$-SAT: Generalization of Chains and Recurrence Proof

Data Structures and Algorithms

Summary

Solving 3-SAT, a problem that asks if there is a way to assign true or false values to variables in a logical formula, can be very slow. The authors present a method that speeds this up deterministically by grouping clauses into small blocks and using a combination of search and reduction techniques. Their approach carefully balances different strategies and proves the improved speed mathematically. This method also offers ideas for building practical SAT solvers by showing how to choose when to switch strategies based on clause overlaps.

What this means in practice

  • For software verification engineers: Improve deterministic SAT solver components that verify complex software properties by integrating block-based clause grouping and mixed search strategies.
  • For artificial intelligence developers: Enhance constraint satisfaction modules in AI systems by applying guaranteed faster deterministic algorithms for satisfiability problems.

Authors

Binbin Cui, S. Cliff Liu, Yongrui Yu

Abstract

We present a deterministic algorithm for 3-SAT running in $1.32736^n$ time. The algorithm is built on a branching-and-chain framework augmented with a polynomial-time expansion procedure that joins short chains through additional clauses to form bounded-size blocks, which impose stronger constraints on the assignment space. After branching, the algorithm chooses between derandomized local search guided by the block structure and enumeration of block assignments together with selected port variables, reducing the remaining formula to 2-SAT. A weighted analysis of branching, partial-assignment, and local-search costs, together with inductive bounds for chains and block interactions, establishes the running-time guarantee. The framework is self-contained and also offers guidance for practical SAT solver design by identifying useful clause-overlap structures and suggesting when to switch between local-search and reduction-based strategies.