Introduction
Boolean Satisfiability (SAT)—the task of finding a truth assignment that makes a logic formula true—is the quintessential NP-complete problem. For decades, "complete" algorithms like Davis-Putnam were the gold standard, but they struggled with large, complex instances. In the early 1990s, "incomplete" local search methods like GSAT emerged, capable of solving massive problems by flipping variables to maximize the number of satisfied clauses. However, the underlying reasons for their success remained unclear. Gent and Walsh set out to isolate the specific features of these solvers to find the "secret sauce" of local search.
The GenSAT Framework
The authors introduced GenSAT, a generalized framework for hill-climbing SAT procedures. GenSAT consists of three main components:
- Initial: Generates the starting truth assignment.
- Hill-climb: Identifies a set of "good" candidate variables to flip.
- Pick: Selects one variable from that set to actually flip.
By swapping out these components, the researchers created several novel variants to test the necessity of greediness and randomness:
- TSAT (Timid): Instead of the best possible flip (greedy), it picks the flip that improves the score the least.
- ISAT (Indifferent): Treats all flips that don't decrease the score as equal.
- HSAT (Historical): A deterministic variant where, when faced with multiple equally good flips, it chooses the variable that hasn't been flipped for the longest time.
Key Insights: Greediness vs. History
A major finding of the study is that "greediness" is overrated. The "Timid" (TSAT) and "Cautious" (CSAT) variants performed almost as well as the greedy GSAT, suggesting that as long as a solver moves "up" or "sideways" on the fitness landscape, the exact magnitude of improvement is secondary. Furthermore, randomness is not essential; deterministic tie-breaking or starting positions can be effective provided they offer enough variety.
The most significant breakthrough was HSAT. By simply keeping track of when variables were last flipped and picking the "oldest" one during ties, the solver avoids getting stuck in local cycles. This simple memory mechanism allowed HSAT to navigate "plateaus"—regions where moves don't immediately improve the score—much more effectively than standard greedy approaches.
Performance and Scaling
The study evaluated these algorithms on Random 3-SAT (at the critical $L/N = 4.3$ ratio) and N-Queens problems. The results highlighted a clear dominance for memory-based hill-climbing. On 100-variable random SAT problems, GSAT required an average of 12,600 total flips, while HSAT required only 3,740—a massive improvement in efficiency.
As problem size (N) increases, the performance gap between HSAT and standard GSAT widens significantly. The data suggests that these hill-climbing procedures scale much better than complete algorithms. While Davis-Putnam is strictly exponential, GenSAT variants appear to scale with a "small-exponent" exponential or potentially even a polynomial dependency (roughly $O(N^3)$) for the tested ranges.
Conclusion
The success of local search for SAT lies not in extreme greediness or randomness, but in the fundamental hill-climbing drive and the ability to navigate plateaus. HSAT's use of historical memory provides a powerful, deterministic way to avoid cycles and traverse the search space, pointing the way toward more sophisticated memory-based heuristics in future SAT solver design.
Summary updated