Davis-Putnam-Logemann-Loveland (DPLL) Algorithm

The pure literal rule is a preprocessing and in-search simplification step. A literal is pure if it appears in the formula, but its negation does not appear anywhere.

• A pure literal can always be assigned TRUE without risk of causing a conflict, as no clause requires its negation to be true.
• The algorithm can safely delete all clauses containing that pure literal, as they are already satisfied.
• While powerful in some theoretical cases, its practical impact in modern solvers is often limited compared to unit propagation. Some DPLL implementations omit it for simplicity.

The order in which variables are chosen for assignment (decision variables) critically impacts performance. Early DPLL implementations used simple heuristics; modern descendants use sophisticated ones. Classic strategies include:

• Maximum Occurrence: Choose the variable that appears most frequently in the current formula.
• Two-Clause Preference: Favor variables that appear in many short (especially binary) clauses.
• Random Selection: A simple baseline. The lack of effective heuristics was a major limitation of early DPLL, later addressed by Conflict-Driven Clause Learning (CDCL) solvers which use activity-based heuristics derived from conflict analysis.

DPLL is the direct precursor to the Conflict-Driven Clause Learning (CDCL) architecture that dominates modern SAT solving. CDCL enhances DPLL with two revolutionary ideas:

1. Clause Learning: Upon conflict, analyze the reason for the contradiction to derive a new clause that prevents the same dead-end in the future.
2. Non-Chronological Backtracking (Backjumping): Instead of backtracking one level, use the learned clause to jump back to the decision level that caused the conflict. While pure DPLL uses chronological backtracking and lacks learning, its core loop of decision, propagation, and backtrack remains the skeleton upon which CDCL is built.

DPLL is both sound and complete, which are its defining theoretical guarantees.

• Soundness: If the algorithm returns SATISFIABLE, the provided assignment is guaranteed to satisfy the input formula. It never returns a false positive.
• Completeness: If a satisfying assignment exists, the algorithm will eventually find it. If the formula is unsatisfiable, the algorithm will exhaust the search space and return UNSATISFIABLE. This contrasts with incomplete methods (like local search) which may find solutions quickly but cannot prove unsatisfiability. DPLL's completeness makes it essential for applications requiring proofs of impossibility, such as formal verification.

Backtracking search is a fundamental, complete depth-first search algorithm for solving constraint satisfaction problems (CSPs) and SAT. It operates by:

• Building partial assignments incrementally, one variable at a time.
• Checking constraints at each step. If the current partial assignment violates a constraint, the algorithm abandons (prunes) this branch.
• Backtracking to the most recent decision point to try a different assignment when a dead-end is reached. DPLL is a highly optimized form of backtracking search for SAT that integrates unit propagation (a constraint propagation technique) and pure literal elimination to drastically reduce the search space before resorting to backtracking.

Constraint propagation is a family of inference techniques used during search to reduce the problem's search space by using the constraints to eliminate values that cannot be part of any solution. In the context of DPLL and SAT solving, the primary propagation technique is unit propagation:

• If a clause is a unit clause (contains only one unassigned literal), that literal must be assigned TRUE to satisfy the clause.
• This assignment is forced, and its implications are propagated through other clauses, potentially creating new unit clauses in a cascade. This process, also called the Boolean Constraint Propagation (BCP) component of DPLL, is critical for its efficiency. In general CSPs, analogous techniques include enforcing node, arc, and path consistency.

Satisfiability Modulo Theories (SMT) extends the Boolean SAT problem by asking whether a first-order logic formula is satisfiable with respect to one or more background theories. These theories define the semantics of domains like:

• Linear Integer/Real Arithmetic (e.g., x + 2*y > 5)
• Bit Vectors (for modeling hardware)
• Arrays
• Uninterpreted Functions An SMT solver, such as Z3 or CVC5, typically uses a CDCL-based SAT solver as its core engine. The SAT solver handles the Boolean structure of the formula, while dedicated theory solvers check the consistency of assignments within their specific theory. The solvers cooperate via the DPLL(T) framework, a generalization of the DPLL algorithm that integrates theory reasoning.

While DPLL provides the backtracking framework, modern solvers rely heavily on heuristics to guide the search. Two critical heuristic classes are:

• Variable Selection Heuristics: Deciding which unassigned variable to branch on next. The VSIDS (Variable State Independent Decaying Sum) heuristic, used in CDCL solvers, dynamically prioritizes variables involved in recent conflicts.
• Phase Selection Heuristics: Deciding whether to first try assigning TRUE or FALSE to the chosen variable. The phase saving heuristic remembers the last successful assignment for a variable across backtracking. These heuristics are essential for performance. In contrast, classic DPLL often used simpler heuristics like the Maximum Occurrences in clauses of Minimum Size (MOMS).