computations that are in principle intractable

Doesn't the fact that the universe is carrying out these computations mean it is feasible in principle? Our current ignorance of how this is done is irrelevant. Am I missing something?

statistical mechanics of gases, which hardly changed when our view of the atoms that make up gases changed from hard Newtonian balls to fuzzy quantum blobs

This seems to be a map/territory confusion. A change in our model shouldn't change what we observe. If our high level theories changed dramatically, that would be a bad sign.