It sounds (towards the end) that this is saying that accepting a approximation of correct is often good enough, and that can often be made polynomial time.<p>Which is of course correct. There are lots of algorithms where there exist theoretical minimum complexities, but good approximations can do far better: lossy compression for example vastly beats the Shannon limit, google maps doesn’t take decades to plot a route from San Francisco to New York, etc