ECAI-2000 Logo

ECAI-2000 Conference Paper

[PDF] [full paper] [prev] [tofc] [next]

Local Search on Random 2+p-SAT

Josh Singer, Ian P. Gent, Alan Smaill

Random 2+p-SAT interpolates between the polynomial-time problem Random 2-SAT when p = 0 and the NP-complete problem Random 3-SAT when p = 1. At some value p = p_0 ~= 0.41, a dramatic change in the structural nature of instances is predicted by statistical mechanics methods. This is reflected by a change in the typical cost scaling for a complete search method Tableau, seen experimentally. We show empirically the same change of of behaviour in the local search algorithm, Novelty+, a recent variant of WSat. Between p = 0.3 and p = 0.5 we see typical cost scaling of Novelty+ at the 50% satisfiability point apparently change from slow polynomial growth to superpolynomial. That this behaviour is seen in two such different algorithms lends credibility to the hypothesis that there is change of typical-case complexity around p_0. Previous work linked the emergence of a backbone of fully constrained variables to the cost peak seen in Random k-SAT. Initial experiments suggest that for those instances whose cost was typical, backbone size is no larger for p = 0.5 than for p = 0.3, implying that this property is not wholly responsible for any typical cost scaling change. A preliminary study shows that the backbones of instances at p = 0.5 are more sensitive to the removal of clauses than those at p = 0.3. This ``backbone fragility'', which has previously been linked to local search cost, may cause the drastic increase.

Keywords: Search, Constraint satisfaction

Citation: Josh Singer, Ian P. Gent, Alan Smaill: Local Search on Random 2+p-SAT. In W.Horn (ed.): ECAI2000, Proceedings of the 14th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2000, pp.113-117.

[prev] [tofc] [next]

ECAI-2000 is organised by the European Coordinating Committee for Artificial Intelligence (ECCAI) and hosted by the Humboldt University on behalf of Gesellschaft für Informatik.