The Complexity of Computing Averages
summary
Computing exact averages — mean magnetization and mean energy for the Ising model, plus average sizes of matchings and independent sets — is #P-hard under the given parameter regimes (ferromagnetic Ising except the zero-field point, and analogous matching/independent-set cases). The proofs use complex-zero analysis (notably Lee–Yang zeros on unit circle plus Gauss–Lucas and an Asano-style induction) to rule out common factors and enable rational interpolation, and a complementary method that recovers log Z by symbolic integration of log partition function via interpolation and partial‑fraction reconstruction; both reductions are constructive and succeed where their model assumptions hold.
AI-written summary · about