3 ms·

I've seen the method and I have a background in math, just not enough to really help prove it. I was never claiming that he succeeded, just that he had somethi

by eximius 11y ago

I've seen the method and I have a background in math, just not enough to really help prove it. I was never claiming that he succeeded, just that he had something similar that worked in all our tests, at least. Even if his solution isn't polynomial it might be quasi polynomial like this result, in which case the differences would be enlightening. The most likely case is that my friends work is polynomial but wrong in some obscure way. But it will be interesting nonetheless.

JadeNB 11y ago
> I was never claiming that he succeeded, just that he had something similar that worked in all our tests, at least. It's hard to tell the running time of an algorithm by testing; an O(1) algorithm is indistinguishable from an O(2^(2^n)) algorithm if you only run them on inputs up to n = 10^(10^(10^(34))), say. (That sounds facetious, and it kind of is, but it cuts the other way, too: I seem to remember that polynomial-time primality testing isn't used in practice because the constants are so huge that, on 'real-life' inputs, it's impractically worse than probabilistic testing.)