Speaking roughly, spin glasses exist because nature itself can't solve the minimization problem. Here's a book on the topic: http://press.princeton.edu/titles/9917.html

In general, minimising a problem with the universal electron-correlation functional is known to in NP due to this [1]. Which is kind of sad for density functional theory (DFT). I've probably misphrased that.

Also, side remark: Coding up a 2D Ising model solver with Metropolis-Hastings is surprisingly fun. Doubly so if you GPU accelerate it.

[1] http://www.nature.com/nphys/journal/v5/n10/abs/nphys1370.htm...

I think I see where you're coming from, but in every case where this has been hypothesized so far (e.g. soap bubbles a few years ago) it has been shown to be false. Mostly, physical phenoma result in purely local minima/maxima -- which is generally useless for solving NP-complete problems. At least that's my intuition.