The University of Edinburgh -
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
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.

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