連続クラスタリングはどれほど難しいのか？実在理論（Existential Theory of the Reals）による下界

抽象: 本論文は、連続的な確率密度上で直接定義されるクラスタリング問題の計算困難性を研究する。有限標本を扱う代わりに、密度は多項式として与えられていると仮定し、そこに特定のクラスタ構造が含まれるかどうかを問う。4つの自然な問いを検討する。第一に、高密度の複数の点が互いに十分離れて存在することはあるか。第二に、高密度の2点の中点が低密度となり、それによって両者の間に谷が形成されることはあるか。第三に、密度がある閾値を超える領域が、少なくとも所定の数の別個の連結成分を持つか。第四に、その同じ領域が穴を含むか、すなわち、点に縮められないループを含むか。第一の問題（分離した点の検出）と第二の問題（谷の検出）は、実数の存在理論（existential theory of the reals）とちょうど同じくらい難しいことを証明する。これはNPを含む複雑性クラスであり、さらに厳密に大きいと考えられている。対照的に、連結成分の数え上げや穴の検出といった位相的問題は、少なくとも実数の存在理論と同程度に難しいが、その正確な複雑性は未解決のままである。それらをそのクラスの中に位置づけるには、実代数幾何における大きな進展が必要となる。これらの結果は、実多項式階層（real polynomial hierarchy）内における、厳密な連続クラスタリングの最初の厳密な分類を与える。また、予期しない崩壊が起きない限り、基本的なクラスタリングの判定基準はNP完全にはならないことも示す。