Re: C-equivalence aware hash function

Milan VXdgsvt wrote:
>Even if we take a special case of FG's problem, where elements are only
>+1 and 0 (and thus drop the polarity operation), we have arrived at a
>problem of graph isomorphism. I was told at school this is a hard
>problem, somewhere between P and NP, just like integer factoring is.

Very interesting observation.

Graph isomorphism is not believed to be in P, but there are algorithms
for testing graph isomorphism that seem to be extremely efficient in practice.
I don't know whether they are any good at putting graphs into a normal
form, though.

Also, there is still the issue of polarity, but this suggests that it
might not necessarily require a breakthrough to solve FG's problem.
.