A New Method for Solving Hard Satisfiability Problems

Bart Selman, Hector J. Levesque, David G. MitchellAAAI 1992 · OpenReview

Abstract

We introduce a greedy local search procedure called GSAT for solving propositional satisfiability problems. Our experiments show that this procedure can be used to solve hard, randomly generated problems that are an order of magnitude larger than those that can be handled by more traditional approaches such as the Davis-Putnam procedure or resolution. We also show that GSAT can solve structured satisfiability problems quickly. In particular, we solve encodings of graph coloring problems, N-queens, and Boolean induction. General application strategies and limitations of the approach are also discussed. GSAT is best viewed as a model-finding procedure. Its good performance suggests that it may be advantageous to reformulate reasoning tasks that have traditionally been viewed as theorem-proving problems as model-finding tasks.

Introduction

Propositional satisfiability (SAT)—determining if there exists a truth assignment that satisfies a given Boolean formula—is the foundational NP-complete problem. Historically, the Davis-Putnam (DP) procedure, a systematic backtracking search, served as the benchmark for SAT solving. While DP is complete, its exponential scaling limits its application to relatively small problem instances. This paper introduces GSAT, a randomized local search algorithm that trades completeness for significant gains in speed and scalability, reframing SAT as a model-finding task rather than a theorem-proving one.

The GSAT Algorithm

GSAT operates on formulas in Conjunctive Normal Form (CNF) using a simple yet effective greedy heuristic. The procedure follows these steps:

  1. Initialization: Assign random truth values to all variables.
  2. Greedy Flip: Identify the variable whose flip (True to False or vice versa) results in the largest increase in the total number of satisfied clauses.
  3. Sideways Moves: If no flip increases the satisfied count, GSAT performs a "sideways move" by flipping a variable that maintains the current number of satisfied clauses.
  4. Restarts: If a solution is not found within a set number of flips (MAX-FLIPS), the algorithm restarts with a new random assignment for a maximum number of tries (MAX-TRIES).

Experimental Evaluation

Performance on Random 3CNF Formulas

The authors evaluated GSAT against the DP procedure using hard random 3CNF formulas at the "phase transition" point (where the ratio of clauses to variables is approximately 4.3). As shown in Figure 1, GSAT demonstrates superior scaling. While the DP procedure becomes computationally prohibitive at 140 variables (taking 4.7 hours), GSAT solves 500-variable instances in approximately 1.6 hours.

Comparison of GSAT and Davis-Putnam (DP) performance on hard random 3CNF formulas, showing GSAT's superior scaling as variables increase.

Structured Problems

Beyond random formulas, GSAT was tested on structured benchmarks:

  • N-Queens: GSAT solved the 100-queens problem (encoded with 10,000 variables and 1.6 million clauses) in just 195 seconds.
  • Graph Coloring: The algorithm successfully found an 18-coloring for a difficult 125-vertex graph in 5 hours, a task DP could not complete.
  • Boolean Induction: GSAT outperformed traditional methods on logic circuit synthesis tasks.

The Power of Sideways Moves

A critical technical insight of this work is the necessity of "sideways moves." In many search spaces, the algorithm reaches a plateau where no single flip improves the objective function. By allowing moves that do not decrease the number of satisfied clauses, GSAT can navigate these plateaus to find a path toward a global solution. As illustrated in Figure 4, enabling sideways moves dramatically increases the percentage of problems solved and reduces the time required, particularly for larger or more structured instances like the N-queens problem.

The impact of sideways moves on GSAT performance, demonstrating that allowing moves that do not immediately improve the score is essential for solving hard instances.

Conclusion

GSAT represents a paradigm shift in SAT solving by demonstrating that local search can handle problems an order of magnitude larger than systematic methods. While the algorithm is incomplete—meaning it cannot prove a formula is unsatisfiable—its efficiency makes it a powerful tool for practical AI reasoning tasks. This success suggests that many traditional theorem-proving tasks in AI, such as planning and diagnosis, may be more effectively solved by reframing them as model-finding problems.

Summary updated

Abstract

We introduce a greedy local search procedure called GSAT for solving propositional satisfiability problems. Our experiments show that this procedure can be used to solve hard, randomly generated problems that are an order of magnitude larger than those that can be handled by more traditional approaches such as the Davis-Putnam procedure or resolution. We also show that GSAT can solve structured satisfiability problems quickly. In particular, we solve encodings of graph coloring problems, N-queens, and Boolean induction. General application strategies and limitations of the approach are also discussed. GSAT is best viewed as a model-finding procedure. Its good performance suggests that it may be advantageous to reformulate reasoning tasks that have traditionally been viewed as theorem-proving problems as model-finding tasks.
BibTeX
@inproceedings{selman1992new,
  author = {Bart Selman and Hector J. Levesque and David G. Mitchell},
  title = {{A New Method for Solving Hard Satisfiability Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
  url = {https://openreview.net/forum?id=HJ-w6TlOWH},
}
Figure