The University of Edinburgh -
Division of Informatics
Forrest Hill & 80 South Bridge

Research Paper #605

Title:The Enigma of Sat Hill-Climbing Procedures
Authors:Gent,I; Walsh,T
Date:Oct 1992
Presented:Submitted to IJCAI-93
Abstract:In this paper, we investigate a family of hill-climbing procedures related to GSAT, a greedy random hill-climbing procedure for satisfiability. These procedures are able to solve large and difficult satisfiability problems beyond the range of conventional procedures like Davis-Putnam. We explore the role of greediness, randomness and hill-climbing in the effectiveness of these procedures. We show that neither greediness nor randomness is crucial to GSAT's performance, and that hill-climbing's importance is limited to a short initial phase of search. In addition, we observe some remarkable and possibly universal features of their search for a satisfying truth assignment.

[Search These Pages] [DAI Home Page] [Comment]