1
$\begingroup$

I've had lectures and read other threads claiming that $k$-means clustering is NP-hard. The fact that they never mention NP-completeness makes me suspect that strict NP-hardness is what's meant. This makes intuitive sense to me: problems in NP can be verified in polynomial time w.r.t. the input, and it seems like receiving a set of clusters can only be verified to be optimal by solving the entire problem once again.

Obviously, "I can't find a verification method" doesn't mean "there is no verification method". So, is $k$-means strictly in NP-hard, or is it NP-complete?

$\endgroup$
1
  • 2
    $\begingroup$ The decision problem is NP-complete even on the plane. But usually we're talking about the optimization problem, and then we say that it's NP-hard. $\endgroup$ Commented Jul 18, 2022 at 13:45

1 Answer 1

2
$\begingroup$

NP is a class of decision problems, i.e., problems where the answer is "yes" or "no". Whether $k$-means clustering is in NP depends on how you formulate it.

One standard formulation would be as an optimization problem:

Optimization: Given $n$ points, find a partition into $k$ clusters that minimizes the sum of squared distances between each point and the centroid of its cluster.

Optimization problems like this aren't technically in NP, just because the output is not just "yes" or "no" (it's a $k$-partition of the points). However, we call them NP optimization problems because the natural corresponding decision problem is in NP. Here's the natural corresponding decision problem for the above formulation:

Decision: Given $n$ points and a number $d$, is there a partition into $k$ clusters such that the sum of squared distances between each point and the centroid of its cluster is at most $d$?

This problem is almost the same as the original problem. In particular, given a solution to the decision problem and by binary searching on $d$, we can find out what the optimal sum of squared distances is fairly accurately. It's trickier to extract the actual partition from a solution to the decision problem, but in practice we usually find that algorithms for the decision problem also turn into algorithms for the optimization problem. So while the decision problem might technically be easier (it's certainly no harder, as a solution to the optimization problem also solves the decision problem), we view them as roughly the same complexity.

And the decision problem is in NP. A certificate is a partition of the points, which can be encoded in $n \log k$ bits. We can verify that the partition achieves the claimed distance by computing the centroid of each cluster and then the sum of squared distances. We need to prove that these computations only need a polynomial number of bits to be sufficiently accurate, but because it's just a linear number of additions and multiplications, this is true.

$\endgroup$
4
  • $\begingroup$ I should have been more specific about the problem; as the Wikipedia page says, computing a function $f(x) = y$ can be seen as deciding the language $\{(x,y)\mid f(x) = y\}$. That's not quite accurate, since you could peek at $y$ and do a verification instead (like when computing prime factors), but I don't think that's possible in the case of the decision problem where $x$ is a set of points and $y$ is a partition. I disagree that your decision problem has the same complexity as the one I just gave, since it allows more solutions, and if not, requires a-priori knowledge of $d$. $\endgroup$
    – Mew
    Commented Jul 18, 2022 at 14:19
  • $\begingroup$ I'm not sure I understand your point. The optimization problem can't be in NP, by definition of NP, so there isn't really more to say about it beyond "NP-hard" and "NP optimization problem" (i.e. it is the optimization version of the NP-complete decision problem parameterized by $d$). I don't think you need a-priori knowledge on $d$; you should be able to compute a range on $d$ quite easily, then binary search on that range (calling an oracle for the decision problem logarithmically many times). $\endgroup$
    – edemaine
    Commented Jul 19, 2022 at 15:06
  • $\begingroup$ What I'm saying is that optimisation problems are functions $f(x) = y$ of the situation $x$, and that you might as well consider them a decision problem for tuples $(x,f(x))$. (Otherwise, saying $k$-means is NP-hard would be nonsensical.) I'm also saying that in the case of $k$-means, being given $f(x)$ beforehand doesn't make the decision problem easier. In any case, I'm still not convinced that introducing $d$ turns our problem (whose certificates seem to only be verifiable by minimising over all possible partitions again) into an equivalent problem suddenly verifiable in mere linear time. $\endgroup$
    – Mew
    Commented Jul 19, 2022 at 17:57
  • $\begingroup$ NP and NPO are different things. Perhaps reading the definition of NPO would help clarify how to formalize "NP optimization problem"? Anyway, yes, exactly, the decision problem is almost surely not much easier than the optimization problem; giving someone $d$ almost surely doesn't help. But it does place the problem in NP (which is an unreasonable model of computation where you can guess certificates). The decision problem is in NP (as argued above) using the partition (not $d$) as the certificate. $\endgroup$
    – edemaine
    Commented Jul 19, 2022 at 20:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.