solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看3299次
Computational Complexity of the Interleaving Distance. (arXiv:1712.04281v1 [cs.CG])
来源于:arXiv
The interleaving distance is arguably the most prominent distance measure in
topological data analysis. In this paper, we provide bounds on the
computational complexity of determining the interleaving distance in several
settings. We show that the interleaving distance is NP-hard to compute for
persistence modules valued in the category of vector spaces. In the specific
setting of multidimensional persistent homology we show that the problem is at
least as hard as a matrix invertibility problem. Persistence modules valued in
the category of sets are also studied. As a corollary, we obtain that the
isomorphism problem for Reeb graphs is graph isomorphism complete. 查看全文>>