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?

  • $\begingroup$ Cross-posted from cstheory.stackexchange.com/questions/34773 $\endgroup$ – Emil Jeřábek May 20 '16 at 16:47
  • $\begingroup$ Can you give a proper reference instead of a link to something on google books that has exhausted its viewing limit? Also, what do you mean by “better than polynomial time”? $\endgroup$ – Emil Jeřábek May 20 '16 at 16:51
  • $\begingroup$ @EmilJeřábek "better than polynomial time" means for small $n$ the run time is smaller than polynomial run-time $n^c$ with small $c \le 8$. I edited it out to remove ambiguity. $\endgroup$ – Mohammad Al-Turkistany May 20 '16 at 16:56
  • $\begingroup$ Babai and Luks extended Miller's result to show that isomorphism testing for symmetric designs can be done in $n^{O(\log \log n)}$. books.google.com.sa/… $\endgroup$ – Mohammad Al-Turkistany May 20 '16 at 19:55
  • $\begingroup$ Relatively recent paper by Huber suggests that Miller's algorithm is the best known algorithm (until 2010): sciencedirect.com/science/article/pii/S0097316510001044 $\endgroup$ – Mohammad Al-Turkistany May 28 '16 at 17:44

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.