Artificial Intelligence By Example

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 ...