4 ms·

I know a guy who may have independently come up with the same or a similar result. He's been keeping it under wraps because he's not a mathematician and hasn't

by eximius 11y ago

I know a guy who may have independently come up with the same or a similar result. He's been keeping it under wraps because he's not a mathematician and hasn't proved it, just come up with the method. I've advised him to upload his results somewhere as soon as possible because he's been working on this for several years. I'll be very interested to see how their methods differ.

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 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.)
314 11y ago
Don't worry, we all have an idea for a method to solve GI in P tucked in the back of a drawer. Best to just let it go. Personally I know where I got stuck many years ago and I'm very excited to see somebody do it for real.
eximius 11y ago
Don't understand the downvotes guys... not cool.

by eximius 11y ago

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 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.)

314 11y ago

Don't worry, we all have an idea for a method to solve GI in P tucked in the back of a drawer. Best to just let it go. Personally I know where I got stuck many years ago and I'm very excited to see somebody do it for real.

eximius 11y ago

Don't understand the downvotes guys... not cool.