solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看6160次
Computing the partition function of the Sherrington-Kirkpatrick model is hard on average. (arXiv:1810.05907v1 [math.PR])
来源于:arXiv
We consider the algorithmic problem of computing the partition function of
the Sherrington-Kirkpatrick model of spin glasses with Gaussian couplings. We
show that there is no polynomial time algorithm for computing the partition
function exactly (in the sense to be made precise), unless P=\#P. Our proof
uses the Lipton's reducibility trick of computation modulo large
primes~\cite{lipton1991new} and near-uniformity of the log-normal distribution
in small intervals. To the best of our knowledge, this is the first statistical
physics model with random parameters for which such average case hardness is
established. 查看全文>>