arXiv:2604.26972cs.CCcs.LG2026-04

证明连续聚类的四个基本问题中两个是难解的,另两个仍待研究。

How Hard Is Continuous Clustering? Lower Bounds from the Existential Theory of the Reals

  • 基于多项式密度函数,分析聚类结构的存在性
  • 分离点与谷值检测问题等价于实数存在理论难题
  • 拓扑相关问题复杂度未知,需突破代数几何

本文研究在连续概率密度上直接定义的聚类问题的计算难度。假设密度由多项式给出,考察四个自然问题:是否存在若干高密度点彼此相距甚远;两个高密度点之间是否存在低密度中点(形成谷值);密度高于阈值的区域是否至少有给定数量的连通分支;该区域是否包含无法收缩的环(即洞)。研究证明,前两个问题——分离点检测与谷值检测——恰好等价于实数存在理论(existential theory of the reals),该复杂度类包含NP且被认为严格更大。后两个拓扑问题——连通分支计数与洞检测——至少与实数存在理论一样难,但其精确复杂度仍悬而未决。将其归入该类需实代数几何的重大进展。这些结果首次对实多项式层次内的精确连续聚类问题进行了严谨分类,也表明即使基础聚类准则也不属于NP完全,除非出现意外的复杂度坍塌。

原文摘要 · Abstract (English)

This paper studies the computational difficulty of clustering problems that are defined directly on a continuous probability density. Rather than working with finite samples, we assume the density is given as a polynomial and ask whether it contains certain cluster structures. Four natural questions are examined. First, do there exist several points with high density that are far apart from each other. Second, do two high density points have a midpoint with low density, creating a valley between them. Third, does the region where the density is above a threshold have at least a given number of separate connected pieces. Fourth, does that same region contain a hole, meaning a loop that cannot be shrunk to a point. We prove that the first two problems, separated points and valley detection, are exactly as hard as the existential theory of the reals, a complexity class that contains NP and is believed to be strictly larger. In contrast, the topological problems of counting connected pieces and detecting holes are at least as hard as the existential theory of the reals, but their exact complexity remains open. Placing them inside that class would need a major advance in real algebraic geometry. These results give the first rigorous classification of exact continuous clustering inside the real polynomial hierarchy. They also show that even basic clustering criteria are not NP complete unless unexpected collapses occur.

聚类复杂度代数几何

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。