Critical Slowing Down in Polynomial Time Algorithms

Abstract

Combinatorial optimization algorithms that compute exact ground states for disordered magnets are seen to exhibit critical slowing down at zero temperature phase transitions. Using the physical features of the models, such as vanishing stiffness on one side of the transition and the ground state degeneracy, the number of operations needed in the push-relabel algorithm for the random field Ising model and in the algorithm for the 2D spin glass is estimated. These results strengthen the connections between algorithms and the physical picture and may be used to improve the speed of computations.