Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs
The effectiveness of stochastic algorithms based on Monte Carlo dynamics in solving hard optimization problems is mostly unknown. Beyond the basic statement that at a dynamical phase transition the ergodicity breaks and a Monte Carlo dynamics cannot sample correctly the probability distribution in times linear in the system size, there are almost no predictions or intuitions on the behavior of this class of stochastic dynamics.