3 ms·
That's only true if you focus purely on the cost as being polynomial or not. The constant factors, the exponents, and the ability to represent difficult problem
by Strilanc 4y ago
That's only true if you focus purely on the cost as being polynomial or not. The constant factors, the exponents, and the ability to represent difficult problems compactly, can of course differ pretty substantially. The ability to find approximate solutions, and the difficulty of the average case, can also differ substantially from problem to problem. An example of an application where these kinds of details are crucial is cryptography.