3 ms·
I'm thinking now that maybe there could be a magnetic material solving an NP-problem
by raverbashing 11y ago
I'm thinking now that maybe there could be a magnetic material solving an NP-problem
- GFK_of_xmaspast 11y agoSpeaking 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 http://press.princeton.edu/titles/9917.html
- tfgg 11y agoIn 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.html http://www.nature.com/nphys/journal/v5/n10/abs/nphys1370.htm...
- lomnakkus 11y agoI 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.