Abstract
We prove that there exists a deterministic configuration of Conflict Driven Clause Learning (CDCL) SAT solvers using a variant of the VSIDS branching heuristic that solves instances of the Ordering Principle (OP) CNF formulas in time polynomial in $n$, where $n$ is the number of variables in such formulas. Since tree-like resolution is known to have an exponential lower bound for proof size for OP formulas, it follows that CDCL under this configuration has an exponential separation with any solver that is polynomially equivalent to tree-like resolution and therefore any configuration of DPLL SAT solvers.
Introduction: The Evolution of SAT Solving
Boolean Satisfiability (SAT) solvers are fundamental tools in computer science, essential for tasks ranging from hardware verification to complex scheduling. Historically, the field has transitioned from the DPLL era (originating in the 1960s) to the modern CDCL (Conflict-Driven Clause Learning) era. While empirical evidence has long suggested that CDCL solvers are vastly superior, providing a rigorous theoretical explanation for this performance gap has remained a challenge.
Theoretical computer science often relies on "nondeterministic" proofs, which assume a solver can perfectly guess the best variables to branch on. However, real-world solvers are deterministic, employing heuristics like VSIDS (Variable State Independent Decaying Sum). This paper addresses the "automatability problem": can a deterministic CDCL solver, using practical heuristics, find the short proofs that exist mathematically and outperform DPLL on formulas where the latter struggles?
Methodology: The Ordering Principle and VSIDS
The researchers focus on the Ordering Principle (OP), a family of logic problems describing a set of elements that must have a total order but no minimum element. This paradox makes the formula "unsatisfiable," and the solver's task is to prove this impossibility.
To demonstrate the performance gap, the authors analyzed a specific deterministic CDCL configuration:
- VSIDS Branching: Utilizing a low decay factor ($\delta \le 1/2$).
- 1UIP Learning: A standard method for generating new "learned" clauses following a conflict.
- Frequent Restarts: The solver restarts its search after every single conflict.
- Fixed Phase Selection: Variables are initially assigned to "false."
The core of the proof involves a direct, inductive analysis of the solver's behavior, mapping out the sequence of learned clauses across three distinct phases: the Head, the Descending Cascade, and the Tail.
Key Insights: The Focus Lemma
A pivotal discovery in this work is the "Focus Lemma." The authors prove that when the VSIDS decay factor is sufficiently low ($\le 1/2$), the solver is mathematically compelled to select variables from the most recently learned clause. This mechanism prevents the solver from wandering aimlessly, forcing it to focus on the immediate contradiction discovered.
Furthermore, the paper shows that a simple tie-breaking rule (column-major order) is sufficient to guide the solver through the Ordering Principle in polynomial time, bridging the gap between abstract proof systems like resolution and practical algorithmic implementations.
Key Results
- Exponential Separation: The research formally proves that while any DPLL solver requires exponential time ($2^{\Omega(n)}$) to solve the Ordering Principle, this deterministic CDCL configuration succeeds in polynomial time.
- Exact Conflict Count: The authors calculated the precise number of conflicts required to reach the "Unsatisfiable" conclusion: exactly $\binom{n}{2} - 3$. For a problem with $n$ variables, this is $O(n^2)$, representing a massive efficiency gain over exponential growth.
- Theoretical Confirmation: This result provides the first formal proof of a polynomial upper bound for a completely deterministic CDCL configuration on this class of formulas.
Limitations and Future Work
While groundbreaking, the proof relies on specific parameters that differ from some industrial practices:
- Decay Factor: The proof uses $\delta \le 1/2$, whereas industrial solvers often use higher factors (around 0.95).
- Restart Frequency: The model restarts after every conflict, which is more frequent than typical solver behavior.
- Tie-Breaking: The efficiency depends on a structured tie-breaking rule.
Future research will explore whether these results hold under more common settings, such as higher decay factors or more randomized tie-breaking strategies.
Summary updated