Mathematically, this is in the land of linear algebra (complex vector spaces.) The particular question at hand concerns the spectrum of a (Hermitian) linear operator, known as "the Hamiltonian". The "gap" refers to a separation in the lowest two eigenvalues ("energy levels") of this operator.

It seems plausible that one could easily encode a turing incomplete problem into linear algebra (think of tensor networks, constraint satisfaction, etc.) but what these guys have done is place very strong restrictions on the form of the linear operator (in jargon: two dimensional, nearest neighbour interactions, translational invariance). This now comes near to a class of physical systems that one may hope to build, or at least understand theoretically, and the result of the paper puts a stark upper limit on what we may hope to achieve in this vein.