In reality if you have O(N^1000000) that is still going to be a killer for our exponential increasing computers. For any N you can wait for computation to catch up but N*2 will stomp you for quite a while.
I meant polynomial time can in practical terms stomp computers even if you are allowed to time travel to a future point in moores law. Maybe n^2 is enough but need to do the math! The derivative is 2n so seems like it depends on n and the problem and of course the constants.
Or maybe human life is just too short to wait for the “42”
By "natural" I mean a problem that one would actually want to solve, not some contrived problem specifically to make it O(n^100) since that's obviously easily possible.