Easy Problems are Sometimes Hard

Research output: Contribution to journalArticlepeer-review

73 Citations (Scopus)

Abstract

We present a detailed experimental investigation of the easy-hard-easy phase transition for randomly generated instances of satisfiability problems. Problems in the hard part of the phase transition have been extensively used for benchmarking satisfiability algorithms. This study demonstrates that problem classes and regions of the phase transition previously thought to be easy can sometimes be orders of magnitude more difficult than the worst problems in problem classes and regions of the phase transition considered hard. These difficult problems are either hard unsatisfiable problems or are satisfiable problems which give a hard unsatisfiable subproblem following a wrong split. Whilst these hard unsatisfiable problems may have short proofs, these appear to be difficult to find, and other proofs are long and hard.

Original languageEnglish
Pages (from-to)335-345
Number of pages11
JournalArtificial Intelligence
Volume70
Publication statusPublished - Oct 1994

Fingerprint

Dive into the research topics of 'Easy Problems are Sometimes Hard'. Together they form a unique fingerprint.

Cite this