Re: On CFL equivalence and graph isomorphism

George Russell <ger@informatik.uni-bremen.de>
26 Apr 2000 02:34:48 -0400

          From comp.compilers

Related articles
On CFL equivalence and graph isomorphism johnston.p@worldnet.att.net (Paul Johnston) (2000-04-20)
Re: On CFL equivalence and graph isomorphism lex@cc.gatech.edu (2000-04-25)
Re: On CFL equivalence and graph isomorphism colohan+@cs.cmu.edu (Christopher Brian Colohan) (2000-04-25)
Re: On CFL equivalence and graph isomorphism pmoisset@altavista.net (Pablo) (2000-04-25)
Re: On CFL equivalence and graph isomorphism ger@informatik.uni-bremen.de (George Russell) (2000-04-26)
Re: On CFL equivalence and graph isomorphism bdm@cs.anu.edu.au (2000-04-26)
Re: On CFL equivalence and graph isomorphism dmolnar@fas.harvard.edu (David A Molnar) (2000-04-27)
Re: On CFL equivalence and graph isomorphism miyazaki@symbolix.cs.uoregon.edu (2000-04-27)
| List of all articles for this month |

From: George Russell <ger@informatik.uni-bremen.de>
Newsgroups: comp.theory,comp.compilers
Date: 26 Apr 2000 02:34:48 -0400
Organization: Universitaet Bremen, Germany
Distribution: inet
References: 00-04-140 00-04-167
Keywords: parse, theory

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


Post a followup to this message

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