Division of Informatics
Forrest Hill & 80 South Bridge
Research Paper #642 | |
|---|---|
| Title: | Easy Problems are Sometimes Hard |
| Authors: | Gent,I; Walsh,T |
| Date: | Jun 1993 |
| Presented: | |
| Keywords: | |
| Abstract: | We present a detailed experimental investigation of the phase transition from satisfiable to unsatisfiable for randomly generated instances of SAT problems. This study demonstrates that problems in classes previously thought to be 'easy' can sometimes be orders of magnitude more difficult than the worst problems in classes considered 'hard'. This result explains the large variability in problem difficulty observed in these 'easy' classes. We present evidence which suggests that this phenomenon cannot be eliminated by the use of better heuristics. These difficult problems appear to be fundamentally hard or to contain subproblems that are fundamentally hard. |
| 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}