3 ms·
Yeah, but the question is does the new algorithm beat the old ones for problems that are solvable in reasonable time. A constant time algorithm is not that use
by sweezyjeezy 11y ago
Yeah, but the question is does the new algorithm beat the old ones for problems that are solvable in reasonable time. A constant time algorithm is not that useful if the constant happens to be 10^1000 years.
- jsprogrammer 11y agoI don't think this claims to be a constant time algorithm. Can someone rule out that there are no problem instances that this algorithm can solve in a reasonable time that others cannot?
- sweezyjeezy 11y agoReread my comment, I'm not saying that it's a constant time algorithm, I'm saying that even constant time algorithms can be impractical.
- jsprogrammer 11y agoReread my comment.
- mcherm 11y agoIf the paper is correct then there ARE problems that this algorithm can solve in less time than others. But it may be that every problem on which it is faster requires more bits of memory than there are atoms in the universe. Or that every problem on which it is faster would have a runtime that is 10^100 times the lifetime of the universe.
- jsprogrammer 11y agoAny of those things could be the case. I'd modify your second sentence to say known atoms in the universe, and the second: projected lifetime. Do you know if the paper (or any commentary) addresses these concerns?