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.