The backtracking survey propagation algorithm for solving random K-SAT problems

Discrete combinatorial optimization has a central role in many scientific disciplines, however,for hard problems we lack linear time algorithms that would allow us to solve very largeinstances. Moreover, it is still unclear what are the key features that make a discretecombinatorial optimization problem hard to solve. Here we study randomK-satisfiabilityproblems withK¼3,4, which are known to be very hard close to the SAT-UNSAT threshold,where problems stop having solutions. We show that the backtracking survey propagationalgorithm, in a time practically linear in the problem size, is able to find solutions very close tothe threshold, in a region unreachable by any other algorithm. All solutions found have nofrozen variables, thus supporting the conjecture that only unfrozen solutions can be found inlinear time, and that a problem becomes impossible to solve in linear time when all solutionscontain frozen variables.