Re: (Probably flawed) Polynomial time Graph Isomorphism



On 22 Sep 2006, Bill Cox wrote:

True. Technically, this algorithm wouldn't be in 'P', which requires
absolute worse-case performance to be polynomial. So, an algorithm
that repeatedly rolls a million-sided die, and only ends when the
result is not 1, technically is not in P. Is 'RP' the correct class.
Here's the Wikipedia link:

http://en.wikipedia.org/wiki/RP_%28complexity%29

Has graph isomorphism been shown to be in RP? If not, this could be a
new result. Of course, being in RP is nearly as good as being in P,
from a usability point of view.

You're confusing random inputs with random algorithms.
On random input graphs (under a suitable distribution) graph isomorphism
is polynomially solvable (even with just a degree-sequence... i.e.
counting up the degrees of all vertices is almost always enough to test
isomorphism.)

Note that testing degree sequences is a deterministic algorithm.

The class RP deals with random algorithms or probabilistic algorithms,
which is a totally different thing.

J

.