ON THE COMPUTATIONAL-COMPLEXITY OF ISING SPIN-GLASS MODELS
ON THE COMPUTATIONAL-COMPLEXITY OF ISING SPIN-GLASS MODELS
复制标题
DOI：
10.1088/0305-4470/15/10/028
复制
发表时间：
1982-01-01
期刊：
影响因子：
--
通讯作者：
BARAHONA, F
中科院分区：
文献类型：
--
作者：
BARAHONA, F
研究了具有伊辛自旋的自旋玻璃中磁配分函数的计算和基态的寻找问题。在一个有限的二维晶格中，这些问题可以通过算法来解决，该算法需要由晶格大小的多项式函数限定的多个步骤。与此相反，同样的问题被证明属于NP-难问题的类，无论是在二维的情况下，在磁场内，并在三维的情况下。一个问题的NP难性表明，它是非常不可能的多项式算法可以存在来解决它。
In a spin glass with Ising spins, the problems of computing the magnetic partition function and finding a ground state are studied. In a finite two-dimensional lattice these problems can be solved by algorithms that require a number of steps bounded by a polynomial function of the size of the lattice. In contrast to this fact, the same problems are shown to belong to the class of NP-hard problems, both in the two-dimensional case within a magnetic field, and in the three-dimensional case. NP-hardness of a problem suggests that it is very unlikely that a polynomial algorithm could exist to solve it.