BriefGPT.xyz
Aug, 2024
格罗莫夫-瓦瑟斯坦距离的NP难度
The NP-hardness of the Gromov-Wasserstein distance
HTML
PDF
Natalia Kravtsova
TL;DR
本文探讨了格罗莫夫-瓦瑟斯坦（GW）距离的NP难度问题，填补了文献中对该性质的不足说明。研究指出GW优化问题的非凸性质直接导致其NP难度，并通过多个具体示例进一步阐释了这一非凸性。研究结果有助于理解GW距离在有限空间中的复杂性，具有重要的理论意义。
Abstract
This note addresses the property frequently mentioned in the literature that the
Gromov-Wasserstein
(GW) distance is NP-hard. We provide the details on the non-convex nature of the GW
optimization
problem that im
→