Structure of best possible strategies for finding ground states

Finding the ground state of a system with a complex energy landscape is important for many physical problems including protein folding, spin glasses, chemical clusters, and neural networks. Such problems are usually solved by heuristic search methods whose efficacy is judged by empirical performance on selected examples. We present a proof that for a wide range of objective functions threshold accepting is the best possible strategy within a large class of algorithms that simulate random walks on the landscape. In particular, it can perform better than simulated annealing, Tsallis and Glauber statistics.