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

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?

• What is the statement of the decision problem tho? Something like for a set of points $x_i \in \mathbb{R}^d$, and a partition number $k$, does partition $D_j$ where $1 \leq j \leq k$ minimize produce minimal within cluster scatter compared to any other partition? – IntegrateThis Nov 11 '19 at 4:11