Skip to main content
As per Gerhard's remark.
Source Link
Adam P. Goucher
  • 12.4k
  • 2
  • 54
  • 105

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

$$ O(\exp(\log^c n)) $$$$ \exp(O(\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.)

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.)

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

$$ \exp(O(\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.)

Source Link
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.)