aiqbench analysis
This research establishes the Universal Clustering Problem as NP-hard by unifying ten major unsupervised learning paradigms under a single optimization framework. The findings provide a rigorous theoretical explanation for common practical failures, such as sensitivity to initialization and entrapment in local optima across diverse algorithms like k-means and DBSCAN. By linking these instability issues to fundamental computational constraints, the work motivates a shift toward stability-aware objectives with explicit guarantees.
Universal NP-Hardness of Clustering under General Utilities
arXiv:2603.00210v2 Announce Type: replace-cross Abstract: Clustering is a central primitive in unsupervised learning, yet practice is dominated by heuristics whose outputs can be unstable and highly sensitive to representations, hyperparameters, and initialisation. Existing theoretical results are largely objective-specific and do not explain these behaviours at a unifying level. We formalise the common optimisation core underlying diverse clustering paradigms by defining the Universal Clustering Problem (UCP): the maximisation of a polynomial-time computable partition utility over a finite metric space. We prove the NP-hardness of UCP via two independent polynomial-time reductions from graph colouring and from exact cover by 3-sets (X3C). By mapping ten major paradigms -- including k-means, GMMs, DBSCAN, spectral clustering, and affinity propagation -- to the UCP framework, we demonstrate that each inherits this fundamental intractability. Our results provide a unified explanation for characteristic failure modes, such as local optima in alternating methods and greedy merge-order traps in hierarchical clustering. Finally, we show that clustering limitations reflect interacting computational and epistemic constraints, motivating a shift toward stability-aware objectives and interaction-driven formulations with explicit guarantees.
Abstract:Clustering is a central primitive in unsupervised learning, yet practice is dominated by heuristics whose outputs can be unstable and highly sensitive to representations, hyperparameters, and initialisation. Existing theoretical results are largely objective-specific and do not explain these behaviours at a unifying level. We formalise the common optimisation core underlying diverse clustering paradigms by defining the Universal Clustering Problem (UCP): the maximisation of a polynomial-time computable partition utility over a finite metric space. We prove the NP-hardness of UCP via two independent polynomial-time reductions from graph colouring and from exact cover by 3-sets (X3C). By mapping ten major paradigms -- including k-means, GMMs, DBSCAN, spectral clustering, and affinity propagation -- to the UCP framework, we demonstrate that each inherits this fundamental intractability. Our results provide a unified explanation for characteristic failure modes, such as local optima in alternating methods and greedy merge-order traps in hierarchical clustering. Finally, we show that clustering limitations reflect interacting computational and epistemic constraints, motivating a shift toward stability-aware objectives and interaction-driven formulations with explicit guarantees.
Computational Complexity (cs.CC); Artificial Intelligence (cs.AI)
arXiv:2603.00210 [cs.CC]
(or arXiv:2603.00210v2 [cs.CC] for this version)
https://doi.org/10.48550/arXiv.2603.00210 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 265 words
Related coverage
Interview with Matthias Troyer, Vice President & Technical Fellow at Microsoft
Quantum Computing Report · Sep 23, 2026
The hard physics and complex economics of AI’s insatiable hunger for power
SiliconANGLE · Sep 11, 2026
Social Theory and Agent Foundations
LessWrong · Oct 8, 2026
What We're Up Against: An AI Safety Crash Course
LessWrong · Sep 24, 2026