Local search on Random 2+p-SAT
Josh Singer, Ian P. Gent, Alan Smaill · 2000
. Random 2+p-SAT interpolates between the polynomialtime problem Random 2-SAT when p = 0 and the NP-complete problem Random 3-SAT when p = 1. At some value p = p0 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 p0 . 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...