Re: Need Graph Isomorphism Algorithm De-bunked

Phil Carmody wrote:
You are checking that it actually detects isomorphisms too, aren't you? You've not explicitly said so. Else here's an O(1) algorithm which correctly differentiates all of the examples you've listed so far.

are_isomorphic(M1, M2) = are_identical(M1,M2)

Not to worry. Francois Grieu has proved that there are no false negatives. (Je ne comprends pas la preuve. Elle implique beaucoup d'onduler de main.)

--Mike Amling
.

Relevant Pages

  • Re: Online poker RNG...
    ... fold, etc., etc.) and part from-the-gut (based on years of playing B&M ... "Good colluders know, as part of their colluding, how ... My particular worry is that, as was shown possible in 1999 ... knew exactly what algorithm was being used. ...
    (sci.math)
  • Re: JSH: Your funeral
    ... computer time using the best known factoring algorithms. ... your algorithm runs about as slow as a random GCD ... never find a way to prove that with some super dramatic discovery ... discoverer then yeah, maybe you should worry. ...
    (sci.math)
  • Re: A factoring algorithm
    ... > Phil Carmody wrote: ... >>It also doesn't need knee-jerk gainsayers. ... At the time, yes, the world needed Dixon's algorithm, ... is man only a blunder of God, or God only a blunder of man? ...
    (sci.crypt)
  • Re: JSH: Your funeral
    ... computer time using the best known factoring algorithms. ... your algorithm runs about as slow as a random GCD ... discoverer then yeah, maybe you should worry. ...
    (sci.math)
  • Re: Goodbye software bloat
    ... > Phil Carmody wrote: ... > He says that his algorithm is a variation of the LZ algorithm, ... > in a table and outputting it. ... If I had a hat to eat, I'd offer to eat it if I were to be found wrong, as ...
    (alt.lang.asm)