COMPUTING THE PARTITION FUNCTION OF THE SHERRINGTON-KIRKPATRICK MODEL IS HARD ON AVERAGE

• 成果类型: Article
• 署名作者: Gamarnik, David; Kizildag, Eren C.
• 署名单位: Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/20-AAP1625
• 发表日期: 2021
• 页码: 1474-1504
• 关键词: COMPUTATIONAL-COMPLEXITY

摘要

We establish the average-case hardness of the algorithmic problem of exact computation of the partition function associated with the Sherrington-Kirkpatrick model of spin glasses with Gaussian couplings and random external field. In particular, we establish that unless P = #P, there does not exist a polynomial-time algorithm to exactly compute the partition function on average. This is done by showing that if there exists a polynomial time algorithm, which exactly computes the partition function for inverse polynomial fraction (1/ nO(1)) of all inputs, then there is a polynomial time algorithm, which exactly computes the partition function for all inputs, with high probability, yielding P = #P. The computational model that we adopt is finite-precision arithmetic, where the algorithmic inputs are truncated first to a certain level N of digital precision. The ingredients of our proof include the random and downward self-reducibility of the partition function with random external field; an argument of Cai et al. (In STACS 99 (Trier) (1999) 90-99 Springer) for establishing the average-case hardness of computing the permanent of a matrix; a list-decoding algorithm of Sudan (In 37th Annual Symposium on Foundations of Computer Science (Burlington, VT, 1996) (1996) 164-172 IEEE Comput. Soc. Press), for reconstructing polynomials intersecting a given list of numbers at sufficiently many points; and near-uniformity of the log-normal distribution, modulo a large prime p. To the best of our knowledge, our result is the first one establishing a provable hardness of a model arising in the field of spin glasses. Furthermore, we extend our result to the same problem under a different real-valued computational model, for example, using a Blum-Shub-Smale machine (In [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science (1988) 387-397 IEEE) operating over real-valued inputs. We establish that, if there exists a polynomial time algorithm which exactly computes the partition function for 3/4 + 1/n(O(1)) fraction of all inputs, then there exists a polynomial time algorithm, which exactly computes the partition function for all inputs, with high probability, yielding P = #P. Our proof uses the random self-reducibility of the partition function, together with a control over the total variation distance for log-normal random variables in presence of a convex perturbation, and the Berlekamp-Welch algorithm.