9
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ Cross-posted from cstheory.stackexchange.com/questions/34773 $\endgroup$ May 20, 2016 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$ May 20, 2016 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$ May 20, 2016 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$ May 20, 2016 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$ May 28, 2016 at 17:44

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.