Re: On CFL equivalence and graph isomorphism

Christopher Brian Colohan wrote:
>
> "Paul Johnston" <johnston.p@worldnet.att.net> writes:
>
> > Furthermore, what is the state of solving the Graph Isomorhism
> > problem? Is there no hope?
>
> I believe it has been proven to be NP-complete (I need to check in my
> Gary&Johnson to be sure, and I am out of town...).


Er I don't. Perhaps Christopher Colohan is confusing it with Subgraph
Isomorphism (which is indeed NP-complete). Graph Isomorphism doesn't
seem to be nearly as hard as that. I get the impression it's rather
like telling knots apart, in that there are quite a lot of
characteristics (degree sequences and generalisations thereof,
eigenvalues and angles with eigenvectors . . .) which will distinguish
virtually all pairs of graphs quickly, but all known polynomial
methods so far fail to distinguish a few irritating cases. But I'm
somewhat out of date; for all I know someone has a polynomial
algorithm now. I don't think it is unlikely that a polynomial
algorithm will be discovered some time in the future, or it might be
(as I think G&J suggests) that this is one of a class of problems
which are just a little bit worse than "P" but not anything like
"NP-complete".

Return to the comp.compilers page.
Search the comp.compilers archives again.