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

Referee: [Proof of the ∃R-hardness results for separated points and valley detection] The central hardness claims for separated-points and valley detection require that the reduction from an arbitrary ∃R sentence produces a valid probability density (non-negative polynomial that integrates to 1) while preserving the clustering predicate. The manuscript must contain an explicit non-negativity lemma and normalization argument (likely in the proof of the main hardness theorem for these two problems) showing that adding a sufficiently large constant and rescaling leaves the existence of points with p(xi) > t and ||xi − xj|| > d, or the valley condition, invariant. Without this, the reduction only establishes hardness for arbitrary polynomials rather than the probability-density model stated in the title and abstract.

Authors: We appreciate the referee for identifying this gap in explicitness. The original reduction begins with an arbitrary polynomial arising from the ∃R sentence and defines high-density points and valleys relative to a threshold; negativity of the polynomial does not affect the predicate because we may always shift the threshold upward. In the revised manuscript we have inserted an explicit Non-negativity Lemma (Lemma 3.4) stating that for any polynomial q there exists C large enough so that p = q + C ≥ 0 everywhere on the compact domain of interest, together with a Normalization Argument showing that the integral Z = ∫p is a positive constant that can be absorbed into a rescaled threshold t′ = t·Z without changing the existence of points satisfying the separated-points or valley conditions. The proof of the main hardness theorem (Theorem 3.1) now invokes this lemma directly, so the reduction is valid for probability densities. We believe this fully resolves the concern. revision: yes

Referee: [Section on topological clustering problems] For the topological problems (connected components and holes), the paper establishes ∃R-hardness but leaves membership open, citing the need for major advances in real algebraic geometry. A concrete discussion of the precise obstruction (e.g., why the semi-algebraic set defined by the superlevel set cannot be directly encoded as an existential sentence without additional quantifier alternations) would strengthen the claim that placement in ∃R is not immediate.

Authors: We agree that a more concrete explanation of the obstruction strengthens the discussion. The superlevel set S = {x | p(x) ≥ t} is indeed semi-algebraic, yet deciding whether S has at least k connected components or contains a hole requires determining global topological invariants. Such properties cannot be expressed by a purely existential sentence over the reals: verifying path-connectedness or the absence of a non-contractible loop inherently involves universal quantification (e.g., “there does not exist a path connecting two points in different putative components”). Consequently, any first-order sentence capturing these predicates requires at least one quantifier alternation and therefore lies outside ∃R unless the real polynomial hierarchy collapses. We have added a new paragraph in Section 4.3 that spells out this quantifier-alternation obstruction and cites the relevant results on the complexity of semi-algebraic topology. This makes the open-membership claim more precise while leaving the possibility of future advances in real algebraic geometry open. revision: yes