Re: On CFL equivalence and graph isomorphism

bdm@cs.anu.edu.au (Brendan McKay)
26 Apr 2000 02:36:07 -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: bdm@cs.anu.edu.au (Brendan McKay)
Newsgroups: comp.theory,comp.compilers
Date: 26 Apr 2000 02:36:07 -0400
Organization: Australian National University
Distribution: inet
References: 00-04-140 00-04-167
Keywords: theory

"Paul Johnston" <johnston.p@worldnet.att.net> writes:
> > Furthermore, what is the state of solving the Graph Isomorhism
> > problem? Is there no hope?


Christopher Brian Colohan <colohan+@cs.cmu.edu> wrote:
> 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...).


Graph isomorphism is not known to be NP-complete, nor to be in P. It
might turn out to be neither.


The practical state of the art is that only the hardest problems
cannot be solved for up to a few tens of thousands of vertices. See
http://cs.anu.edu.au/~bdm/nauty.


> So it is possible to solve, just not in reasonable time given today's
> known algorithms. If anyone finds a way of efficiently solving
> NP-complete problems, then we will have a great deal to celebrate.


That might not be a correct statement even if the problem is
NP-complete. It is a very common myth, though. The truth is that
people solve real-life instances of NP-complete problems every day.


Brendan.


Post a followup to this message

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