News for hackers. Stuff that matters.
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by JadeNB on Wednesday November 04, 2015 @09:56PM (#10511361)
> 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.)

There are no comments on this comment yet.