Бабаи, Ласло

We show that the Graph Isomorphism проблема изоморфизма графов and the related problems of String Isomorphism^[14] (under action group) (SI) and Coset Intersection (CI)^[15] can be solved in quasipolynomial

${\displaystyle \exp \left(\left(\log n\right)^{O\left(1\right)}\right)}$

time. The best previous bound for GI was

${\displaystyle \exp \left(O\left({\sqrt {n\log n}}\right)\right)}$

where ${\displaystyle n}$ is the number of vertices (Юджин M. Лукс, 1983); for the other two problems, the bound was similar,

${\displaystyle \quad \qquad \exp \left({\tilde {O}}\left({\sqrt {n}}\right)\right)}$

where ${\displaystyle n}$ is the size of the permutation domain (Babai, 1983).

The algorithm builds on Luks's SI framework and attacks the barrier configurations for Luks's algorithm group by theoretic «local certificates and combinatorial canonical partitioning techniques. We show that in a well-defined sense, граф Джонсона are the only obstructions to effective canonical partitioning.