On Tue, 14 Oct 2003, Christopher Benson-Manica wrote:
Arthur J. O'Dwyer <aj*@nospam.andrew.cmu.edu> spoke thus: Okay, I wasn't going to post to this thread, seeing as all I know about
graph isomorphism is that it's hard, and since I recognize 'sasha.mal'
from sci.math (or was it rec.puzzles?) I'm fairly sure he knows that.
Isn't the graph isomorphism problem one of those lovely NP-hard problems?
Or something like that?
Almost. AIUI from a brief tour of MathWorld, graph isomorphism
is in NP (of course)
is not known to be in P
is not known to be NP-complete
so it's not known to be NP-hard. Up until now, I've been kind of
colloquially using the English word "hard" to denote "not known to
be in P" (i.e., "not easy" :), but I suppose I should know to be
more precise.
[There *are* apparently a *lot* of problems reducible to graph
isomorphism, but AFAICT the problem isn't known to be NP-complete.]
-Arthur