News for hackers. Stuff that matters.
Re:Efficient algorithms, the Exponential Time Hypothesis, an... by tsimionescu on Tuesday November 03, 2026 @08:05AM (#50351514)
> For example, we now have now have a deterministic interger factoring algorithm with run time N^o(1), where N is the integer being factored. Heuristic algorithms already achieved this bound, but the new claim is a deterministic worst-case guarantee. The result is a fairly straightforward application of the new 3-SAT solver.

This can't be true unless you're talking about unfathomably large integers, since the new 3SAT algorithm only improves on the 2^n bound for n > 10^100000000. That is, it's not in any way a practical algorithm that will ever be runnable on any possible computer.

There are no comments on this comment yet.