Re: On CFL equivalence and graph isomorphism

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

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