I am also kind of out of my depth here (Devac, care to chime in if what follows is way off track?), but to my knowledge the interesting bit is here:

Having a “sign problem” thus means that no local transformation that removes the signs and phases is possible. Notably, the definition of a sign problem must involve the notion of locality [see also the study of Hastings (7)]. By performing a nonlocal transformation on the physical degrees of freedom, one can always diagonalize the Hamiltonian and obtain a classical partition function. However, such a transformation requires computational resources that scale exponentially with the system size.

The problem of performing a nonlocal transformation is in NP: if you knew the exact set of steps to take when performing the transformation, you could do it in polynomial time --- but nobody knows whether or not you can compute the steps to take in polynomial time. What we have now is an exponential-time algorithm for finding those steps --- in this case, diagonalizing the Hamiltonian.