%0 Journal Article %1 bachas84 %A Bachas, C P %D 1984 %J Journal of Physics A: Mathematical and General %K complexity physics spin.glass %N 13 %P L709 %T Computer-Intractability of the Frustration Model of a Spin Glass %U http://stacks.iop.org/0305-4470/17/i=13/a=006 %V 17 %X 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.

@article{bachas84, abstract = {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.}, added-at = {2016-11-13T11:22:17.000+0100}, author = {Bachas, C P}, biburl = {https://www.bibsonomy.org/bibtex/250e6d954b4d4c8668a59e68852d68f4a/ytyoun}, interhash = {858d2caa870080ff5548c838595ec0ef}, intrahash = {50e6d954b4d4c8668a59e68852d68f4a}, journal = {Journal of Physics A: Mathematical and General}, keywords = {complexity physics spin.glass}, number = 13, pages = {L709}, timestamp = {2016-12-29T04:47:55.000+0100}, title = {Computer-Intractability of the Frustration Model of a Spin Glass}, url = {http://stacks.iop.org/0305-4470/17/i=13/a=006}, volume = 17, year = 1984 }