NP-hard – the meaning of P

The P here means that the time to solve or verify the solution of a problem is polynomial (poly=many, nomial=terms). For example, x³ is a polynomial.

Once x is known, then x³ will be computed. Applied to 3,000,000,000 records, an estimation can be applied:

x³ = 3,000,000^3

It seems a lot but it isn't that much for two reasons:

• In a world of big data, the number can be subject to large-scale randomized sampling
• K-means clustering can be trained by mini-batches (subsets of the dataset) to speed up computations

The big difference between a polynomial function and an exponential function relies, in this case, on x being the variable, and 3 the exponent.

In an exponential function, x would be the variable and 3 the constant. With x as an exponent, the time to solve this problem would be exponential. It's certainly not a polynomial time you can predict.

3^{3,000,000,000} is something you don't even want to think about!

Polynomial time means that this time will be more or less proportional to the size of the input. Even if the time it takes to train the k-means clustering remains a bit fuzzy, as long as the time it will take to verify the solution remains proportional to the size of the input, the problem remains a polynomial.

The IT department feels better about the problem. The volume of the training process will overload their servers. They do not have the time to purchase a server and set it up.