  We show that computing the interleaving distance between two multi-graded
persistence modules is NP-hard. More precisely, we show that deciding whether
two modules are $1$-interleaved is NP-complete, already for bigraded, interval
decomposable modules. Our proof is based on previous work showing that a
constrained matrix invertibility problem can be reduced to the interleaving
distance computation of a special type of persistence modules. We show that
this matrix invertibility problem is NP-complete. We also give a slight
improvement of the above reduction, showing that also the approximation of the
interleaving distance is NP-hard for any approximation factor smaller than $3$.
Additionally, we obtain corresponding hardness results for the case that the
modules are indecomposable, and in the setting of one-sided stability.
Furthermore, we show that checking for injections (resp. surjections) between
persistence modules is NP-hard. In conjunction with earlier results from
computational algebra this gives a complete characterization of the
computational complexity of one-sided stability. Lastly, we show that it is in
general NP-hard to approximate distances induced by noise systems within a
factor of 2.
