  The class of two-spin systems contains several important models, including
random independent sets and the Ising model of statistical physics. We show
that for both the hard-core (independent set) model and the anti-ferromagnetic
Ising model with arbitrary external field, it is NP-hard to approximate the
partition function or approximately sample from the model on d-regular graphs
when the model has non-uniqueness on the d-regular tree. Together with results
of Jerrum--Sinclair, Weitz, and Sinclair--Srivastava--Thurley giving FPRAS's
for all other two-spin systems except at the uniqueness threshold, this gives
an almost complete classification of the computational complexity of two-spin
systems on bounded-degree graphs.
  Our proof establishes that the normalized log-partition function of any
two-spin system on bipartite locally tree-like graphs converges to a limiting
"free energy density" which coincides with the (non-rigorous) Bethe prediction
of statistical physics. We use this result to characterize the local structure
of two-spin systems on locally tree-like bipartite expander graphs, which then
become the basic gadgets in a randomized reduction to approximate MAX-CUT. Our
approach is novel in that it makes no use of the second moment method employed
in previous works on these questions.
