Computer-Intractability of the Frustration Model of a Spin Glass
C. Bachas. Journal of Physics A: Mathematical and General, 17 (13):
L709(1984)
Zusammenfassung
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.
%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
}