A new method for solving hard satisfiability problems
Bart Selman, Hector J. Levesque, David G. M. Mitchell · 1992
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 The property of NP-hardness is traditionally taken to be the barrier separating tasks that can be solved computationally with realistic resources fro...
Cited by 1,175 works.
Authors
References
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- The complexity of theorem-proving procedures
- A Computing Procedure for Quantification Theory
- Hard and easy distributions of SAT problems
- Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
- Planning as satisfiability
- Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
- Making believers out of computers
- On selecting a satisfying truth assignment
- Efficient local search for very large-scale satisfiability problems