Algorithms testing two graphs for isomorphism known as yet have exponential worst case complexity. In this paper we propose a new algorithm that has polynomial complexity and constructively supplies the evidence that the graph isomorphism lies in P.
Will be very interesting to see if the algorithm is indeed correct. I wonder how this process works. Do they have millions of comp sci geeks on hand to verify it? I know that these computational complexity problems were the most interesting problems I did in school. Reducing one problem to the other was awesome.
I'm going to try and give it a read if I have some time and brainpower.