Computer-Intractability of the Frustration Model of a Spin Glass

. Journal of Physics A: Mathematical and General 17 (13): L709 (1984)


The author proves that finding a ground state of the three-dimensional frustration model of a spin glass is an NP-complete optimisation problem, and hence probably intractable in the sense that no algorithm requiring a time bounded by a polynomial of the volume can exactly solve it.

Links and resources

BibTeX key:
search on:

Comments and Reviews  

There is no review or comment yet. You can write one!


Cite this publication