  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 with disorder on random hypergraphs. It is
well known that the best such algorithms are akin to non-equilibrium processes
in a high-dimensional space. In particular, algorithms known as focused, and
which do not obey detailed balance, outperform simulated annealing and related
methods in the task of finding the solution to a complex satisfiability
problem, that is to find (exactly or approximately) the minimum in a complex
energy landscape. A physical question of interest is if the dynamics of these
processes can be well predicted by the well-developed theory of equilibrium
Gibbs states. While it has been known empirically for some time that this is
not the case, an alternative systematic theory that does so has been lacking.
In this paper we introduce such a theory based on the recently developed
technique of cavity master equations and test it on the paradigmatic random
$3$-satisfiability problem. Our theory predicts the solution process very
accurately away from the algorithm phase boundary and also predicts the
qualitative form of this boundary.
