  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/n^{O(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 {\em 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.
\cite{cai1999hardness} for establishing the average-case hardness of computing
the permanent of a matrix; a list-decoding algorithm of Sudan
\cite{sudan1996maximum}, 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 {\em
real-valued} computational model, e.g. using a Blum-Shub-Smale machine
\cite{blum1988theory} operating over real-valued inputs.

Probability;Statistical Mechanics;Computational Complexity