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 |
| Keywords: | |
| 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. |
| Download: | POSTSCRIPT COPY |
![[Search These Pages]](http://www.dai.ed.ac.uk/icons/dai_search.gif){kind=icon}
![[DAI Home Page]](http://www.dai.ed.ac.uk/icons/dai_home.gif){kind=icon}
![[Comment]](http://www.dai.ed.ac.uk/icons/dai_comment.gif){kind=icon}