# Computing p-presentation distances is hard

Håvard Bakke Bjerkevik, Magnus Bakke Botnan

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.