Skip to main content
1 of 2
Adam P. Goucher
  • 12.4k
  • 2
  • 54
  • 105

Complexity of graph isomorphism

Last year, Laszlo Babai proved that the graph isomorphism problem can be solved in time:

$$ O(\exp(\log^c n)) $$

where $n$ is the number of vertices.

What is the best bound we have for $c$? (The case $c = 1$ would correspond to a polynomial-time algorithm for graph isomorphism.)

Adam P. Goucher
  • 12.4k
  • 2
  • 54
  • 105