Polynomial computability and NP-hardness conjecture for multiparameter persistence distances

Let $n\geq 1$ be fixed, and let $d^p_{\mathcal{M}}$ and $d^p_{\mathcal I}$ denote the corresponding distances on finitely presented $n$-parameter persistence modules, with $d^p_{\mathcal I}$ considered specifically for $2$-parameter modules. Computational complexity conjecture. (i) For fixed $n\geq 1$, the distance $d^p_{\mathcal{M}}$ on finitely presented $n$-parameter persistence modules is exactly computable in polynomial time. (ii) Computing $d^p_{\mathcal I}$ on finitely presented $2$-parameter persistence modules is NP-hard, for all $p\in[1,\infty]$. These computational claims concern the complexity of the distances whose approximation and computation are discussed in the paper; both assertions are left to future work.