The bulk spectral gap is RE-complete: certifiable from above, uncomputable from below
What can algorithms tell us about spectral gaps in quantum many-body systems? We construct certified upper bounds and show why no general algorithm can compute them from below.
