3 ms·

I 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 reasonab

• sweezyjeezy 11y ago
  Reread 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 ago
    Reread my comment.
• mcherm 11y ago
  If 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 ago
    Any 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?