Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:58
bram (bram@gawth.com)
Fri, 14 Aug 1998 09:14:03 -0700 (PDT)
On Fri, 14 Aug 1998, Mok-Kong Shen wrote:
> bram wrote:
>
> > That technique requires the use of a big number class, and isn't
> > horrendously fast (it's n^3 for each node, n^4 for the whole thing), but
> > it's still polynomial, and for it not to work would require very, very
> > purposeful construction of the graph.
> >
> > I personally would just throw in the towel beforehand and view finding
> > hard graph isomorphism problems as a lost cause.
>
> The problem of graph isomorphism is not the solubility but to devise
> a method that is fast enough for practical cases.
For cryptographic purposes, I wouldn't even consider something which
relied on the slowness of an algorithm with runtime less than n^5, and
even above that I'd proceed with extreme caution, since algorithms which
run in polynomial time have the rather alarming property of tending to
have their exponents drop precipitously.
-Bram
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:58