Isomorphism testing is a core problem in computational complexity. Recently, Babai has shown that Graph Isomorphism problem for general graphs can be solved in quasipolynomial time. Long time before that, it has been shown that the isomorphism problem for tournament graphs is in quasipolynomial time ($QP$).

While searching for the easiest hard isomorphism testing problem, I found an interesting result which seems no one has improved on. Miller showed that isomorphism testing of projective planes can be done in $n^{O(\log \log n)}$. This is very interesting since this upper-bound is almost polynomial time.

Is Miller's algorithm still the fastest known algorithm? Is there a polynomial-time algorithm?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.