Computing $p$-presentation distances is hard
<|reference_start|>Computing $p$-presentation distances is hard: 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\geq 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.<|reference_end|>
@article{bjerkevik2024computing,
    title={Computing $p$-presentation distances is hard},
    author={H{aa}vard Bakke Bjerkevik, Magnus Bakke Botnan},
    journal={arXiv preprint arXiv:2403.07200},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.07200},
    primaryClass={cs.CG cs.CC math.RT}
}