The largest I've seen [1] is an exponent of 10^12, which I suppose still counts as polynomial time.
replyI'm sure all of these super small or large constants will improve over time, but it's still amusing. It is entertaining to see the exponents directly rather than have them hidden as n^c or epsilon or O(1).
[1]: https://github.com/openai/math/blob/main/preprints/Determini...
That's why I grimace when I see pop-sci descriptions of P as "all problems that can be solved efficiently".
replyTo be fair, there is a pretty strong correlation between a problem being in BPP and being efficiently solvable in practice.
replyThere are some exceptions of course (graph isomorphism was solved in practice when the best theoretical algorithms were still exponential) but in general once people find a n^100000 algorithm it soon turns into a n^3 algorithm with reasonable coefficients.
well nobody uses AKS right?
replyIt's efficient, but somewhat slow..
replyThe runtime looks very weird. The +2 can and should be dropped. This reduces my confidence that the bound is tight. Who knows how the model came up with that expression.
replyIs it mostly an artifact of the proof or does the algorithm actually need anything close to it?
reply