A theory of non-equilibrium local search on random satisfaction problems

Erik Aurell, Eduardo Domínguez, David Machado +1

We study local search algorithms to solve instances of the random $k$-satisfiabi lity problem, equivalent to finding (if they exist) zero-energy ground states of statistical models…