Backbone Fragility and the Local Search Cost Peak

I. P. Gent, J. Singer, A. Smaill

The local search algorithm WSat is one of the most successful algorithms for solving the satisfiability (SAT) problem. It is notably effective at solving hard Random 3-SAT instance…