What does it mean for K mean problem to be NP hard and why?

Question

Given a decision problem (a problem with yes or no answer), the problem is said to be NP-hard if there is an NP-complete problem Y, such that Y is reducible to X in polynomial time.

Recall that NP-complete represents the set of all problems X in NP for which it is possible to reduce any other NP problem Y to X in polynomial time, and an NP is a complexity class that represents the set of all decision problems for which the instances where the answer is "yes" have proofs that can be verified in polynomial time.

From these definitions, it is not obvious to me why people say that K-mean is an NP hard problem.

First, the goal of K-mean is to produce an optimal (in the sense of Euclidean distance) set of set-vector pairs $\{(S, \mu)\}$, where set represents the membership of the data and the vector represents the centroid of the data. This is clearly not a decision problem.

Let's for the sake of the argument we can make the equivalence that the decision problem at hand is whether if there exists an optimal set or not (forget even computing the solution, just check existence). Then what characteristics of K-mean makes it NP hard? We know that it is an optimization problem, it is non-convex due to the fact that the centroids form a discrete set of points, but why does this necessarily mean that it is NP hard?

Answer 1

You can likely encode other known NP-complete problems such as set-cover or 3SAT using a high-dimensional space with binary variables such that finding the global optimum "k-means" clustering solves these problems.

For a full proof of NP-hardness, please visit the actual literature on this topic. I am pretty sure your can find papers that show the exact constructions necessary. For example:

Dasgupta, Sanjoy. The hardness of k-means clustering. Department of Computer Science and Engineering, University of California, San Diego, 2008.

Mahajan, Meena, Prajakta Nimbhorkar, and Kasturi Varadarajan. "The planar k-means problem is NP-hard." Theoretical Computer Science 442 (2012): 13-21.

P.S. k-means does not minimize Euclidean distance!