  Finding the ground state energy of the Heisenberg Hamiltonian is an important
problem in the field of condensed matter physics. In some configurations, such
as the antiferromagnetic translationally-invariant case on the 2D square
lattice, its exact ground state energy is still unknown. We show that finding
the ground state energy of the Heisenberg model cannot be an NP-Hard problem
unless P=NP. We prove this result using a reduction to a sparse set and certain
theorems from computational complexity theory. The result hints at the
potential tractability of the problem and encourages further research towards a
positive complexity result. In addition, we prove similar results for many
similarly structured Hamiltonian problems, including certain forms of the
Ising, t-J, and Fermi-Hubbard models.
