The Satisability Constraint Gap

We describe an experimental investigation of the satisability phase transition for several dierent classes of randomly generated problems. We show that the \conventional " picture of easy-hard-easy problem diculty is inadequate. In particular, there is a region of very variable problem di-culty where problems are typically underconstrained and satisable. Within this region, problems can be orders of magnitude harder than problems in the middle of the satisability phase transition. These extraordinary hard problems appear to be associated with a constraint gap, a minimum in the amount of constraint propagation compared to the amount of search. We show that the position and shape of this constraint gap are very consist-ent with problem size. Unlike hard problems in the middle of satisability phase transition, hard problems in the variable region are not critically con-strained between satisability and unsatisability. Indeed, hard problems in the variable region often contain a small and unique minimal unsatisable subset or reduce at an early stage in search to a hard unsatisable subprob-lem with a small and unique minimal unsatisable subset. The diculty in solving such problems is thus in identifying the minimal unsatisable subset from the many irrelevant clauses. The existence of a constraint gap greatly hinders our ability to nd such minimal unsatisable subsets. We conjec-ture that these results will generalise both to other SAT problem classes, and to the phase transitions of other NP-hard problems