Mossel–Weitz–Wormald hardness conjecture for the hardcore model

Let $d\geq 4$, let $\lambda_c(d)$ denote the critical fugacity for the hardcore model on the $d$-regular tree, and let $\lambda$ satisfy $\lambda_c(d)<\lambda$. A fully polynomial approximation scheme (FPTAS) is an algorithm that approximates a partition function to arbitrary relative accuracy in time polynomial in the input size and the inverse accuracy.

Mossel–Weitz–Wormald conjecture. Unless $\mathrm{NP}=\mathrm{RP}$, there does not exist a fully polynomial approximation scheme for the partition function of the hardcore model with fugacity $\lambda$ on graphs of maximum degree at most $d$.

The conjecture links the uniqueness threshold and computational hardness for approximate counting in the hardcore model. It was proposed in the context of exponential mixing-time lower bounds above the threshold; its resolution is not specified in the source.