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

Abstract 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:msubsup> <mml:mi>α</mml:mi> <mml:mtext>d</mml:mtext> <mml:mtext>opt</mml:mtext> </mml:msubsup> <mml:mtext>⩾</mml:mtext> <mml:msub> <mml:mi>α</mml:mi> <mml:mtext>d</mml:mtext> </mml:msub> </mml:mrow> </mml:math> , 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.