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

Understand

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 $\alpha$ is increased.

• However, smart algorithms start to fail finding solutions in polynomial time at some threshold $\alpha_{\rm alg}$ which is algorithmic dependent and generally bigger than the dynamical one $\alpha_d$.
• The reason for this discrepancy is due to the fact that $\alpha_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 $\alpha_d$.