The hardcore model is a model of lattice gas systems which has received much
attention in statistical physics, probability theory and theoretical computer
science. It is the probability distribution over independent sets $I$ of a
graph weighted proportionally to $\lambda^{|I|}$ with fugacity parameter
$\lambda$. We prove that at the uniqueness threshold of the hardcore model on
the $d$-regular tree, approximating the partition function becomes
computationally hard on graphs of maximum degree $d$.
Specifically, we show that unless NP$=$RP there is no polynomial time
approximation scheme for the partition function (the sum of such weighted
independent sets) on graphs of maximum degree $d$ for fugacity $\lambda_c(d) <
\lambda < \lambda_c(d) + \epsilon(d)$ where $\lambda_c =
\frac{(d-1)^{d-1}}{(d-2)^d}$ is the uniqueness threshold on the $d$-regular
tree and $\epsilon(d)>0$. Weitz produced an FPTAS for approximating the
partition function when $0<\lambda < \lambda_c(d)$ so this result demonstrates
that the computational threshold exactly coincides with the statistical physics
phase transition thus confirming the main conjecture of [28]. We further
analyze the special case of $\lambda=1, d=6$ and show there is no polynomial
time algorithm for approximately counting independent sets on graphs of maximum
degree $d= 6$ which is optimal.
Our proof is based on specially constructed random bi-partite graphs which
act as gadgets in a reduction to MAX-CUT. Building on the second moment method
analysis of [28] and combined with an analysis of the reconstruction problem on
the tree our proof establishes a strong version of 'replica' method heuristics
developed by theoretical physicists. The result establishes the first rigorous
correspondence between the hardness of approximate counting and sampling with
statistical physics phase transitions.

证明了在 $d$- 正则树上 hardcore 模型的唯一性阈值处计算配分函数在最大度数为 $d$ 的图上变得计算困难。通过随机二分图构造，结合重构问题分析和第二时刻方法，建立了定量的统计物理阶段转变计数难度和取样难度的强耦合关系。