Introduction
Modern Boolean Satisfiability (SAT) solvers primarily utilize the Conflict-Driven Clause Learning (CDCL) framework. While highly effective, CDCL is theoretically bounded by the Resolution proof system. This limitation imposes a "speed limit" on certain problem classes, such as the Pigeonhole Principle or XOR-SAT, where any Resolution-based proof grows exponentially in size.
To bypass this bottleneck, this research explores Extended Resolution (ER), a more powerful system that allows solvers to introduce new variables representing logical combinations of existing ones (e.g., $z \iff x \lor y$). While ER can reduce exponential proofs to polynomial ones, its implementation is challenging due to the infinite search space for new variables. This paper introduces Local Extended Resolution (LER), a restricted, computationally efficient version of ER that automatically discovers useful variable extensions.
Methodology: Local Extended Resolution (LER)
LER is designed to be a conservative extension of CDCL. Rather than searching the entire space of possible variables, LER uses the solver's own search history to identify candidates.
The "Window of One" Heuristic
The solver monitors the sequence of clauses learned during conflict analysis. If two consecutive learned clauses share a common sub-structure—for instance, $l_1 \lor \alpha$ and $l_2 \lor \alpha$—the solver introduces a new variable $z$ to represent the disjunction $l_1 \lor l_2$. This heuristic targets logical redundancies directly visible in the proof trace.
Clause Substitution and Resource Management
Once a new variable $z$ is defined, the solver actively replaces occurrences of $(l_1 \lor l_2)$ with $z$ in subsequent learned clauses, effectively compressing the proof. To prevent memory bloat and performance degradation, the authors treat these extended variables as dynamic resources. Variables with low activity (measured by the VSIDS heuristic) are periodically deleted, similar to the garbage collection of "useless" learned clauses.
These techniques were implemented in the state-of-the-art solvers of the time, resulting in MiniSater (based on MiniSat) and GlucoseR (based on Glucose).
Experimental Evaluation
The solvers were evaluated on two primary datasets:
- Competition Benchmarks: 234 instances from SAT 2007 and 292 from SAT 2009, representing real-world applications like formal verification.
- Hard Theoretical Instances: Problems known to be difficult for standard resolution, including Pigeonhole Principle encodings and Urquhart problems.
Results and Discussion
The implementation of LER yielded significant performance improvements, particularly on instances that typically trigger exponential behavior in standard solvers.
As shown in Table 1, GlucoseR and MiniSater consistently outperformed their base versions. On the SAT 2009 application set, GlucoseR solved 213 instances, surpassing the 211 solved by the standard Glucose solver. While the numerical increase in competition benchmarks is modest, it represents the successful resolution of previously "unsolvable" instances within the time limit.
The most dramatic results were observed on theoretical benchmarks. Standard solvers like PrecoSAT and MiniSat often timed out on Urquhart problems. In contrast, the LER-enabled solvers solved these instances in seconds or minutes.
Table 2 details how LER allows solvers to bypass Resolution bottlenecks. For example, on Urq3_5, GlucoseR required only 8 seconds compared to the 21 seconds for Glucose, and it successfully solved Urq5_5 where others failed. The data also confirms that the solver frequently branches on these new "extended" variables, proving that the heuristic identifies high-impact logical structures.
Conclusion
Local Extended Resolution provides a practical bridge between the efficiency of CDCL and the power of Extended Resolution. By using the proof trace to guide variable introduction and employing aggressive resource management, the authors demonstrated that solvers can automatically simplify complex proofs.
However, LER is not a universal solution; for instance, standard Pigeonhole Principle problems still require specialized branching heuristics to fully leverage the new variables. Future research will focus on more aggressive variable introduction heuristics and exploring the theoretical limits of LER within the hierarchy of proof complexity.
Summary updated