Biased thermodynamics can explain the behaviour of smart optimization algorithms that work above the dynamical threshold

Random constraint satisfaction problems can display a very rich structure in the space of solutions, with often an ergodicity breaking—also known as clustering or dynamical—transition preceding the satisfiability threshold when the constraint-to-variables ratio α is increased. However, smart algorithms start to fail finding solutions in polynomial time at some threshold αalg which is algorithmic dependent and generally bigger than the dynamical one αd. The reason for this discrepancy is due to the fact that αd is traditionally computed according to the uniform measure over all the solutions. Thus, while bounding the region where a uniform sampling of the solutions is easy, it cannot predict the performance of off-equilibrium processes, that are still able of finding atypical solutions even beyond αd. Here we show that a reconciliation between algorithmic behaviour and thermodynamic prediction is nonetheless possible at least up to some threshold α d opt ⩾ α d , which is defined as the maximum value of the dynamical threshold computed on all possible probability measures over the solutions. We consider a simple Monte Carlo-based optimization algorithm, which is restricted to the solution space, and we demonstrate that sampling from the equilibrium distribution of a biased measure improving on αd is still possible even beyond the ergodicity breaking point for the uniform measure, where other algorithms hopelessly enter the out-of-equilibrium regime. The conjecture we put forward is that many smart algorithms sample the solution space according to a biased measure: once this measure is identified, the algorithmic threshold is given by the corresponding ergodicity-breaking transition.