Can we predict the difficulty of optimization problems without solving them?

Surprisingly often. Based on previous results of a large-scale numerical study of the equilibrium three-dimensional Edwards-Anderson Ising spin glass where it was demonstrated that autocorrelation times are directly correlated with the roughness of the free-energy landscape [Phys. Rev. E 87, 012104 (2013)], we show that a generalized spin-glass order parameter can be used as a proxy to the computational difficulty of various paradigmatic optimization problems. Our results are illustrated with different optimization algorithms, as well as optimization problems. Furthermore, we show numerical evidence that the order-parameter distribution does mirror salient features in the free-energy landscape of complex systems for moderate system sizes.