Re: (Probably flawed) Polynomial time Graph Isomorphism

You're confusing random inputs with random algorithms.
On random input graphs (under a suitable distribution) graph isomorphism
is polynomially solvable (even with just a degree-sequence... i.e.
counting up the degrees of all vertices is almost always enough to test
isomorphism.)

Note that testing degree sequences is a deterministic algorithm.

The class RP deals with random algorithms or probabilistic algorithms,
which is a totally different thing.

J

I see. The problem here is the algorithm relies on a hash function,
and all hash functions (like SHA-1) which output less data than is
input are not collision free. Under the assumption that we do not
repeatedly find hash-collisions again and again (which, of course, we
wouldn't with a good hash), then the algorithm could be in P (which it
probably isn't). I'm not sure what to call such an almost-P class.

The degree-sequence solution you described for random graphs has this
problem even worse. While realistically the graphs wont match if large
enough, the possibility still exists, which would cause the algorithm
to fail, thus making it technically not in P (or any class I read
about). In the case that I run into a hash-collision, I can detect
that the reported isomorphism is wrong, and just try again with
different hashing, so rather than failing, it just takes 2X longer.

I think this reliance on a hash-function is a minor thing. It makes it
difficult to describe the complexity class, but in real computational
terms, it's still O(N^3). For now, I'll just call it almost-P.

I think the harder question is whether it is possible to have
non-isomorphic graphs that will always be reported as isomorphic by
this algorithm, sort of a graph-collision, regardless of the hash
function used.

.

Relevant Pages

  • Re: Is graph isomorphism in P?
    ... algorithm runs in polynomial time. ... graphs which are "pathological", so most of the time, you can solve NP- ... This is also why the average running time is not a good measure; ... isomorphism problem, where you only look at graphs with at most 400 ...
    (sci.math)
  • Re: Is graph isomorphism in P?
    ... algorithm runs in polynomial time. ... Fra invites people to post graphs to test his isomorphism program, ... Anyway, I've no problem to solve 600x600 or 1000x1000 MI istances, ...
    (sci.math)
  • Re: Is graph isomorphism in P?
    ... "In this site you will not find the algorithm or any ... algorithm fails to find the isomorphism, ... Fra invites people to post graphs to test his isomorphism program, ...
    (sci.math)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... Bill Cox algorithm that you verified up to 8 nodes, ... not in your implementation) is in my rendering of Bill Cox's ... proved the graphs are not isomorphic. ... graphs are equal iff you have established an isomorphism between the two graphs, and to do that you have to cope with Bill Cox's automorphism issue. ...
    (sci.crypt)
  • Re: Sean PItman and nested hierarchy
    ... if God created life then the patterns in the ... the concept of "uniform probability distribution" is well-defined. ... Since the vast majority of the graphs ... Yes, it can, depending on the algorithm used. ...
    (talk.origins)