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”
Sure, but in practice there don't really seem to exist "natural" problems that are both in P and are worse than O(n^3) or so.
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.
hnfong|1 year ago
datascienced|1 year ago
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”
supernewton|1 year ago
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.
PhilipRoman|1 year ago