  We study the complexity of finding the ground state energy density of a local
Hamiltonian on a lattice in the thermodynamic limit of infinite lattice size.
We formulate this rigorously as a function problem, in which we request an
estimate of the ground state energy density to some specified precision; and as
an equivalent promise problem, $\mathsf{GSED}$, in which we ask whether the
ground state energy density is above or below specified thresholds.
  The ground state energy density problem is unusual, in that it concerns a
single, fixed Hamiltonian in the thermodynamic limit, whose ground state energy
density is just some fixed, real number. The only input to the computational
problem is the precision to which to estimate this fixed real number,
corresponding to the ground state energy density. Hardness of this problem for
a complexity class therefore implies that the solutions to all problems in the
class are encoded in this single number (analogous to Chaitin's constant in
computability theory).
  This captures computationally the type of question most commonly encountered
in condensed matter physics, which is typically concerned with the physical
properties of a single Hamiltonian in the thermodynamic limit. We show that for
classical, translationally invariant, nearest neighbour Hamiltonians on a 2D
square lattice,
$\mathsf{P}^{\mathsf{NEEXP}}\subseteq\mathsf{EXP}^{\mathsf{GSED}}\subseteq
\mathsf{EXP}^{\mathsf{NEXP}}$, and for quantum Hamiltonians
$\mathsf{P}^{\mathsf{NEEXP}}\subseteq\mathsf{EXP}^{\mathsf{GSED}}\subseteq
\mathsf{EXP}^{\mathsf{QMA}_{EXP}}$. With some technical caveats on the oracle
definitions, the $\mathsf{EXP}$ in some of these results can be strengthened to
$\mathsf{PSPACE}$. We also give analogous complexity bounds for the function
version of $\mathsf{GSED}$.
