Recently, p-presentation distances for \(p\in [1,\infty ]\) were introduced for merge trees and multiparameter persistence modules as more sensitive variations of the respective interleaving distances ( \(p=\infty )\) . It is well-known that computing the interleaving distance is NP-hard in both cases. We extend this result by showing that computing the p-presentation distance is NP-hard for all \(p\in [1,\infty )\) for both merge trees and t-parameter persistence modules for any \(t\ge 2\) . Though the details differ, both proofs follow the same novel strategy, suggesting that our approach can be adapted to proving the NP-hardness of other distances based on sums or p-norms.
