3 ms·
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
by datascienced 2y ago
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.
- hnfong 2y agoFWIW, LLMs are currently stomped by the "mere" N^2.
- datascienced 2y agoSure that is indeed true! 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”
- PhilipRoman 2y agoWake me up when the "exponentially increasing computers" can multiply two matrices in O(n^2.371552)
- supernewton 2y agoSure, 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.