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

Research Paper #680

Title:The Hardest Random Sat Problems
Authors:Gent,I; Walsh,T
Date:Jan 1994
Presented:Submitted to AAAI-94
Keywords:
Abstract:We describe a detailed experimental investigation of the phase transition for several different classes of satisfiability problems including random k-SAT, the constant probability model, and encodings of k-colourability and the independent set problem. We show that the conventional picture of easy-hard-easy behaviour is inadequate. in each of the problem classes, although median problem difficulty shows an easy-hard-easy pattern, there is also a region of very variable problem difficulty. Within this region, we have found problems orders of magnitude harder than those in the middle of the phase transition. These extraordinary problems can easily dominate the man problem difficulty. We report experimental evidence which strongly suggests that this behaviour is due to a "constraint gap", a region where the number of constraints on variables is minimal while simultaneously the depth of search required to solve problems is maximal. We also report results suggesting that better algorithms will be unable to eliminate this constraint gap and hence will continue to find very difficult problems in this region. Finally, we report an interesting correlation between these variable regions and a peak in the number of prime implicates. We predict that these extraordinarily hard problems will be of considerable use in analysing and comparing the performance of satisfiability algorithms.
Download:POSTSCRIPT COPY

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