real algebraic geometry

新研究探讨连续聚类问题的计算难度

研究人员调查了直接定义在连续概率密度上的聚类问题的计算复杂性，假设密度由多项式表示。他们分析了四个问题：分离的高密度点的存在性、两个高密度点之间存在低密度中点的存在性、密度阈值区域中连通块的数量以及该区域内孔洞的检测。研究发现，检测分离点和谷的难度与实数存在性理论的难度相当，该理论被认为比NP大。连通块计数和孔洞检测的复杂性仍然是一个悬而未决的问题，可能需要实代数几何的重大进展。