Computing p-presentation distances is hard

Recently, p-presentation distances for p∈ [1,∞] were introduced for merge trees and multiparameter persistence modules as more sensitive variations of the respective interleaving distances (p=∞). 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∈ [1,∞) for both merge trees and t-parameter persistence modules for any t≥ 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.