3 ms·
Giving false proofs that GI is in P or a related time class is, I think, a common occupation (see, for example, https://rjlipton.wordpress.com/2009/11/04/on-mat
by JadeNB 11y ago
Giving false proofs that GI is in P or a related time class is, I think, a common occupation (see, for example, https://rjlipton.wordpress.com/2009/11/04/on-mathematical-diseases https://rjlipton.wordpress.com/2009/11/04/on-mathematical-di... ); so, if all you know is that this guy thinks he has a solution to the problem, and if the guy is not a mathematician and doesn't have a proof, then the balance of probabilities is that he's probably mistaken (but there's no harm in making the work publicly available, just in case).
- eximius 11y agoI'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.)